QuickSort AlgorithmTopics CoveredQuick SortSlide 4Slide 5QuickSort (Hoare 1962)Partition array for QuicksortSlide 8Partition on a sorted listWorst Case Call Tree (N=4)Worst Case IntuitionRecursion Tree for Best CaseAnother Example of O(n lg n) ComparisonsRecursion Tree for Magic pivot function that Partitions a “list” into 1/9 and 8/9 “lists”Intuition for the Average case worst partition followed by the best partitionRecurrence equation:Sorts and extra memoryQuicksort - enhancementsRandomized algorithmsRandomized QuicksortRQuicksort-main procedureRandomized Quicksort AnalysisAverage case time complexitySummary of Worst Case RuntimeSortingGoalDecision TreesFor a particular sorting algorithmSlide 29Exchange SortSlide 31Questions about the Decision Tree For a Correct Sorting Algorithm Based ONLY on Comparison of KeysProposition: Any decision tree that sorts n elements has depth (n lg n ).Proposition: Any Decision Tree that Sorts n Elements has Depth (n lg n ).ImplicationsQuickSort AlgorithmUsing Divide and Conquer for SortingQuickSort 2Topics Covered •QuickSort algorithm–analysis•Randomized Quick Sort•A Lower Bound on Comparison-Based SortingQuickSort 3Quick Sort•Divide and conquer idea: Divide problem into two smaller sorting problems.•Divide:–Select a splitting element (pivot)–Rearrange the array (sequence/list)QuickSort 4Quick Sort•Result: –All elements to the left of pivot are smaller or equal than pivot, and –All elements to the right of pivot are greater or equal than pivot–pivot in correct place in sorted array/list•Need: Clever split procedure (Hoare)QuickSort 5Quick SortDivide: Partition into subarrays (sub-lists)Conquer: Recursively sort 2 subarraysCombine: TrivialQuickSort 6QuickSort (Hoare 1962)Problem: Sort n keys in nondecreasing orderInputs: Positive integer n, array of keys S indexed from 1 to nOutput: The array S containing the keys in nondecreasing order.quicksort ( low, high )1. if high > low 2. then partition(low, high, pivotIndex)3. quicksort(low, pivotIndex -1)4. quicksort(pivotIndex +1, high)QuickSort 7Partition array for Quicksortpartition (low, high, pivot)1. pivotitem = S [low]2. k = low3. for j = low +1 to high4. do if S [ j ] < pivotitem 5. then k = k + 16. exchange S [ j ] and S [ k ] 7. pivot = k8. exchange S[low] and S[pivot]QuickSort 8Input low =1, high = 4pivotitem = S[1]= 55 3 2 6pivotk5 3 6 2k j5 3 6 2j,k5 3 6 2j,k5 3 6 2k j5 3 6 2k j5 3 6 2k j5 3 2 6k jafter line3after line5after line6after loopQuickSort 9Partition on a sorted list3 4 6k j3 4 6after line33 4 6 k jpivotkafter loopHow does partition work for S = 7,5,3,1 ?S= 4,2,3,1,6,7,5QuickSort 10Worst Case Call Tree (N=4)Q(1,4)Left=1, pivotitem = 1, Right =4Q(1,0)Q(2,4)Left =2,pivotItem=3Q(2,1)Q(3,4)pivotItem = 5, Left = 3Q(3,2)Q(4,4)S =[ 1,3,5,7 ]S =[ 3,5,7 ]S =[ 5,7 ]S =[ 7 ]Q(4,3)Q(5,4)QuickSort 11Worst Case Intuitionn-10n-20n-30n-401...00n-1n-2n-3n-410t(n) = k = 1n k = (n+1)n/2Total =QuickSort 12Recursion Tree for Best Casenn/2 n/2n/4 n/4nnnnn/4 n/4n/8..>n/8n/8..>n/8n/8..>n/8n/8..>n/8Sum =(n lgn)Nodes contain problem sizePartition ComparisonsQuickSort 13Another Example of O(n lg n) Comparisons•Assume each application of partition () partitions the list so that (n/9) elements remain on the left side of the pivot and (8n/9) elements remain on the right side of the pivot.•We will show that the longest path of calls to Quicksort is proportional to lgn and not n•The longest path has k+1 calls to Quicksort= 1 + log 9/8 n  1 +  lgn / lg (9/8) = 1 + 6lg n •Let n = 1,000,000. The longest path has 1 + 6lg n = 1 + 620 = 121 << 1,000,000calls to Quicksort.–Note: best case is 1+ lg n = 1 +7 =8QuickSort 14Recursion Tree for Magic pivot function that Partitions a “list” into 1/9 and 8/9 “lists”nn/98n/98n/81 64n/81<nn/81 8n/81256n/729..>..>..>9n/729..>n/7290/10/10/1...(log9 n)(log9/8 n)<n0/1nnnnQuickSort 15Intuition for the Average caseworst partition followed by the best partitionVsnn-11(n-1)/2(n-1)/2n1+(n-1)/2 (n-1)/2This shows a bad split can be “absorbed” by a good split.Therefore we feel running time for the average case is O(n lg n)QuickSort 16Recurrence equation: T(n) = max ( T(q-1) + T(n - q) )+ (n)0 q n-1A(n) = (1/n)  (A(q -1) + A(n - q ) ) + (n)n Worst caseAverage case q = 1QuickSort 17Sorts and extra memory•When a sorting algorithm does not require more than   extra memory we say that the algorithm sorts in-place.•The textbook implementation of Mergesort requires n extra space•The textbook implementation of Heapsort is in-place.•Our implement of Quick-Sort is in-place except for the stack.QuickSort 18Quicksort - enhancements•Choose “good” pivot (random, or mid value between first, last and middle)•When remaining array small use insertion sortQuickSort 19Randomized algorithms•Uses a randomizer (such as a random number generator)•Some of the decisions made in the algorithm are based on the output of the randomizer•The output of a randomized algorithm could change from run to run for the same input•The execution time of the algorithm could also vary from run to run for the same inputQuickSort 20Randomized Quicksort•Choose the pivot randomly (or randomly permute the input array before sorting).•The running time of the algorithm is independent of input ordering.•No specific input elicits worst case behavior.–The worst case depends on the random number generator.•We assume a random number generator Random. A call to Random(a, b) returns a random number between a and b.QuickSort 21RQuicksort-main procedure// S is an instance "array/sequence"// terminate recursionquicksort ( low, high )1. if high > low 2a. then i=random(low, high);2b. swap(S[high], S[I]);2c. partition(low, high, pivotIndex)3. quicksort(low, pivotIndex -1)4. quicksort(pivotIndex +1, high)QuickSort 22Randomized Quicksort Analysis •We assume that all elements are distinct (to make analysis simpler).•We partition around a random element, all partitions from 0:n-1 to n-1:0 are equally likely•Probability of each partition is 1/n.QuickSort 23Average case time complexity )log()()1()1()1()0()()(2)()0()...1()1(...)0(1)())()1((1)(101nnnTTTnkTnnTnTnTTnnknTkTnnTnknkQuickSort