Introduction to algorithms 6.046J/18.401J/SMA5503 Lecture 4 Prof. charles e. leiserson
Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 4 Prof. Charles E. Leiserson
Quicksort 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) Day 6 Introduction to Algorithms L4.2
Day 6 Introduction to Algorithms L4.2 Quicksort • 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)
Divide and conquer Quicksort an n-element array 1. Divide: Partition the array into two subarrays around a pivot x such that elements in lower subarray xs elements in upper subarray X X x 2. Conquer: Recursively sort the two subarrays 3. Combine: Trivial Key: Linear-time partitioning subroutine Day 6 Introduction to Algorithms L4.3
Day 6 Introduction to Algorithms L4.3 Divide and conquer Quicksort 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. ≤≤xx xx ≥≥xx Key: Linear-time partitioning subroutine
Partitioning subroutine PARTITION(A, P, DAlp. q x<alp p pivot A[p] Running time <p O(n) for n forj<p+ l to g elements do if Alji≤x then iti+1 exchange A[分>A exchange Alp<> Ai return i variant:x≤x Day 6 Introduction to Algorithms
Day 6 Introduction to Algorithms L4.4 xx Running time = O(n) for n elements. Running time = O(n) for n elements. Partitioning subroutine PARTITION(A, p, q) ⊳ A[p . . q] x ← A[p] ⊳ pivot = A[p] i ← p for j ← p + 1 to q do if A[j] ≤ x then i ← i + 1 exchange A[i] ↔ A[j] exchange A[p] ↔ A[i] return i ≤≤xx ≥≥xx ?? pi q j Invariant:
Example of partitioning 61013583211 Day 6 Introduction to Algorithms L4.5
Day 6 Introduction to Algorithms L4.5 Example of partitioning i j 66 1010 1313 55 88 33 22 1111