|
I have already studied bubblesort, insertion sort and selection sort and can implement them in C pretty much from knowledge of the algorithm. I want to go on to learn shellsort, merge sort, heapsort and quicksort, which I guess are a lot harder to understand. What order should I take these other sort algos? I am assuming a simpler sort algo helps learn a more complex one. Don't mind taking on some others if it helps the learning process. |
|||||||||||||||||||
|
|
Learn mergesort and quicksort first: they are both fairly simple, high-performance, and frequently used. Next, look at heapsort. It is more complicated than mergesort and quicksort, but it is also high-performance and frequently used; also, heapsort is based on a priority queue, which is sometimes a more appropriate solution than sorting an entire array at once. The above three sorts have O(N log N) asymptotic performance; most practical sorting implementations are based on them. Shellsort isn't very complicated to implement, but it doesn't really have much to recommend it, either: the algorithms mentioned above perform better, and it is not used much, so I would leave it until later. For breadth, I would also recommend learning bitonic sort, which aside from being asymptotically slower at O(N (log N)^2) is both complicated and harder to understand -- but it has the advantage of being parallellizable, in ways that many other sorts aren't. If you want to use a GPU to sort things, you should look into bitonic sort. Finally, radix sort is a bit different: it is not a general comparison sort, which is why it can have an asymptotic speed of O(k N) (for keys of fixed size k). Although IMHO it has sometimes been oversold, radix sort can be made quite fast, and is occasionally used in practice; it is relatively simple, and worth understanding for its own sake. |
||||
|
|
|
It never ceases to amaze me how many different sorts there are. I'd definitely recommend you checking out sleep sort. It's pretty wonderful... I just saw it today and it completely blew my mind. |
|||||
|
|
Coursera's Algorithms, Part 1 covers topics roughly in the following order: union-find, binary search, stacks, queues, bags, insertion sort, selection sort, shellsort, quicksort, 3-way quicksort, mergesort, heapsort, binary heaps, binary search trees, red-black trees, separate chaining and linear probing hash tables, Graham scan, and kd-trees. Coursera's Algorithms, Part 2 focuses on graph and string-processing algorithms. Topics include depth-first search, breadth-first search, topological sort, Kosaraju-Sharir, Kruskal, Prim, Dijkistra, Bellman-Ford, Ford-Fulkerson, LSD radix sort, MSD radix sort, 3-way radix quicksort, multiway tries, ternary search tries, Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp, regular expression matching, run-length coding, Huffman coding, LZW compression, and the Burrows-Wheeler transform. |
|||
|
|
|
Although higher level languages like .NET and Java already come with implemented sort algorithms , it is always better to know the stuff behind the scenes that you are using . These algorithms also teaches some nifty programming techniques that you can apply in your programming . QuickSort is kind of the most important of these sort algorithms as it achieves a O(n log n) time on average and the constants hiding behind the scenes are pretty good and it sorts in place. Heap Sort too has O(n log n) time in the worst case . Merge Sort also is O(n log n) time in the worst case but it doesn't sort in place . It also gives a good foundation for divide and conquer algorithms . Both randomized QuickSort and HeapSort use divide and Conquer paradigm . Heap Sort uses that indirectly through a procedure called Max-HEapify and quick Sort uses divide and conquer directly . So definitely you should learn MergeSort first and then you can learn Quick Sort and then the Heap Sort . Learning about heap sort also has the added advantage of learning a the heap datastructure . After these you may want to look at some sort algorithms that achieves O(n) in the worst case like Count Sort , radix sort and bucket sort . |
|||
|
|
|
Most programmers only ever learn these algorithms so that they know that they don't need to implement them. If you're using a well-tested platform such as .NET, Java, Python, etc., it's pretty much insane to write your own sorts. So choose the order that will teach you the most about algorithms, and then make sure you don't ever put it into practice. |
|||||||||
|
|
Skip shellsort and heapsort. I'd probably skip merge sort. You NEED to understand quicksort. Look for an explanation that presents a recursive algorithm first, as it will be much easier to grasp what is going on (pick a pivot element, partition into three sets (elements less than pivot, elements equal to pivot, elements greater than pivot), quicksort elements less than pivot, quicksort elements greater than pivot). Then you can read the almost-incomprehensible iterative-with-explicit-stack versions. |
|||||
|
