Original Post
Of all the sorting algorithms (eg. Bubble Sort, Shell Sort, etc.), which one is the fastest?
Thanx!
🔒 Locked
Sorting Algorithms
Advertisement
The answer isn''t as simple as that. The answer depends on what you are trying to sort and what you already know about the data.
Although there has been some research developments in this field recently I don''t know about here is what I suggest:
In case you need to sort objects that has fairly few values (say the set of integers) then radix-sort, bucket-sort, and distribution-sort is the fastest. (These algorithms can sort in linear time!)
Otherwise, the sort algorithms with the best worst-case is heap-sort and merge-sort. Heap-sort is probably a bit slower than merge sort but has the advantage that the sort can be done in place very easily.
However, if you want to optimize for the best average sorting time quick-sort is best - but quick sort performs very poorly in some cases.
Insertion sort (of which Shell''s sort is a varient), bubble sort, etc. are slow and should be avoided if you need high speed.
Although there has been some research developments in this field recently I don''t know about here is what I suggest:
In case you need to sort objects that has fairly few values (say the set of integers) then radix-sort, bucket-sort, and distribution-sort is the fastest. (These algorithms can sort in linear time!)
Otherwise, the sort algorithms with the best worst-case is heap-sort and merge-sort. Heap-sort is probably a bit slower than merge sort but has the advantage that the sort can be done in place very easily.
However, if you want to optimize for the best average sorting time quick-sort is best - but quick sort performs very poorly in some cases.
Insertion sort (of which Shell''s sort is a varient), bubble sort, etc. are slow and should be avoided if you need high speed.
Well, it depends on the order of your data.
The ones I use most extensively and seem to do wonders for me are quicksort and merge sort. They are both O(n log n) if the data is "good", and O(n2) if the data is "bad."
The quicksort is the faster of the two, and the merge sort uses a more than double the memory (due to the second array). They are both recursive, so that could be a con or a pro depending on who (or what) taught you how to program, but they both can be implemented in a non-recursive fashion though it doesn't yield any significant improvement on most machines.
The quicksort is the most practical sort function, but there are others such as the heap sort that are better than the quicksort for extremely large (around 107+ (dependent on the machine of course) items. [Edit] There are others that are better for small data sets too. But, for the best overall performance I'd stick with the quicksort.
[edited by - Floppy on June 1, 2002 7:27:00 PM]
The ones I use most extensively and seem to do wonders for me are quicksort and merge sort. They are both O(n log n) if the data is "good", and O(n2) if the data is "bad."
The quicksort is the faster of the two, and the merge sort uses a more than double the memory (due to the second array). They are both recursive, so that could be a con or a pro depending on who (or what) taught you how to program, but they both can be implemented in a non-recursive fashion though it doesn't yield any significant improvement on most machines.
The quicksort is the most practical sort function, but there are others such as the heap sort that are better than the quicksort for extremely large (around 107+ (dependent on the machine of course) items. [Edit] There are others that are better for small data sets too. But, for the best overall performance I'd stick with the quicksort.
[edited by - Floppy on June 1, 2002 7:27:00 PM]
>> and merge sort. They are both O(n log n) if the data is "good", and O(n2) if the data is "bad."
No, the worst case of merge sort is O(n log n).
I want to put attention to the radix-sort algorithm (and the related algorithms) since it has a worst case complexity of O(n).
And for a really fast number sorting algorithm check out this article:
http://www.marner.dk/Nilsson.pdf
[edited by - felonius on June 1, 2002 8:09:30 PM]
No, the worst case of merge sort is O(n log n).
I want to put attention to the radix-sort algorithm (and the related algorithms) since it has a worst case complexity of O(n).
And for a really fast number sorting algorithm check out this article:
http://www.marner.dk/Nilsson.pdf
[edited by - felonius on June 1, 2002 8:09:30 PM]
Heap sort isn''t half bad, but the best are merge and quick.
I''d like to point out that although radix sort is linear, if you actually analyze it you''ll see that radix sort will only be faster than O(nlogn) if there are are more elements than there are values. (eg. If you are sorting bytes (value: 0..255) then you need to be sorting more than 256 bytes in order for radix sort to be faster than qsort).
Give a man a fish and you feed him for a day; teach him to use the Net and he won''t bother you for weeks.
Give a man a fish and you feed him for a day; teach him to use the Net and he won''t bother you for weeks.
Topic Locked
This topic has been locked by a moderator. New replies are not allowed.
Sign in to reply to this topic.
Advertisement