Bubble Sort -------------- Bubble sort is the simplest of the sort methods, and runs in O(n2) time. It can be accomplished with a remarkably small amount of memory, but it is also probably the least efficient sort that we looked at. The basic idea is to look at each pair of nodes in turn, and swap them if they are out of order. You do this comparison n times, if there are n elements in the list. So, starting with 7 5 1 9 0 2 4 6 3 iteration one would first swap 7 and 5, then 7 and 1, then 9 and 0, then 9 and 2, then 9 and 4, then 9 and 6, then 9 and 3, resulting in 5 1 7 0 2 4 6 3 9 Iteration two would swap 5 and 1, 0 and 7, 2 and 7, 4 and 7, 6 and 7, 3 and 7, resulting in 1 5 0 2 4 6 3 7 9 And further interations would produce 1 0 2 4 5 3 6 7 9 0 1 2 4 3 5 6 7 9 0 1 2 3 4 5 6 7 9 Selection Sort ----------------- The idea behind selection sort is to look through the list for the smallest item, and put it in front. Then look for the next smallest, and put it second, then for the third smallest, and put it third, and so on, up to the nth smallest (which is the largest). This also takes O(n2) to run. Given the same example as above 7 5 1 9 0 2 4 6 3 Iteration one will find 0, and put it in first place, swapping with the value already there. 0 5 1 9 7 2 4 6 3 And successive iterations will produce 0 1 5 9 7 2 4 6 3 0 1 2 9 7 5 4 6 3 0 1 2 3 7 5 4 6 9 0 1 2 3 4 5 7 6 9 0 1 2 3 4 5 7 6 9 -- note, 5 swaps with itself, since it is the next smallest 0 1 2 3 4 5 6 7 9 Insertion Sort ----------------- The idea behind insertion sort is to take the unsorted elements one at a time in sequence, and insert them into their appropriate spot in the list. This alos takes O(n2) to run. Given the same example as above 7 5 1 9 0 2 4 6 3 Iteration one is not very exciting, because the first element will always be in the right place, since there is no sorted list yet. The second iteration will take 5, and insert it into the correct place, or 5 7 1 9 0 2 4 6 3 The third will take 1 and insert it into the correct place, or 1 5 7 9 0 2 4 6 3 Then subsequent iterations will produce 1 5 7 9 0 2 4 6 3 0 1 5 7 9 2 4 6 3 0 1 2 5 7 9 4 6 3 0 1 2 4 5 7 9 6 3 0 1 2 4 5 6 7 9 3 0 1 2 3 4 5 6 7 9 One thing to remember about insertion sort is that it works faster the closer the list is to already being sorted. Shell Sort ------------ Shell sort is a modified insertion sort that doesn't seem like it should improve the running time of insertion sort all that much, but in practice, it does. It still takes O(n2) to run, but in practice it never actually takes that long, and compares favorably with many of the nLogn sorts. The idea behind shell sort is to start by sorting regularly spaced sub-arrays before sorting the whole list with insertion sort. Thus, when the insertion sort is done, the list will be overall "more sorted" than it was before the subsorts. We start with a spacing of n/2, and halve the spacing each time, doing an insertion sort on the subarrays, until the spacing reduces to 1, at which point it becomes a regular insertion sort. Given the same example as above 7 5 1 9 0 2 4 6 3 We will start with a spacing of 9/2, or 4. This will produce the subarrays 7 0 3 5 2 1 4 9 6 And, sorting those subarrays, we get 0 2 1 6 3 5 4 9 7 Now, we move to a spacing of 4/2, or 2. This will produce the subarrays 0 1 3 4 7 2 6 5 9 And, sorting these subarrays, we get 0 2 1 5 3 6 4 9 7 Now, we move to a spacing of 2/2 or 1, which is the full insertion sort. Note that the array is much closer to being sorted, however. Ignoring the moves where the next element is already in it's correct place, we sort to the finish with 0 1 2 5 3 6 4 7 9 0 1 2 3 5 6 4 7 9 0 1 2 3 4 5 6 7 9 Merge Sort ------------ Merge sort is the first recursive sort that we examine, and also the first one that runs in less than n2 time. In fact, it runs in O(nlogn) time. The sort is accomplished by breaking the array into two halves, sorting the halves, and merging them back together. Done recursively, this produces a sorted array. This is a very fast sort in practice, but it has the disadvantage of requiring extra memory for a temporary array to "merge" the sorted halves back into. Given the same example as above 7 5 1 9 0 2 4 6 3 We will split the array into two halves 7 5 1 9 and 0 2 4 6 3 and sort those halves with merge sort, splitting them further into 7 5 and 1 9 and 0 2 and 4 6 3 And split these again, into 7 and 5, 1 and 9, 0 and 2, 4 and 6 3 Only one is left that needs to be split, which is 6 3. We will split that one, and merge the now sorted (since one element is always sorted) results back into a new temporary array, leading to 7 and 5, 1 and 9, 0 and 2, 4 and 3 6 Now we merge the next level up, which will be all of the pairs, resulting in 5 7 and 1 9 and 0 2 and 3 4 6 Now we merge the next level, which will result in 1 5 7 9 and 0 2 3 4 6 then the final level, for 0 1 2 3 4 5 6 7 9 Quick Sort ------------ Quick sort is also a recursive sort, whose basic algorithm is to 1. pick a pivot point in the array. 2. put all values less than that point before it, and all values greater than that after it 3. quick sort the smaller values, then the larger values. This is also an O(nlogn) sort, but a great deal of difference is made in the run time depending on the pivot that you pick. You want to find one that is the median value for the list, so that it is split into even halves. This will limit the depth of the recursion necessary. Given the same example as above 7 5 1 9 0 2 4 6 3 we will simplistically pick the midpoint (0) for the pivot. We put all values less to the left, and all values greater to the right. That leaves us with 0 7 5 1 9 2 4 6 3 which is a bad split. There is no left half to recursively sort, so lets do the right half. Again, pick the midpoint for the split, which is 9. Partition the array. This leaves us with 0 7 5 1 2 4 6 3 9 again, a bad split, for the opposite reason. Now we only have a left half to recurse on. again picking the center as the pivot, we grab 2. We partition, leaving 0 1 2 7 5 4 6 3 9 This time we have two sides, but the left is trivial. Recursing on the right, we get a pivot of 4. We partition for 0 1 2 3 4 7 5 6 9 again, a trivial split to the left. Recursing to the right one more time, we get a pivot of 5, do the partition, and get 0 1 2 3 4 5 76 9 No left split, leaving only 76 to recurse on. There aren't enough values left to partiton, so we just sort the two left, giving us 0 1 2 3 4 5 67 9 and that will end the recursion, and give us our sorted list. Radix Sort ----------- A good example of this is shown in the book Heap Sort ----------- Again, look in the book. Heaps are hard to draw in a text file.