#### Archived

This topic is now archived and is closed to further replies.

# Sorting Algorithms

This topic is 5986 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Of all the sorting algorithms (eg. Bubble Sort, Shell Sort, etc.), which one is the fastest? Thanx!

##### Share on other sites
Quicksort and possibly mergesort

##### Share on other sites
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.

##### Share on other sites
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.  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]

##### Share on other sites
>> 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]

##### Share on other sites
Heap sort isn''t half bad, but the best are merge and quick.

##### Share on other sites
Those (Quick, Merge, Shell, etc) algorithms belong to the past...
Dont you remember that now we have BS Sort, that is probably something like O(1)? Ha...

Cya,
-RoTTer

##### Share on other sites
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.

##### Share on other sites
Insertion sort is fast for data that''s almost in order already. Some people implement Quicksort so that after the chunks are small enough (like, less than 4 elements), it sorts the array with insertion sort.

Of the simple algorithms, bubble sort is something everyone should avoid though.

1. 1
Rutin
44
2. 2
3. 3
4. 4
5. 5

• 11
• 9
• 12
• 10
• 13
• ### Forum Statistics

• Total Topics
632984
• Total Posts
3009712
• ### Who's Online (See full list)

There are no registered users currently online

×