StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You asked the question <a href="https://stackoverflow.com/questions/18820288/sorting-based-on-key-from-a-file">Sorting based on key from a file</a> and were given various answers about how to sort in memory. You added a supplemental question as an answer, and then created this question instead (which was correct).</p> <p>Your code here is basically a disk-based bubble sort, with O(N<sup>2</sup>) complexity, and poor time performance because it is manipulating file buffers and disk. A bubble sort is a bad choice at the best of times — simple, yes, but slow.</p> <p>The basic ways to speed up sorting programs are:</p> <ol> <li>If possible, read all the data into memory, sort in memory, and write the result out.</li> <li>If it won't all fit into memory, read as much into memory as possible, sort it, and write the sorted data to a temporary file. Repeat as often as necessary to sort all the data. Then merge the temporary files into one file. If the data set is truly astronomical (or the memory truly minuscule), you may have to create intermediate merge files. These days, though, you have to be sorting many hundreds of gigabytes for that to be an issue at all, even on a 32-bit computer.</li> <li>Make sure you choose a good sorting algorithm. Quick sort with appropriate pivot selection is very good. You could look up 'introsort' too.</li> </ol> <p>You'll find example in-memory sorting code in the answers to the cross-referenced question (your original question). If you choose to write your own sort, you can consider whether to base the interface on the standard C <code>qsort()</code> function. If you write a Quick Sort, you should look at <a href="https://stackoverflow.com/questions/164163/quicksort-choosing-the-pivot/164183#164183">Quicksort — Choosing the pivot</a> where the answers have copious references.</p> <p>You'll find example merging code in the answer to <a href="https://stackoverflow.com/questions/18812266/merging-sorted-multiple-files-into-1-sorted-file">Merging multiple sorted files into one file</a>. The merging code out-performs the system <code>sort</code> program in its merge mode, which is intriguing since it is not highly polished code (but it is reasonably workmanlike).</p> <p>You could look at the external sort program described in <a href="http://rads.stackoverflow.com/amzn/click/020103669X" rel="nofollow noreferrer">Software Tools</a>, though it is a bit esoteric in that it is written in 'RatFor' or Rational Fortran. The design, though, is readily transferrable to other languages.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload