Question:
Sorting - standard algorithms!?
MartinObviously
2009-06-11 10:17:37 UTC
I have a big list to sort in VB, which is the fastest method or the best?
•Bubble sort
•Selection sort
•Insertion sort
•Quick sort
•Merge sort
•Heap sort
•Preliminary Results
•BubbleExit Sort
•Comb Sort
•Shell Sort
•Shaker Sort
•Radix Sort
•Results
•Project Files
•Visual Sorting

I had a look and Radix seems to be the fastest. I just want to know what type is the best =D any help cheers. the big list i am sorting is String and is to be A to Z style
Three answers:
Lie Ryan
2009-06-11 10:44:05 UTC
There are no fastest sort method.



For a specific sample of data, one type of sorting will always be faster than the other.



Generally though, Bubble sort is only good for small number of data that is almost nearly sorted. Its advantage is its working is simple to describe and understand, and is often taught to Algorithm 101.



Quicksort is considered one of the fastest sorting algorithms, having an O(n log(n)) performance; however it has a worst case scenario of O(n^2), on certain type of initial arrangements could make it run very slow.



Heap sort is also considered as one of the fastest sorting algorithm and it has no worst case scenario. However, it has large overhead, making QuickSort sometimes faster.



Radix/bucket sort is lexicographic sort, avoiding the O(n log(n)) speed limit of comparison-based sort (such as Quicksort). However, due to not being a comparison sort, it is not capable of sorting certain sorts of data (pun not intended). Radix sort also have relatively high overhead.



In general though, you should just use the built-in sorting library in whatever programming language you uses. Most of the time, writing a your own sorting function is just not worth the slight speed gain; and often half-baked sorting function would just be slower than the generic built-in one. Using built-in sort is also more bug-proof.



In general, the fastest sorting algorithm would be one that mixes several algorithms together. Quicksort and Radix sort are fast for sorting large amount of data, but they are recursive sorting, and as the part/bucket gets smaller other sorting methods that have lower overhead is often used.



Also, sometimes your problem really is not algorithm. Sometimes it is much easier, faster, and better to use the correct data structure for the problem. With the correct data structure (such as sorted binary tree), sorting often becomes unnecessary.
2009-06-11 10:27:13 UTC
Bubble sort is definitely NOT the fastest. It runs in O(n^2) time. Radix is the fastest, but I believe it only works in certain scenarios and has some drawbacks (I believe it runs in O(n) time). Quick-sort is the fastest overall for any scenario (runs in O(nlog(n))) Merge sort works the same way as Quick-sort, so it's just as fast, but it eats up a lot more memory and memory allocation and deallocation slows it down.



Of course, I'm not 100% familiar with all these sorting methods, but whatever.
kevinyipeio
2009-06-11 10:20:54 UTC
Bubble sort is the fastest of course...

Bubbles are cool.


This content was originally posted on Y! Answers, a Q&A website that shut down in 2021.
Loading...