Menu
This is the problem I ran into long time ago. I thought I may ask your for your ideas. assume I have very small list of numbers (integers), 4 or 8 elements, that need to be sorted, fast. what would be the best approach/algorithm?
my approach was to use the max/min functions (10 functions to sort 4 numbers, no branches, iirc).
// s(i,j) == max(i,j), min(i,j) i,j = s(i,j) k,l = s(k,l) i,k = s(i,k) // i on top j,l = s(j,l) // l on bottom j,k = s(j,k) I guess my question pertains more to implementation, rather than type of algorithm.
At this point it becomes somewhat hardware dependent , so let us assume Intel 64-bit processor with SSE3 .
Thanks
268
Insertion sort or selection sort are both typically faster for small arrays (i.e., fewer than 10-20 elements).
But since it has the upper hand in the average cases for most inputs, Quicksort is generally considered the “fastest” sorting algorithm.
3) For small size data sets, Insertion sort is more efficient than Quicksort and Heapsort. 4) For large size data sets, Heapsort is better than the other twos, Heapsort is a better choice.
Insertion Sort – If the data is nearly sorted or when the list is small as it has a complexity of O(N2) and if the list is sorted a minimum number of elements will slide over to insert the element at it's correct location. This algorithm is stable and it has fast running case when the list is nearly sorted.
For small arrays like this, you should probably look into sorting networks. As you can see on that page, insertion sort can be expressed as a sorting network. However, if you know the size of the array beforehand, you can devise an optimal network. Take a look at this site that can help you to find optimal sorting networks for a given size of array (though optimal is only guaranteed up to a size of 16 I believe). The comparators are even grouped together in operations that can be done in parallel. The comparators are essentially the same as your s(x,y) function though if you really want this to be fast, you shouldn't be using min and max because then you're doing twice the number of comparisons that are necessary.
If you need this sorting algorithm to work on a wide range of sizes, then you should probably just go with insertion sort as others have suggested.
122
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
