Sorting AlgorithmsSorting Algorithms1111111Cpt S 223. School of EECS, WSUSorting methodsComparison based sorting O(n2) methods E g Insertion bubbleE.g., Insertion, bubble Average time O(n log n) methods E.g., quick sortO( l ) h dO(n logn) methods E.g., Merge sort, heap sortNon-comparison based sortingNoncomparison based sorting Integer sorting: linear time E.g., Counting sort, bin sortRdi tb kt t2Radix sort, bucket sortStable vs. non-stable sortingCpt S 223. School of EECS, WSUInsertion sort: snapshot at a given iterationcomparisonsWorst-case run-time complexity: (n2)Btti l it()When?3Best-case run-time complexity:(n)Image courtesy: McQuain WD, VA Tech, 2004When?Cpt S 223. School of EECS, WSUThe Divide and Conquer Technique  Input: A problem of size n Recursive At each level of recursion: (Divide) Split the problem of size n into a fixed number of sub-problems of smaller sizes, and solve each sub-problem recursively (Conquer) Merge the answers to the sub-problems 4gpCpt S 223. School of EECS, WSUTwo Divide & Conquer sorts Merge sortDivide is trivialDivide is trivial Merge (i.e, conquer) does all the work Quick sort Partition (i.e, Divide) does all the work Merge (i.e, conquer) is trivial5Cpt S 223. School of EECS, WSUMain idea:•Dividing is trivialMiiti i lMerge Sort•Merging is non-trivialInput(divide)O(lg n) (divide)(g )stepsHow much work at every step?O(n) sub-problems (conquer)O(lg n) stepsHow much work 6Image courtesy: McQuain WD, VA Tech, 2004at every step?Cpt S 223. School of EECS, WSUHow to merge two sorted arrays?ij8 1423324 9 10 19A1A2ij1. B[k++] =Populate min{ A1[i], A2[j] }2. Advance the minimum contributing pointerTemporary Bgp4891014192332array to holdthe outputk(n) time7Do you always need the temporary array B to store the output, or can you do this inplace?Cpt S 223. School of EECS, WSUMerge Sort : AnalysisMerge Sort takes (n lg n) timeProof: Let T(n) be the time taken to merge sort n elementsTime for each comparison operation=O(1)Main observation: To merge two sorted arrays of size n/2, it takes n comparisons at most.Therefore: T(n) = 2 T(n/2) + n Solving the above recurrence: T(n) = 2 [ 2 T(n/22) + n/2 ] + n= 22T(n/22) + 2n(/)… (k times)= 2kT(n/2k) + kn At k = lg n, T(n/2k) = T(1) = 1 (termination case) ==> T(n) = (n lg n)8Cpt S 223. School of EECS, WSUMain idea:•Dividing (“partitioning”) is non-trivialMiitiilQuickSort•Merging is trivial Divide-and-conquer approach to sorting Like MergeSort, except Don’t divide the array in half Partition the array based elements being less than or greater than some element of the array (the pivot) i.e., divide phase does all the work; merge phase is trivial. Worst case running time O(N2)A i ti O(N l N)Average case running time O(N log N) Fastest generic sorting algorithm in practiceEven faster if use simple sort (e g InsertionSort)9Even faster if use simple sort (e.g., InsertionSort) when array becomes small9Cpt S 223. School of EECS, WSUQuickSort AlgorithmQuickSort( Array: S)1. If size of S is 0 or 1, returnQ) What’s the best way to pick this element? (arbitrary?2. Pivot = Pick an element v in Selement? (arbitrary? Median? etc)1. Partition S – {v} into two disjoint groups S1 = {x  (S – {v}) | x < v}S2 = {x(S–{v}) | x > v}S2 = {x (S {v}) | x > v}2. Return QuickSort(S1), followed by v, followed by QuickSort(S2)10QuickSort(S2)10Cpt S 223. School of EECS, WSUQuickSort Example1111Cpt S 223. School of EECS, WSUQuickSort vs. MergeSort Main problem with quicksort: QuickSort may end up dividing the input array into bbl fi1dN1i th tsubproblems of size 1 and N-1 in the worst case, at every recursive step (unlike merge sort which always divides into two halves) When can this happen? Leading to O(N2) performance =>Need to choose pivot wisely (but efficiently)=>Need to choose pivot wisely (but efficiently) MergeSort is typically implemented using a temporary array (for merge step)12temporary array (for merge step) QuickSort can partition the array “in place”12Cpt S 223. School of EECS, WSUGoal: A “good” pivot is one that creates two even sized partitions=> Median will be best, but finding median ld b t h ti it lfPicking the Pivotcould be as tough as sorting itselfHow about choosing the first element? What if array already or nearly sorted? Good for a randomly populated arrayHow about choosing a random element? Good in practice if “truly random” Still possible to get some bad choices Requires execution of random number generator13Cpt S 223. School of EECS, WSUPicking the Pivot8149035276 Best choice of pivot Median of array8 1 4 9 0 3 5 2 7 61 0 3 2 4 8 9 5 7 6will result in But median is expensive to calculateNext strategy: Approximate the medianEstimatemedian as the median of any three pivotelementsMedian = median {first, middle, last}Has been shown to reduce8 1 4 9 0 3 5 2 7 61 4 0 3 5 2 6 8 9 7will result in14Has been shown to reduce running time (comparisons) by 14%14Cpt S 223. School of EECS, WSUHow to write6 1 4 9 0 3 5 2 7 8How to write the partitioning code?1 4 0 3 5 2 6 9 7 8should result in6 9035 8 Goal of partitioning:  i) Move all elements < pivot to the left of pivotii) Move all elements > pivot to the right of pivotii) Move all elements > pivot to the right of pivot Partitioning is conceptually straightforward, but easy d i ffi i lto do inefficientlyOne bad way:One bad way: Do one pass to figure out how many elements should be on either side of pivotThen create a temp array to copy elements relative to pivot15Then create a temp array to copy elements relative to pivot15Cpt S 223. School of EECS, WSU6 1 4 9 0 3 5 2 7 8Partitioning strategy1 4 0 3 5 2 6 9 7 8should result in6 9035 8 A good strategy to do partition : do it in place// Swap pivot with last element S[right]ilfti = leftj = (right – 1)While (i < j) {OK to also swap with S[left] but then the rest of the code hldh// advance i until first element > pivot// decrement j until first element < pivotshould change accordingly// swap A[i] & A[j] (only if i<j) }This is called“in place” because all operations are done il fthi t16}Swap ( pivot , S[i] )16in place of the inputarray (i.e., withoutcreating temp array)Cpt S 223. School of EECS, WSUPartitioning Strategy An in place partitioning