程序代写代做代考 algorithm 11.key

11.key

http://people.eng.unimelb.edu.au/tobym

@tobycmurray

toby.murray@unimelb.edu.au

DMD 8.17 (Level 8, Doug McDonell Bldg)

Toby Murray

COMP90038  
Algorithms and Complexity

Lecture 11: Sorting with Divide-and-Conquer  
(with thanks to Harald Søndergaard)

Divide and Conquer
• We earlier studied recursion as a powerful problem

solving technique.

• The divide-and-conquer strategy tries to make the most
of this idea:
1. Divide the given problem instance into smaller

instances.
2. Solve the smaller instances recursively.
3. Combine the smaller solutions to solve the original

instance.

• This works best when the smaller instances can be made
to be of equal (or near-equal) size.

Split-Solve-and-Join  
Approach

Divide and Conquer
Algorithms

• We will discuss:
• The Master Theorem
• Mergesort
• Quicksort
• Tree traversal
• Closest Pair revisited

Divide-and-Conqer
General Case

problem of size n

problem
of size n/b

problem
of size n/b …

problem
of size n/b

b sub-problems

Divide-and-Conqer
General Case

problem of size n

problem
of size n/b

problem
of size n/b …

problem
of size n/b

only a sub-problems need to be solved

Divide-and-Conqer
General Case

problem of size n

problem
of size n/b

problem
of size n/b …

problem
of size n/b

only a sub-problems need to be solved

combine the a
solutions

Divide-and-Conquer
Recurrences
• What is the time required to solve a problem of size n by

divide-and-conquer?

• For the general case, assume we split the problem into b
instances (each of size n/b), of which a need to be
solved:  
 
 
where f(n) expresses the time spent on dividing a problem
into b sub-problems and combining the a results.

• (A very common case is T(n) = 2T(n/2) + n.)

• How to find closed forms for these recurrences?

T(n) = aT(n/b) + f(n)

The Master Theorem
• (A proof is in Levitin’s Appendix B.)

• For integer constants a ≥ 1 and b > 1, and function
f with f(n) ∈ Θ(nd), d ≥ 0, the recurrence  
 
 
(with T(1) = c) has solutions, and  
 
 

• Note that we also allow a to be greater than b.

T(n) = aT(n/b) + f(n)

Master Theorem: Example 1

T(n) = 2T(n/2) + n a = 2, b = 2, d = 1

Master Theorem: Example 1

T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
a = bd

So, by the Master Theorem, T(n) ∈ Θ(n log n)

Master Theorem: Example 1

T(n) = 2T(n/2) + n a = 2, b = 2, d = 1

Master Theorem: Example 1

T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) = 2(2T(n/4) + (n/2)) + n

Master Theorem: Example 1

T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) = 4T(n/4) + 2(n/2) + n

Master Theorem: Example 1

T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) = 4(2T(n/8) + n/4) + 2(n/2) + n

Master Theorem: Example 1

T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) = 8T(n/8) + 4(n/4) + 2(n/2) + n

Master Theorem: Example 1

T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) = 8(2T(n/16) + n/8) + 4(n/4) + 2(n/2) + n

Master Theorem: Example 1

T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) = 16T(n/16) + 8(n/8) + 4(n/4) + 2(n/2) + n

Master Theorem: Example 1

T(n) = 2T(n/2) + n a = 2, b = 2, d = 1

Master Theorem: Example 1

T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) ∈ Θ(n log n)

Master Theorem: Example 2

T(n) = 4T(n/4) + n a = 4, b = 4, d = 1
a = bd

So, by the Master Theorem, T(n) ∈ Θ(n log n)

Master Theorem: Example 2

T(n) = 4T(n/4) + n a = 4, b = 4, d = 1

Master Theorem: Example 2

T(n) = 4T(n/4) + n
T(n) = 4(4T(n/16) + (n/4)) + n

a = 4, b = 4, d = 1

Master Theorem: Example 2

T(n) = 4T(n/4) + n
T(n) = 16T(n/16) + 4(n/4) + n

a = 4, b = 4, d = 1

