7. Quicksort

Contents Quicksort Randomized quicksort 섹션 7.1에서 퀵소트알고리즘이 무언인지, 그리고 특징으로 어떤것이 있는지 알아보겠습니다. 7.2에서는 퀵소트의 퍼포먼스를 워스트 베스트 에버러지의 각경우에 어떤지 살펴보고 7.3에서 퀵소트의 알고리즘의 변형으로 피봇값을 미리정해두는 것이 아니라 램덤하게 선택함으로서 퍼포먼스가 좋아진다는 것을 설명하고 있습니다. 그리고 7.4는 섹션 7.2보다 퀵소트의 퍼포먼스 분석을 좀더 자세하게 설명하고 있습니다..

Quicksort Divide-and-Conquer paradigm QUICKSORT(A, p, r) if p < r then q ← PARTITION(A, p, r) QUICKSORT(A, p, q - 1) QUICKSORT(A, q + 1, r)

Quicksort Partition Pivot element 2 8 7 1 3 5 6 4 2 1 3 4 7 5 6 8

Quicksort 4 6 5 3 1 7 8 2 4 6 5 3 8 7 1 2 4 6 5 7 8 3 1 2 4 6 5 3 1 7 8 2 4 6 5 7 8 3 1 2 4 6 5 3 1 7 8 2 4 6 5 7 8 3 1 2 4 6 5 3 1 7 8 2 8 6 5 7 4 3 1 2

Quicksort Partition Θ(n) time. Balanced partitioning vs. unbalanced partitioning

Performance of quicksort Balanced partitioning When PARTITION produces two subproblems of sizes ⌊n/2⌋ and ⌈n/2⌉- 1. T (n) ≤ 2T (n/2) + Θ(n) = O(nlgn)

Performance of quicksort Balanced partitioning n n n n/2 n/2 lg n n n/4 n/4 n/4 n/4 n 1 1 1 1

Performance of quicksort Unbalanced partitioning n 1 n-1 n-2 1 1 n-3 n-4 1

Performance of quicksort Unbalanced partitioning T(n-1)=t(n-2)+t(n-1) T(n-2)=t(n-3)+t(n-2) t(n) = t(n-2) + t(n-3) + t(n-1) + t(n) 그리고 t(n)=세타 n 그래서 시그마 세타 k 이다

Worst-case Analysis Worst-case analysis Quicksort takes Ω(n2) time in worst case. Consider the unbalanced partitioning. Is the unbalanced partitioning the worst case?

Worst-case Analysis Worst-case analysis Show that the running time of quicksort is O(n2) by substitution method. Show that T(n)≤cn2 for some constant c.

Worst-case Analysis Worst-case analysis The internal expression is maximized when q = 0 or n-1. We can pick the constant c large enough so that the c(2n-1) term dominates the Θ(n) term. Thus, T(n)=O(n2).

Average-case Analysis By substitution method, show T(n)≤cnlgn for some c. Problem 7-2.

Average-case Analysis II Let X be the number of comparisons over the entire execution of QUICKSORT on an n-element array. Then the average running time of QUICKSORT is O(n + E[X]). We will not attempt to analyze how many comparisons are made in each PARTITION. Rather, we will derive an overall bound on the total number of comparisons.

Average-case Analysis II Let zi denote the ith smallest element in the sorted array. Zij = {zi, zi+1,…, zj} Each pair of elements zi and zj is compared at most once. An element is compared only to the pivot element in each PARTITION. The pivot element used in a PARTITION is never again compared to any other elements.

Average-case Analysis II Pr{zi is compared to zj} Pr{zi or zj is first pivot chosen from Zij}

Average-case Analysis II k = j – i, the harmonic series

Randomized quicksort RANDOMIZED-PARTITION(A, p, r) i ← RANDOM(p, r) exchange A[r] ↔ A[i] return PARTITION(A, p, r)

Randomized quicksort RANDOMIZED-QUICKSORT(A, p, r) 1 if p < r 2 then q ← RANDOMIZED-PARTITION(A, p, r) 3 RANDOMIZED-QUICKSORT(A, p, q - 1) 4 RANDOMIZED-QUICKSORT(A, q + 1, r)