Introduction to Algorithms6.046J/18.401JQuicksortDivide and conquerPartitioning subroutineExample of partitioningExample of partitioningExample of partitioningExample of partitioningExample of partitioningExample of partitioningExample of partitioningExample of partitioningExample of partitioningExample of partitioningExample of partitioningExample of partitioningPseudocode for quicksortAnalysis of quicksortWorst-case of quicksortWorst-case recursion treeWorst-case recursion treeWorst-case recursion treeWorst-case recursion treeWorst-case recursion treeWorst-case recursion treeWorst-case recursion treeBest-case analysisAnalysis of “almost-best” caseAnalysis of “almost-best” caseAnalysis of “almost-best” caseAnalysis of “almost-best” caseAnalysis of “almost-best” caseMore intuitionRandomized quicksortRandomized quicksort analysisAnalysis (continued)Calculating expectationCalculating expectationCalculating expectationCalculating expectationCalculating expectationHairy recurrenceSubstitution methodSubstitution methodSubstitution methodSubstitution methodQuicksort in practiceSeptember 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.1Introduction to Algorithms6.046J/18.401JLECTURE 4Quicksort• Divide and conquer• Partitioning• Worst-case analysis• Intuition • Randomized quicksort• AnalysisProf. Charles E. LeisersonSeptember 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.2Quicksort• Proposed by C.A.R. Hoare in 1962.• Divide-and-conquer algorithm.• Sorts “in place” (like insertion sort, but not like merge sort).• Very practical (with tuning).September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.3Divide and conquerQuicksort an n-element array:1. Divide: Partition the array into two subarrays around a pivot x such that elements in lower subarray ≤ x ≤ elements in upper subarray.2. Conquer: Recursively sort the two subarrays.3. Combine: Trivial.≤ x≤ xxx≥ x≥ xKey: Linear-time partitioning subroutine.September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.4Partitioning subroutineRunning time= O(n) for nelements.Running time= O(n) for nelements.PARTITION(A, p, q) ⊳ A[p . . q] x ← A[p] ⊳ pivot = A[ p]i ← pfor j ← p + 1 to qdo if A[ j] ≤ xthen i ← i + 1exchange A[i] ↔ A[ j]exchange A[p] ↔ A[i]return iInvariant:xx≤ x≤ x≥ x≥ x??qjpiSeptember 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.5Example of partitioningij6610101313558833221111September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.6Example of partitioningij6610101313558833221111September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.7Example of partitioningij6610101313558833221111September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.8Example of partitioning661010131355883322111166ij55131310108833221111September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.9Example of partitioning661010131355883322111166ij55131310108833221111September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.10Example of partitioning661010131355883322111166ij55131310108833221111September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.11Example of partitioning661010131355883322111166551313101088332211116655ij331010881313221111September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.12Example of partitioning661010131355883322111166551313101088332211116655ij331010881313221111September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.13Example of partitioning661010131355883322111166551313101088332211116655331010881313221111665533ij2288131310101111September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.14Example of partitioning661010131355883322111166551313101088332211116655331010881313221111665533ij2288131310101111September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.15Example of partitioning661010131355883322111166551313101088332211116655331010881313221111665533ij2288131310101111September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.16Example of partitioning6610101313558833221111665513131010883322111166553310108813132211116655332288131310101111225533i6688131310101111September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.17Pseudocode for quicksortQUICKSORT(A, p, r)if p < rthen q ← PARTITION(A, p, r)QUICKSORT(A, p, q–1)QUICKSORT(A, q+1, r)Initial call: QUICKSORT(A, 1, n)September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.18Analysis of quicksort• Assume all input elements are distinct.• In practice, there are better partitioning algorithms for when duplicate input elements may exist.• Let T(n) = worst-case running time on an array of n elements.September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.19Worst-case of quicksort• Input sorted or reverse sorted.• Partition around min or max element.• One side of partition always has no elements.)()()1()()1()1()()1()0()(2nnnTnnTnnTTnTΘ=Θ+−=Θ+−+Θ=Θ+−+=(arithmetic series)September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.20Worst-case recursion treeT(n) = T(0) + T(n–1) + cnSeptember 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.21Worst-case recursion treeT(n) = T(0) + T(n–1) + cnT )(nSeptember 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.22Worst-case recursion treeT(n) = T(0) + T(n–1) + cncnT(0) T(n–1)September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.23Worst-case recursion treeT(n) = T(0) + T(n–1) + cncnT(0) c(n–1)T(0) T(n–2)September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.24Worst-case recursion treeT(n) = T(0) + T(n–1) + cncnT(0) c(n–1)T(0) c(n–2)T(0)Θ(1)OSeptember 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.25Worst-case recursion treecnT(0) c(n–1)T(n) = T(0) + T(n–1) + cnT(0) c(n–2)T(0)Θ(1)O()21nknkΘ=⎟⎟⎠⎞⎜⎜⎝⎛Θ∑=September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.26Worst-case