Master Theorem: Example 2

T(n) = 4T(n/4) + n
T(n) = 16T(n/16) + 4(n/4) + n

a = 4, b = 4, d = 1

Master Theorem: Example 2

T(n) = 4T(n/4) + n
T(n) = 16(4T(n/64) + n/16) 4(n/4) + n

a = 4, b = 4, d = 1

Master Theorem: Example 2

T(n) = 4T(n/4) + n
T(n) = 64T(n/64) + 16(n/16) + 4(n/4) + n

a = 4, b = 4, d = 1

Master Theorem: Example 2

T(n) = 4T(n/4) + n
T(n) = 64T(n/64) + 16(n/16) + 4(n/4) + n

a = 4, b = 4, d = 1
…

(log4 n times)

Master Theorem: Example 2

T(n) = 4T(n/4) + n
T(n) = 64T(n/64) + 16(n/16) + 4(n/4) + n

a = 4, b = 4, d = 1
…

(log4 n times)

Master Theorem: Example 2

T(n) ∈ Θ(n log n)

a = 4, b = 4, d = 1 T(n) = 4T(n/4) + n
T(n) = 64T(n/64) + 16(n/16) + 4(n/4) + n

Master Theorem: Example 3

a = 1, b = 2, d = 1 T(n) = T(n/2) + n

Master Theorem: Example 3

a = 1, b = 2, d = 1 T(n) = T(n/2) + n

So, by the Master Theorem, T(n) ∈ Θ(n)

