StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Using any additional data structure won't help. Since most of your data is already sorted and you just need to fix the occasional value, use a simple array to extract data, then use <strong>Insertion Sort</strong>.</p> <p>Insertion sort runs in <strong>O(n)</strong> for mostly presorted data.</p> <p>However, this depends if you can hold large enough an array in memory or not depending upon your input size.</p> <p><strong>Update:</strong></p> <p>I wasn't very clear on your definition of "<strong>mostly sorted</strong>". Generally it means <em>only few elements are not in the precise sorted position</em>.</p> <p>However, as you stated further, <em>'data is in different files where each file is individually sorted'</em>, then may be it is a good candidate for the sub function call - <strong>Merge</strong> as in merge Sort.</p> <p>Note that Merge routine, merges two already sorted arrays. If you have say 10 files where each of them is individually sorted for sure, then using Merge routine would only take O(n).</p> <p>However, if you have even a few off instances where a single file is not perfectly sorted (on its own), you need to use Insertion Sort.</p> <p><strong>Update 2:</strong></p> <p>OP says he cannot use an array because he cannot know the number of records in advance. Using simple link list is out of question, since that never competes with arrays (sequential vs random access time) in time complexity.</p> <p>Pointed out in comments, <strong><em>using link list is a good idea IF the files are individually sorted and all you need to run on them is the merge procedure</em>.</strong></p> <p>Dynamically allocated arrays are best, if he can predict size at some point. Since c++ tag was used (only removed latter), going for vector would be a good idea, since it can re size comfortably.</p> <p>Otherwise, one option might be <strong>Heap Sort</strong>, since it would call heapify first i.e. build a heap (so it can <em>dynamically accommodate</em> as many elements needed) and <strong>still produce O(nlogn)</strong> complexity. This is still better than trying to use a link list.</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