StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>For the first question: If your array have only a small set of unique values (like 28 as you say) you may want to consider some sort of counting sort (flavors: radix, pigeonhole, bucket). If you know hard limits and ranges of your array content you may be able to do something good.</p> <p>But as previously said, for such small array you are probably good with std::sort, unless you have a lot of 5000-element arrays to sort.</p> <p>For the second question: Length matter (see sky's answer). O(n log n) is the best any normal sort can do. O(n^2) is normally the worst case. O(n^2) means that in worst case your 20 element array would need time corresponding to 20^2 (=400) operations, and your 5000 array time corresponding to 5000^2 (=25million) operations. As you can see larger array means much more time in this case. For your case and a O(n log n) algorithm the 5000 array would need time corresponding to 5000 log 5000 (=18500) operations. </p> <p>What an operation is and how long it takes depend on the particular implementation, and is in general irrelevant for comparison (and thus ignored with Ordo notation). A slow implementation of a O(n log n) algorithm will still be faster than a fast implementation of a O(n^2) algorithm when the array size is large enough. But for a small array like 20 elements a good low overhead implementation matter most. 400 fast operations will be faster than 26 slow operations. Same comparison for 5000 array give that 25million fast operations would still not be faster than 18500 slow operations.</p> <p>Another factor is the content of the array. Some algorithms, like insertion sort, are particularly fast (approaching O(n)) on arrays that are in almost correct order, while poor O(n^2) on random input.</p> <p>By utilizing predefined (known) limitations/ranges on array content (thus not a classified as a normal sort) counting sort can approach O(n), that is, the time is directly proportional to the number of elements. See wikipedia.</p> <p>Happy research!</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