a < bd Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Master Theorem: Example 3 33 a = 1, b = 2, d = 1 T(n) = T(n/2) + n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Master Theorem: Example 3 34 a = 1, b = 2, d = 1 T(n) = T(n/2) + n T(n) = T(n/4) + n/2 + n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Master Theorem: Example 3 35 a = 1, b = 2, d = 1 T(n) = T(n/2) + n T(n) = T(n/8) + n/4 + n/2 + n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Master Theorem: Example 3 36 a = 1, b = 2, d = 1 T(n) = T(n/2) + n T(n) = T(n/8) + n/4 + n/2 + n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Master Theorem: Example 3 37 a = 1, b = 2, d = 1 T(n) = T(n/2) + n T(n) = T(n/8) + n/4 + n/2 + n T(n) ∈ Θ(n) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Master Theorem: Example 4 38 a = 2, b = 2, d = 2 T(n) = 2T(n/2) + n2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Master Theorem: Example 4 39 a = 2, b = 2, d = 2 T(n) = 2T(n/2) + n2 a < bd So, by the Master Theorem, T(n) ∈ Θ(n2) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Master Theorem: Example 4 40 a = 2, b = 2, d = 2 T(n) = 2T(n/2) + n2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Master Theorem: Example 4 41 a = 2, b = 2, d = 2 T(n) = 2T(n/2) + n2 T(n) = 2(2T(n/4) + (n/2)2) + n2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Master Theorem: Example 4 42 a = 2, b = 2, d = 2 T(n) = 2T(n/2) + n2 T(n) = 4T(n/4) + 2(n/2)2 + n2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Master Theorem: Example 4 43 a = 2, b = 2, d = 2 T(n) = 2T(n/2) + n2 T(n) = 4(2T(n/8) + (n/4)2) + 2(n/2)2 + n2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Master Theorem: Example 4 44 a = 2, b = 2, d = 2 T(n) = 2T(n/2) + n2 T(n) = 8T(n/8) + 4(n/4)2 + 2(n/2)2 + n2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Master Theorem: Example 4 45 a = 2, b = 2, d = 2 T(n) = 2T(n/2) + n2 T(n) = 8T(n/8) + 4(n/4)2 + 2(n/2)2 + n2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Master Theorem: Example 4 46 a = 2, b = 2, d = 2 T(n) = 2T(n/2) + n2 T(n) = 8T(n/8) + 4(n/4)2 + 2(n/2)2 + n2 T(n) ∈ Θ(n2) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort • Perhaps the most obvious application of divide-and-conquer: • To sort an array (or a list), cut it into two halves, sort each half, and merge the two results. 47 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 48 Mergesort Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 49 Mergesort Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 50 Mergesort Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 51 Mergesort Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 52 Mergesort Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 53 Mergesort Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 54 Mergesort Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 55 Mergesort Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 56 Mergesort Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 57 Mergesort Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 58 Mergesort Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 59 Mergesort Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 60 Mergesort Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 61 Mergesort Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 62 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 63 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 64 1 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 65 1 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 66 1 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 67 1 2 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 68 1 2 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 69 1 2 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 70 1 2 3 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 71 1 2 3 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 72 1 2 3 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 73 1 2 3 4 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 74 1 2 3 4 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 75 1 2 3 4 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 76 1 2 3 4 5 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 77 1 2 3 4 5 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 78 1 2 3 4 5 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 79 1 2 3 4 5 7 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 80 1 2 3 4 5 7 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 81 1 2 3 4 5 7 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 82 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 83 1 2 3 4 5 7 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 84 1 2 3 4 5 7 8 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 85 1 2 3 4 5 7 8 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 86 1 2 3 4 5 7 8 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Merging Arrays 87 1 2 3 4 5 7 8 0 1 2 3 4 5 6 2 3 8 9 1 4 5 0 1 2 3 0 1 2 7 3 B: C: 9 7 A: i j k p: 4 q: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Analysis • How many comparisons will MERGE need to make in the worst case, when given arrays of size ⌊n/2⌋ and ⌈n/2⌉ ? • If the largest and second-largest elements are in different arrays, then n − 1 comparisons. Hence the cost equation for Mergesort is     • By the Master Theorem, C(n) ∈ Θ(n log n). 88 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Properties • For large n, the number of comparisons made tends to be around 75% of the worst-case scenario. • Is mergesort stable? • Is mergesort in-place? • If comparisons are fast, mergesort ranks between quicksort and heapsort (covered next week) for time, assuming random data. • Mergesort is the method of choice for linked lists and for very large collections of data. 89 ? no Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Stability 90 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Mergesort: Properties • For large n, the number of comparisons made tends to be around 75% of the worst-case scenario. • Is mergesort stable? • Is mergesort in-place? • If comparisons are fast, mergesort ranks between quicksort and heapsort (covered next week) for time, assuming random data. • Mergesort is the method of choice for linked lists and for very large collections of data. 91 yes no Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Bottom-Up Mergesort • An alternative way of doing mergesort: • Generate runs of length 2, then of length 4, and so on: 92 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Quicksort • Quicksort takes a divide-and-conquer approach that is different to mergesort’s. • It uses the partitioning idea from QuickSelect, picking a pivot element, and partitioning the array around that, so as to obtain this situation:       • The element A[s] will be in its final position (it is the (s + 1)th smallest element). • All that then needs to be done is to sort the segment to the left, recursively, as well as the segment to the right. 93 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Quicksort • Very short and elegant:             • Initial call: Quicksort(A, 0, n − 1). 94 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 9 Quicksort: Example 95 23 8 41 22 3 37A: 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 8 Quicksort: Example 96 3 9 41 22 23 37A: 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 8 9 Quicksort: Example 97 3 41 22 23 37A: 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 3 9 Quicksort: Example 98 8 41 22 23 37A: 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 4183 9 Quicksort: Example 99 22 23 37A: 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 3783 9 Quicksort: Example 100 22 23 41A: 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 37 4183 9 Quicksort: Example 101 22 23A: 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 3723 4183 9 Quicksort: Example 102 22A: 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 23 37 4183 9 Quicksort: Example 103 22A: 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 22 37 4183 9 Quicksort: Example 104 23A: 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 2322 37 4183 9 Quicksort: Example 105 A: 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Hoare Partitioning • The standard way of doing partitioning in Quicksort 106 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Hoare Partitioning 107 9 23 8 41 22 3 37A: 0 1 2 3 4 5 6 p: 9 i j Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Hoare Partitioning 108 9 23 8 41 22 3 37A: 0 1 2 3 4 5 6 p: 9 i j Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Hoare Partitioning 109 9 23 8 41 22 3 37A: 0 1 2 3 4 5 6 p: 9 i j Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Hoare Partitioning 110 9 3 8 41 22 23 37A: 0 1 2 3 4 5 6 p: 9 i j Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Hoare Partitioning 111 9 3 8 41 22 23 37A: 0 1 2 3 4 5 6 p: 9 i j Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Hoare Partitioning 112 9 3 8 41 22 23 37A: 0 1 2 3 4 5 6 p: 9 i j Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Hoare Partitioning 113 9 3 8 41 22 23 37A: 0 1 2 3 4 5 6 p: 9 i j Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Hoare Partitioning 114 9 3 8 41 22 23 37A: 0 1 2 3 4 5 6 p: 9 ij Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Hoare Partitioning 115 9 3 8 41 22 23 37A: 0 1 2 3 4 5 6 p: 9 ij Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Hoare Partitioning 116 9 3 41 8 22 23 37A: 0 1 2 3 4 5 6 p: 9 ij Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Hoare Partitioning 117 9 3 8 41 22 23 37A: 0 1 2 3 4 5 6 p: 9 ij Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Hoare Partitioning 118 8 3 9 41 22 23 37A: 0 1 2 3 4 5 6 p: 9 ij Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Quicksort Analysis:   Best Case Analysis • The best case happens when the pivot is the median; that results in two sub-tasks of equal size.         The ‘n’ is for the n key comparisons performed by Partition. • By the Master Theorem, Cbest(n) ∈ Θ(n log n), just as for mergesort, so quicksort’s best case is (asymptotically) no better than mergesort’s worst case. 119 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Quicksort Worst Case 120 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Quicksort Analysis:  Worst Case Analysis • The worst case happens if the array is already sorted. • In that case, we don’t really have divide-and- conquer, because each recursive call deals with a problem size that has only been decremented by 1:         • That is, Cworst(n) = n + (n − 1) + · · · + 3 + 2 ∈ Θ(n2). 121 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Quicksort Improvements: Median-of-Three • It would be better if the pivot was chosen randomly.  • A cheap and useful approximation to this is to take the median of three candidates, A[lo], A[hi], and A[⌊(lo + hi)/2⌋].     • Reorganise the three elements so that p1 is the median, and p3 is the largest of the three. • Now run quicksort as before. 122 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Quicksort Improvements: Median-of-Three • In fact, with median-of-three, we can have a much faster version than before, simplifying tests in the innermost loops: 123 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Quicksort Improvements: Early Cut-Off • A second useful improvement is to stop quicksort early and switch to insertion sort. This is easily implemented: 124 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Quicksort Properties • With these (and other) improvements, quicksort is considered the best available sorting method for arrays of random data. • A major reason for its speed is the very tight inner loop in PARTITION. • Although mergesort has a better performance guarantee, quicksort is faster on average. • In the best case, we get ⌈log2 n⌉ recursive levels. It can be shown that on random data, the expected number is 2 loge n ≈ 1.38 log2 n. So quicksort’s average behaviour is very close to the best-case behaviour. • Is quicksort stable? • Is it in-place? 125 ? yes Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Quicksort Stability 126 2 2 1 i j Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Quicksort Stability 127 2 2 1 i j Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Quicksort Stability 128 2 2 1 i j Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Quicksort Stability 129 221 i j Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Quicksort Stability 130 221 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Quicksort Stability 131 221 2 2 1 This is where we finished This is where we started Not stable Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Quicksort Properties • With these (and other) improvements, quicksort is considered the best available sorting method for arrays of random data. • A major reason for its speed is the very tight inner loop in PARTITION. • Although mergesort has a better performance guarantee, quicksort is faster on average. • In the best case, we get ⌈log2 n⌉ recursive levels. It can be shown that on random data, the expected number is 2 loge n ≈ 1.38 log2 n. So quicksort’s average behaviour is very close to the best-case behaviour. • Is quicksort stable? • Is it in-place? 132 no yes Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Next up • Tree traversal methods, plus we apply the divide- and-conquer technique to the closest-pair problem. 133

Related Posts