Menu
Our algorithm professor gave us a assignment that requires us to choose a rare sorting algorithm (e.g. Introsort, Gnomesort, etc.) and do some research about it. Wikipedia sure has a plenty of information about this, but it is still not enough for me to do the research in depth. So I would like to find a book that include discussions of those rare sorting algorithms, since most of the textbooks (like CLRS, the one I am using) only discuss about some basic sorting algorithms (e.g. Bubble Sort, Merge Sort, Insertion Sort.). Is there a book or website that contains a good amount of those information? Thanks!
488
Definition of Bogosort. The universally-acclaimed worst sorting algorithm is Bogosort, sometimes called Monkey Sort or Random Sort, for reasons we'll see shortly. Bogosort develops from the idea that, in probability theory, if a certain phenomenon is possible, then it will eventually happen.
Quicksort. Quicksort is one of the most efficient sorting algorithms, and this makes of it one of the most used as well. The first thing to do is to select a pivot number, this number will separate the data, on its left are the numbers smaller than it and the greater numbers on the right.
Analysis of sorting techniques : When order of input is not known, merge sort is preferred as it has worst case time complexity of nlogn and it is stable as well.
The heapsort algorithm involves preparing the list by first turning it into a max heap. The algorithm then repeatedly swaps the first value of the list with the last value, decreasing the range of values considered in the heap operation by one, and sifting the new first value into its position in the heap.
Well, a very interesting "rare" sorting algorithm in Smoothsort by Edsger Dijkstra. On paper it is almost a perfect sort:
O(n) best
O(n log n) average
O(n log n) worst
O(1) memory
n comparisons, 0 swaps when input is sorted
It is so rare due to it's complex nature (which makes it hard to optimize).
You can read the paper written by Dijkstra himself here: http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF
And here is the wikipedia link and a very extensive article about smoothsort (by Keith Schwarz).
63
One of a sorting which may be you say Rare Sorting, is timsorting, It works great in arrays which are have sorted parts, best case is O(n), and worst and average case is O(n log n).
Another fast way of sorting is bitonic sorting, which is base of nearly all parallel sorting algorithms. you can find thousands of papers about in the web, also some books like Parallel algorithm of Quinn you can find extended discussion on it, and related variations of this algorithm.
Also Art of computer programming volume 3 has good discussion on sorting strategies.
23
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
