Sorting AlgorithmsQuickSortQuickSort AlgorithmQuickSort ExampleWhy so fast?Picking the PivotPicking the PivotPartitioning StrategyPartitioning ExamplePartitioning Example (cont.)Partitioning StrategyPartitioning StrategySmall ArraysQuickSort ImplementationQuickSort ImplementationSlide Number 16Analysis of QuickSortAnalysis of QuickSortAnalysis of QuickSortComparison SortingComparison SortingLower Bound on SortingDecision TreesSlide Number 24Decision Tree for SortingLower Bound for Comparison SortingLower Bound for Comparison SortingLinear SortingLinear SortingExternal SortingExternal MergeSortExternal MergeSortSorting: Summary111111Sorting AlgorithmsCptS 223 – Advanced Data StructuresLarry HolderSchool of Electrical Engineering and Computer ScienceWashington State UniversityQuickSort 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) Worst case running time O(N2) Average case running time O(N log N) Fastest generic sorting algorithm in practice Even faster if use simple sort (e.g., InsertionSort) when array is small2QuickSort Algorithm Given array S Modify S so elements in increasing order1. If size of S is 0 or 1, return2. Pick any element v in S as the pivot3. Partition S – {v} into two disjoint groups S1 = {x Є (S – {v}) | x ≤ v} S2 = {x Є (S – {v}) | x ≥ v}4. Return QuickSort(S1), followed by v, followed by QuickSort(S2)3QuickSort Example4Why so fast? MergeSort always divides array in half QuickSort might divide array into subproblems of size 1 and N-1 When? Leading to O(N2) performance Need to choose pivot wisely (but efficiently) MergeSort requires temporary array for merge step QuickSort can partition the array in place This more than makes up for bad pivot choices5Picking the Pivot Choosing the first element What if array already or nearly sorted? Good for random array Choose random pivot Good in practice if truly random Still possible to get some bad choices Requires execution of random number generator6Picking the Pivot Best choice of pivot? Median of array Median is expensive to calculate Estimate median as the median of three elements Choose first, middle and last elements E.g., <8, 1, 4, 9, 6, 3, 5, 2, 7, 0> Has been shown to reduce running time (comparisons) by 14%7Partitioning Strategy Partitioning is conceptually straightforward, but easy to do inefficiently Good strategy Swap pivot with last element S[right] Set i = left Set j = (right – 1) While (i < j) Increment i until S[i] > pivot Decrement j until S[j] < pivot If (i < j), then swap S[i] and S[j] Swap pivot and S[i]8Partitioning Example98 1 4 9 6 3 5 2 7 0 Initial array8 1 4 9 0 3 5 2 7 6 Swap pivot; initialize i and jij8 1 4 9 0 3 5 2 7 6 Position i and jij2 1 4 9 0 3 5 8 7 6 After first swapijPartitioning Example (cont.)102 1 4 9 0 3 5 8 7 6 Before second swapij2 1 4 5 0 3 9 8 7 6 After second swapij2 1 4 5 0 3 9 8 7 6 Before third swapj i2 1 4 5 0 3 6 8 7 9 After swap with pivotipPartitioning Strategy How to handle duplicates? Consider the case where all elements are equal Current approach: Skip over elements equal to pivot No swaps (good) But then i = (right – 1) and array partitioned into N-1 and 1 elements Worst case O(N2) performance11Partitioning Strategy How to handle duplicates? Alternative approach Don’t skip elements equal to pivot Increment i while S[i] < pivot Decrement j while S[j] > pivot Adds some unnecessary swaps But results in perfect partitioning for array of identical elements Unlikely for input array, but more likely for recursive calls to QuickSort12Small Arrays When S is small, generating lots of recursive calls on small sub-arrays is expensive General strategy When N < threshold, use a sort more efficient for small arrays (e.g., InsertionSort) Good thresholds range from 5 to 20 Also avoids issue with finding median-of-three pivot for array of size 2 or less Has been shown to reduce running time by 15%13QuickSort Implementation14QuickSort Implementation158 1 4 9 6 3 5 2 7 0L C R6 1 4 9 8 3 5 2 7 0L C R0 1 4 9 8 3 5 2 7 6L C R0 1 4 9 6 3 5 2 7 8L C R0 1 4 9 7 3 5 2 6 8L C P R16Swap should be compiled inline.Analysis of QuickSort Let I be the number of elements sent to the left partition Compute running time T(N) for array of size N T(0) = T(1) = O(1) T(N) = T(i) + T(N – i – 1) + O(N)17Analysis of QuickSort Worst-case analysis Pivot is the smallest element (i = 0)18∑===+−+−+−=+−+−=+−=+−+=+−+=NiNOiONTNONONONTNTNONONTNTNONTNTNONTONTNONTTNT12)()()()()1()2()3()()()1()2()()()1()()()1()1()()()1()0()(Analysis of QuickSort Best-case analysis Pivot is in the middle (i = N/2) Average-case analysis Assuming each partition equally likely T(N) = O(N log N)19)log()()()2/(2)()()2/()2/()(NNONTNONTNTNONTNTNT=+=++=Comparison SortingSort WorstCaseAverageCaseBestCaseCommentsInsertionSort Θ(N2) Θ(N2) Θ(N) Fast forsmall NMergeSort Θ(N log N) Θ(N log N) Θ(N log N) Requires memoryHeapSort Θ(N log N) Θ(N log N) Θ(N log N) Large constantsQuickSort Θ(N2) Θ(N log N) Θ(N log N) Small constants20Comparison Sorting21Good sorting applets• http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html• http://math.hws.edu/TMCM/java/xSortLab/Lower Bound on Sorting Best worst-case sorting algorithm (so far) is O(N log N) Can we do better? Can we prove a lower bound on the sorting problem? Preview For comparison sorting, no, we can’t do better Can show lower bound of Ω(N log N)22Decision Trees A decision tree is a binary tree Each node represents a set of possible orderings of the array elements Each branch represents an outcome of a particular comparison Each leaf of the decision tree represents a particular ordering of the original array elements2324Decision tree for sorting three elementsDecision Tree for Sorting The logic of every sorting algorithm that uses comparisons can be represented by a decision tree In the worst case, the number of comparisons used by the algorithm equals the depth of the deepest leaf In the average case, the number of comparisons is the average of the