04/09/1411:16:24 130 CS 61B: Lecture 30 Wednesday, April 9, 2014SORTING=======The need to sort numbers, strings, and other records arises frequently. Theentries in any modern phone book were sorted by a computer. Databases havefeatures that sort the records returned by a query, ordered according to anyfield the user desires. Google sorts your query results by their "relevance".We’ve seen that Kruskal’s algorithm uses sorting. So do hundreds of otheralgorithms.Sorting is perhaps the simplest fundamental problem that offers a huge varietyof algorithms, each with its own inherent advantages and disadvantages. We’llstudy and compare eight sorting algorithms.Insertion Sort--------------Insertion sort is very simple and runs in O(n^2) time. We employ a list S, andmaintain the invariant that S is sorted. Start with an empty list S and the unsorted list I of n input items. for (each item x in I) { insert x into the list S, positioned so that S remains in sorted order. }S may be an array or a linked list. If S is a linked list, then it takesTheta(n) worst-case time to find the right position to insert each item. If Sis an array, we can find the right position in O(log n) time by binary search,but it takes Theta(n) worst-case time to shift the larger items over to makeroom for the new item. In either case, insertion sort runs in Theta(n^2)worst-case time--but for a different reason in each case.If S is an array, one of the nice things about insertion sort is that it’s anin-place sort. An _in-place_sort_ is a sorting algorithm that keeps the sorteditems in the same array that initially held the input items. Besides the inputarray, it uses only O(1) or perhaps O(log n) additional memory.To do an in-place insertion sort, we partition the array into two pieces: theleft portion (initially empty) holds S, and the right portion holds I. Witheach iteration, the dividing line between S and I moves one step to the right. ---------- ---------- ---------- ---------- ---------- ][7|3|9|5| => |7][3|9|5| => |3|7][9|5| => |3|7|9][5| => |3|5|7|9][ ---------- ---------- ---------- ---------- ---------- \_____/ S \___/ \_/ \_/ \___/ I \_____/ I I S I S SIf the input list I is "almost" sorted, insertion sort can be as fast asTheta(n)--if the algorithm starts its search from the _end_ of S. In thiscase, the running time is proportional to n plus the number of _inversions_.An inversion is a pair of keys j < k such that j appears after k in I.I could have anywhere from zero to n (n - 1) / 2 inversions.If S is a balanced search tree (like a 2-3-4 tree or splay tree), then therunning time is in O(n log n); but that’s not what computer scientists meanwhen they discuss "insertion sort." This is our first O(n log n) sortingalgorithm, but we’ll pass it by for others that use less memory and havesmaller constants hidden in the asymptotic running time bounds.Selection Sort--------------Selection sort is equally simple, and also runs in quadratic time. Again weemploy a list S, and maintain the invariant that S is sorted. Now, however, wewalk through I and pick out the smallest item, which we append to the end of S. Start with an empty list S and the unsorted list I of n input items. for (i = 0; i < n; i++) { Let x be the item in I having smallest key. Remove x from I. Append x to the end of S. }Whether S is an array or linked list, finding the smallest item takes Theta(n)time, so selection sort takes Theta(n^2) time, even in the best case! Hence,it’s even worse than insertion sort.If S is an array, we can do an in-place selection sort. After finding theitem in I having smallest key, swap it with the first item in I, as shown here. ---------- ---------- ---------- ---------- ---------- ][7|3|9|5| => |3][7|9|5| => |3|5][9|7| => |3|5|7][9| => |3|5|7|9][ ---------- ---------- ---------- ---------- ---------- \_____/ S \___/ \_/ \_/ \___/ I \_____/ I I S I S SIf I is a data structure faster than an array, we call it...04/09/1411:16:24 230Heapsort--------Heapsort is a selection sort in which I is a heap. Start with an empty list S and an unsorted list I of n input items. toss all the items in I onto a heap h (ignoring the heap-order property). h.bottomUpHeap(); // Enforces the heap-order property for (i = 0; i < n; i++) { x = h.removeMin(); Append x to the end of S. }bottomUpHeap() runs in linear time, and each removeMin() takes O(log n) time.Hence, heapsort is an O(n log n)-time sorting algorithm.There are several ways to do heapsort in place; I’ll describe just one.Maintain the heap _backward_ at the _end_ of the array. This makes theindexing a little more complicated, but not substantially so. As items areremoved from the heap, the heap shrinks toward the end of the array, makingroom to add items to the end of S. bottomUpHeap() removeMin() removeMin() removeMin() removeMin() 5 3 5 7 9 / \ / \ / \ / 9 3 => 7 5 => 7 9 => 9 => => empty / /7 9--------- ---------- ---------- ---------- ---------- ----------|7|3|9|5| => ][9|5|7|3| => |3][9|7|5| => |3|5][9|7| => |3|5|7][9| => |3|5|7|9][--------- ---------- ---------- ---------- ---------- ---------- \_____/ \_____/ S \___/ \_/ \_/ \___/ I \_____/ I I I S I S SHeapsort is excellent for sorting arrays, but it is an awkward choice forlinked lists. The easiest way to heapsort a linked list is to create a newarray of n references to the listnodes. Sort the array of references (usingthe keys in the listnodes for comparisons). When the array is sorted, link allthe listnodes together into a sorted list.The array of references uses extra memory. There is another O(n log n)algorithm that can sort linked lists using very little additional memory.Mergesort---------Mergesort is based on the observation that it’s possible to merge two sortedlists into one sorted list in linear time. In fact, we can do it with queues: Let Q1 and Q2 be two
View Full Document
Unlocking...