SortingReadingSortingSpaceTimeStabilitySlide 7Bubble SortBubblesortPut the largest element in its placePut 2nd largest element in its placeBubble Sort: Just Say NoInsertion SortInsertion SortExampleSlide 16Insertion Sort CharacteristicsHeap SortUsing Binary Heaps for Sorting1 Removal = 1 AdditionRepeated DeleteMaxHeap Sort is In-placeHeapsort: Analysis“Divide and Conquer”MergesortMergesort ExampleAuxiliary ArraySlide 28Slide 29MergingSlide 31Merging AlgorithmRecursive MergesortIterative MergesortSlide 35Slide 36Mergesort AnalysisMergesort Recurrence RelationProperties of MergesortQuicksort“Four easy steps”The steps of QuickSortDetails, detailsQuicksort PartitioningPartitioning:Choosing the pivotPartitioning in-placeSlide 47Slide 48Slide 49Recursive QuicksortQuicksort Best Case PerformanceQuicksort Worst Case PerformanceProperties of QuicksortFolkloreSorting CSE 373Data StructuresLecture 1912/26/03 Sorting - Lecture 19 2Reading•Reading ›Sections 7.1-7.3 and 7.5›Section 7.6, Mergesort›Section 7.7, Quicksort12/26/03 Sorting - Lecture 19 3Sorting•Input›an array A of data records (Note: we have seen how to sort when elements are in linked lists: Mergesort)›a key value in each data record›a comparison function which imposes a consistent ordering on the keys (e.g., integers)•Output›reorganize the elements of A such that•For any i and j, if i < j then A[i]  A[j]12/26/03 Sorting - Lecture 19 4Space•How much space does the sorting algorithm require in order to sort the collection of items?›Is copying needed? O(n) additional space›In-place sorting – no copying – O(1) additional space›Somewhere in between for “temporary”, e.g. O(logn) space›External memory sorting – data so large that does not fit in memory12/26/03 Sorting - Lecture 19 5Time•How fast is the algorithm?›The definition of a sorted array A says that for any i<j, A[i] < A[j]›This means that you need to at least check on each element at the very minimum, I.e., at least O(N)›And you could end up checking each element against every other element, which is O(N2)›The big question is: How close to O(N) can you get?12/26/03 Sorting - Lecture 19 6Stability•Stability: Does it rearrange the order of input data records which have the same key value (duplicates)? ›E.g. Phone book sorted by name. Now sort by county – is the list still sorted by name within each county?›Extremely important property for databases ›A stable sorting algorithm is one which does not rearrange the order of duplicate keysn2n·log2nnlog2nFaster is better!12/26/03 Sorting - Lecture 19 8Bubble Sort•“Bubble” elements to to their proper place in the array by comparing elements i and i+1, and swapping if A[i] > A[i+1]›Bubble every element towards its correct position•last position has the largest element•then bubble every element except the last one towards its correct position•then repeat until done or until the end of the quarter, whichever comes first ...12/26/03 Sorting - Lecture 19 9Bubblesortbubble(A[1..n]: integer array, n : integer): { i, j : integer; for i = 1 to n-1 do for j = 2 to n–i+1 do if A[j-1] > A[j] then SWAP(A[j-1],A[j]); }SWAP(a,b) : { t :integer;6 t:=a; a:=b; b:=t; }65327112345656327153627112/26/03 Sorting - Lecture 19 10Put the largest element in its place1 2 3 8 7 9 10 12 23 18 15 16 17 142 3larger value?8 87 8swap1 2 3 7 8 9 10 12 23 18 15 16 17 149 10 12 2318 23swap2315 16 17 1418 15swap23 16 17 1418 15swap16 23 17 1418 15swap16 17 23 1418 15swap16 17 14 231 2 3 7 8 9 10 121 2 3 7 8 9 10 121 2 3 7 8 9 10 121 2 3 7 8 9 10 121 2 3 7 8 9 10 129 10 12 23 18 15 16 17 141 2 312/26/03 Sorting - Lecture 19 11Put 2nd largest element in its place1 2 3 7 8 9 10 122 3larger value?7 87 8swap1 2 3 7 8 9 10 121 2 3 7 8 9 10 121 2 3 7 8 9 10 129 10 121 2 318 15 16 17 14 2315 18 16 17 14 239 10 12 18 18swap15 16 18 17 14 23swap15 16 17 18 14 23swap15 16 17 14 18 23Two elements done, only n-2 more to go ...12/26/03 Sorting - Lecture 19 12Bubble Sort: Just Say No•“Bubble” elements to to their proper place in the array by comparing elements i and i+1, and swapping if A[i] > A[i+1]•We bubblize for i=1 to n (i.e, n times)•Each bubblization is a loop that makes n-i comparisons•This is O(n2)12/26/03 Sorting - Lecture 19 13Insertion Sort •What if first k elements of array are already sorted?›4, 7, 12, 5, 19, 16•We can shift the tail of the sorted elements list down and then insert next element into proper position and we get k+1 sorted elements›4, 5, 7, 12, 19, 1612/26/03 Sorting - Lecture 19 14Insertion SortInsertionSort(A[1..N]: integer array, N: integer) { i, j, temp: integer ;for i = 2 to N { temp := A[i]; j := i; while j > 1 and A[j-1] > temp { A[j] := A[j-1]; j := j–1;} A[j] = temp; } }•Is Insertion sort in place? •Running time = ?2 1 41 2 3ij12/26/03 Sorting - Lecture 19 15Example1 2 3 8 7 9 10 12 23 18 15 16 17 141 2 3 7 8 9 10 12 23 18 15 16 17 1418 23 15 16 17 1418 15 23 16 17 1415 18 23 16 17 1415 18 16 23 17 141 2 3 7 8 9 10 121 2 3 7 8 9 10 121 2 3 7 8 9 10 121 2 3 7 8 9 10 1215 16 18 23 17 141 2 3 7 8 9 10 1212/26/03 Sorting - Lecture 19 16Example15 16 18 17 23 141 2 3 7 8 9 10 1215 16 17 18 23 141 2 3 7 8 9 10 1215 16 17 18 14 231 2 3 7 8 9 10 1215 16 17 14 18 231 2 3 7 8 9 10 1215 16 14 17 18 231 2 3 7 8 9 10 1215 14 16 17 18 231 2 3 7 8 9 10 1214 15 16 17 18 231 2 3 7 8 9 10 1212/26/03 Sorting - Lecture 19 17Insertion Sort Characteristics•In place and Stable•Running time›Worst case is O(N2)•reverse order input•must copy every element every time•Good sorting algorithm for almost sorted data›Each item is close to where it belongs in sorted order.12/26/03 Sorting - Lecture 19 18Heap Sort•We use a Max-Heap•Root node = A[1]•Children of A[i] = A[2i], A[2i+1]•Keep track of current size N (number of nodes)N = 5valueindex765427 5 6 2 4 1 2 3 4 5 6 7 812/26/03 Sorting - Lecture 19 19Using Binary Heaps for Sorting•Build a max-heap•Do N DeleteMax operations and store each Max element as it comes out of the heap•Data comes out in largest to smallest order•Where can we put the elements as they are removed from the heap?BuildMax-heapDeleteMax765426457212/26/03 Sorting - Lecture 19 201 Removal = 1 Addition•Every time we do a DeleteMax, the heap gets smaller by one node, and we have one more node to store›Store the data at the end of the heap array›Not "in the