Which sorting algorithm would be best for a X set of integers?
I am wondering about which sorting algorithm would be most efficient for sorting:
(Presuming they are integers)
1. An array with 10 elements that are unsorted
2. An array with 100.000 elements that are unsorted
3. An array with 100.000 elements that are almost sorted
4. An array with 100.000 elements that are almost sorted in the opposite order.
Would it be different if these algorithms where something else than integers too?
Say you have these algorithms to choose from:
Selection Sort, Insertion Sort, Bubble Sort, Shell Sort and Merge Sort.
I'm also genuinely interested in how this is thought through. Personally, I've learned these algorithms to some degree. But I still find it difficult to see the full extent of how one should apply these algorithms practically.
(Presuming they are integers)
1. An array with 10 elements that are unsorted
2. An array with 100.000 elements that are unsorted
3. An array with 100.000 elements that are almost sorted
4. An array with 100.000 elements that are almost sorted in the opposite order.
Would it be different if these algorithms where something else than integers too?
Say you have these algorithms to choose from:
Selection Sort, Insertion Sort, Bubble Sort, Shell Sort and Merge Sort.
I'm also genuinely interested in how this is thought through. Personally, I've learned these algorithms to some degree. But I still find it difficult to see the full extent of how one should apply these algorithms practically.
1&2 are you favorite n log n sort. for these tiny arrays, avoiding recursion is preferable and it is likely shellsort will beat poor implementations of n log n sorts, but that is *implementation* not *run time analysis*. So in theory the n log n wins but in practice a hot iteration might beat it... shell sort tends to be n^7/6 and you might plot this against n log n … as I recall, n log n is always better on paper.
3 & 4 are shellsort hands down. shell is very hard to understand, but part of its charm is that it handles nearly sorted or nearly backwards sorted data very, very well (it approaches O(N) as the list approaches sorted and reverse sorted).
***1-4 are all bucket sort if the # of values vs available ram are tractable; eg for 16 bit ints, 32 on large machines, etc... this overrides my previous answer
-- bucket isn't usuable on most non integer data, unless it can be converted to a small range of int values.
the other algorithms are the same no matter what type of data, but fat data that costs a lot to move is better sorted via pointer swapping than data swapping...
your selection of sorts is way incomplete. you at least need quicksort in the mix.
practically you want to use the built in std::sort.
second practically, shellsort is good for small arrays, platforms that don't support recursion or have limited resources for recursion (embedded systems), the n squared sorts have no value at all apart from learning, merge sort is good for linked list type structures and files, do you see why?
many quicksorts use shell once the array splitting gets small enough (varies by hardware).
for large lists, think about how you might do a parallel processing attack on the data?
3 & 4 are shellsort hands down. shell is very hard to understand, but part of its charm is that it handles nearly sorted or nearly backwards sorted data very, very well (it approaches O(N) as the list approaches sorted and reverse sorted).
***1-4 are all bucket sort if the # of values vs available ram are tractable; eg for 16 bit ints, 32 on large machines, etc... this overrides my previous answer
-- bucket isn't usuable on most non integer data, unless it can be converted to a small range of int values.
the other algorithms are the same no matter what type of data, but fat data that costs a lot to move is better sorted via pointer swapping than data swapping...
your selection of sorts is way incomplete. you at least need quicksort in the mix.
practically you want to use the built in std::sort.
second practically, shellsort is good for small arrays, platforms that don't support recursion or have limited resources for recursion (embedded systems), the n squared sorts have no value at all apart from learning, merge sort is good for linked list type structures and files, do you see why?
many quicksorts use shell once the array splitting gets small enough (varies by hardware).
for large lists, think about how you might do a parallel processing attack on the data?
Last edited on
As always, thank you for a good answer Jonnin! I appreciate it :D Quick sort is actually an algorithm I meant to put in. Would that change much if u had Quick Sort?
Last edited on
Not really.
Again, for 1&2, a really good quicksort will tie or beat shellsort. BUT as I also said a lot of quicksorts ARE shellsort when the recursion stops ... your array sizes are so small that 'quicksort' may actually BE some other sort instead because it is too small a list to bother with sub-divide via the recursion. And again, it gets into implementation vs theory... in "theory" n log n is faster than n^7/6 .... but if each iteration takes 10 times longer for the n log n code, is that still true in *practice* ?? Sometimes the 'better' run time analysis is slower due to the actual work being done (at the cpu clock cycles level) being significantly higher for the 'faster' algorithm. Change that 100 to a billion and the faster algorithm overcomes this issue and handily beats the slower algorithm as expected, though. the good news is that even if you used a N squared sort on 100 items it will still be done faster than you can print out how much time it took, so it really does not matter for small data. Don't even get INTO this kind of thinking for small amounts of data, just use std::sort unless you have an exceptionally large amount of sorting to do that is actually giving you a performance hit.
Note that a hybrid (swap to another sort) version of quicksort is 1) not exactly N log N and 2) not the pure 'algorithm' ... its an implementation detail and performance tweak. Multithreading and mergesorting back is similar, a hybrid performance tweak.
Honestly, if std::sort is not doing it, you are probably doing something very specialized, and you will know if and when that happens. Its a very good tool.
Again, for 1&2, a really good quicksort will tie or beat shellsort. BUT as I also said a lot of quicksorts ARE shellsort when the recursion stops ... your array sizes are so small that 'quicksort' may actually BE some other sort instead because it is too small a list to bother with sub-divide via the recursion. And again, it gets into implementation vs theory... in "theory" n log n is faster than n^7/6 .... but if each iteration takes 10 times longer for the n log n code, is that still true in *practice* ?? Sometimes the 'better' run time analysis is slower due to the actual work being done (at the cpu clock cycles level) being significantly higher for the 'faster' algorithm. Change that 100 to a billion and the faster algorithm overcomes this issue and handily beats the slower algorithm as expected, though. the good news is that even if you used a N squared sort on 100 items it will still be done faster than you can print out how much time it took, so it really does not matter for small data. Don't even get INTO this kind of thinking for small amounts of data, just use std::sort unless you have an exceptionally large amount of sorting to do that is actually giving you a performance hit.
Note that a hybrid (swap to another sort) version of quicksort is 1) not exactly N log N and 2) not the pure 'algorithm' ... its an implementation detail and performance tweak. Multithreading and mergesorting back is similar, a hybrid performance tweak.
Honestly, if std::sort is not doing it, you are probably doing something very specialized, and you will know if and when that happens. Its a very good tool.
Last edited on
Topic archived. No new replies allowed.