麻省理工学院：《算法导论》（英文版）Lecture 4 Prof. charles e. leiserson

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 xA 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

Example of partitioning 61013583211 Day 6 Introduction to Algorithms L46

Day 6 Introduction to Algorithms L4.6 Example of partitioning i j 66 1010 1313 55 88 33 22 1111

Example of partitioning 61013583211 Day 6 Introduction to Algorithms 4.7

Day 6 Introduction to Algorithms L4.7 Example of partitioning i j 66 1010 1313 55 88 33 22 1111

Example of partitioning 66 10135 3211 51310 88 3211 Day 6 Introduction to Algorithms L4.8

Day 6 Introduction to Algorithms L4.8 Example of partitioning 66 1010 1313 55 88 33 22 1111 i j 66 55 1313 1010 88 33 22 1111

Example of partitioning 66 10135 3211 51310 88 3211 Day 6 Introduction to Algorithms

Day 6 Introduction to Algorithms L4.9 Example of partitioning 66 1010 1313 55 88 33 22 1111 i j 66 55 1313 1010 88 33 22 1111

Example of partitioning 66 10135 3211 51310 88 3211 Day 6 Introduction to Algorithms L4.10

Day 6 Introduction to Algorithms L4.10 Example of partitioning 66 1010 1313 55 88 33 22 1111 i j 66 55 1313 1010 88 33 22 1111