程序代写代做代考 algorithm data structure PowerPoint Presentation

PowerPoint Presentation

Faculty of Information Technology,
Monash University

FIT2004: Algorithms and Data Structures
Week 3:
Quick Sort and its Analysis

These slides are prepared by M. A. Cheema and are based on the material developed by Arun Konagurthu and Lloyd Allison.

Things to note/remember
FIT2004: Lec-3: Quick Sort and its Analysis
Assignment 1 due 10-April 23:59:00
Assignment 2 released soon
Requires dynamic programming (taught in week 4) – don’t miss the lecture

Quick Sort and its Analysis
FIT2004: Lec-3: Quick Sort and its Analysis
Algorithm and partitioning
Complexity Analysis
Improving Worst-case complexity
Quick Select
Quick Sort in O(N log N) worst-case

Quick Sort Idea
FIT2004: Lec-3: Quick Sort and its Analysis
If list is length 1 or less, do nothing
Choose a pivot p
Put items <= p on the left, items >p on the right
Quicksort the left and right parts of the list

Quicksort
Choose a pivot p
2 8 7 1 3 4 5 6

FIT2004: Lec-3: Quick Sort and its Analysis

Quicksort
Choose a pivot p
Partition the array in two sub-arrays w.r.t. p
LEFT  elements smaller than or equal to p
RIGHT  elements greater than p
2 8 7 1 3 4 5 6

8 7 5 6

2 1 3

Pivot
X

In Sorted position
X

Others
FIT2004: Lec-3: Quick Sort and its Analysis

Quicksort
Choose a pivot p
Partition the array in two sub-arrays w.r.t. p
LEFT  elements smaller than or equal to p
RIGHT  elements greater than p
2 8 7 1 3 4 5 6

8 7 5 6

2 1 3

Pivot now in sorted position

Pivot
X

In Sorted position
X

Others
FIT2004: Lec-3: Quick Sort and its Analysis
<=p >p

Quicksort
Choose a pivot p
Partition the array in two sub-arrays w.r.t. p
LEFT  elements smaller than or equal to p
RIGHT  elements greater than p
2 8 7 1 3 4 5 6

8 7 5 6

2 1 3

Pivot
X

In Sorted position
X

Others
Partitioning

FIT2004: Lec-3: Quick Sort and its Analysis

<=p >p

Pivot now in sorted position

Quicksort
Choose a pivot p
Partition the array in two sub-arrays w.r.t. p
LEFT  elements smaller than or equal to p
RIGHT  elements greater than p
Quicksort(LEFT)
2 8 7 1 3 4 5 6

8 7 5 6

2 1 3

Pivot
X

In Sorted position
X

Others
Partitioning

FIT2004: Lec-3: Quick Sort and its Analysis

<=p >p

Pivot now in sorted position

Quicksort
Choose a pivot p
Partition the array in two sub-arrays w.r.t. p
LEFT  elements smaller than or equal to p
RIGHT  elements greater than p
Quicksort(LEFT)
2 8 7 1 3 4 5 6

8 7 5 6

2 1 3

Pivot
X

In Sorted position
X

Others
Partitioning

FIT2004: Lec-3: Quick Sort and its Analysis

Quicksort this sublist

Quicksort
Choose a pivot p
Partition the array in two sub-arrays w.r.t. p
LEFT  elements smaller than or equal to p
RIGHT  elements greater than p
Quicksort(LEFT)
2 8 7 1 3 4 5 6

8 7 5 6

1 2 3

Pivot
X

In Sorted position
X

Others
Partitioning

FIT2004: Lec-3: Quick Sort and its Analysis

Quicksort this sublist

Quicksort
Choose a pivot p
Partition the array in two sub-arrays w.r.t. p
LEFT  elements smaller than or equal to p
RIGHT  elements greater than p
Quicksort(LEFT)
2 8 7 1 3 4 5 6

8 7 5 6

1 2 3

Pivot
X

In Sorted position
X

Others
Partitioning

FIT2004: Lec-3: Quick Sort and its Analysis

Quicksort this sublist

Quicksort
Choose a pivot p
Partition the array in two sub-arrays w.r.t. p
LEFT  elements smaller than or equal to p
RIGHT  elements greater than p
Quicksort(LEFT)
2 8 7 1 3 4 5 6

8 7 5 6

1 2 3

Pivot
X

In Sorted position
X

Others
Partitioning

FIT2004: Lec-3: Quick Sort and its Analysis

Quicksort
Choose a pivot p
Partition the array in two sub-arrays w.r.t. p
LEFT  elements smaller than or equal to p
RIGHT  elements greater than p
Quicksort(LEFT)
Quicksort(RIGHT)
2 8 7 1 3 4 5 6

8 7 5 6

1 2 3

Pivot
X

In Sorted position
X

Others
Partitioning

FIT2004: Lec-3: Quick Sort and its Analysis

Quicksort this sublist

8 7 5 6

1 2 3

Pivot
X

In Sorted position
X

Others
Partitioning

FIT2004: Lec-3: Quick Sort and its Analysis

Quicksort this sublist (not shown in slides)

Partitioning: An out-of-place version
Initialize two lists LEFT and RIGHT
For each element e (except pivot)
If e ≤ pivot
Insert e in LEFT
If e > pivot
Insert e in RIGHT
FIT2004: Lec-3: Quick Sort and its Analysis
2 8 7 1 3 4 5 6

Partitioning: An out-of-place version
Initialize two lists LEFT and RIGHT
For each element e (except pivot)
If e ≤ pivot
Insert e in LEFT
If e > pivot
Insert e in RIGHT
LEFT
RIGHT
FIT2004: Lec-3: Quick Sort and its Analysis
2 8 7 1 3 4 5 6

8 7

2 1

8 7

2 1

8 7

2 1 3

8 7

2 1 3

8 7

2 1 3

8 7 5

2 1 3

8 7 5

2 1 3

8 7 5 6

Partitioning: An out-of-place version
Initialize two lists LEFT and RIGHT
For each element e (except pivot)
If e ≤ pivot
Insert e in LEFT
If e > pivot
Insert e in RIGHT
Copy LEFT+ [pivot] + RIGHT over the input array
LEFT
RIGHT
FIT2004: Lec-3: Quick Sort and its Analysis
2 8 7 1 3 4 5 6

2 1 3

8 7 5 6

Initialize two lists LEFT and RIGHT
For each element e (except pivot)
If e ≤ pivot
Insert e in LEFT
If e > pivot
Insert e in RIGHT
Copy LEFT+ [pivot] + RIGHT over the input array

Array is now correctly partitioned
2 1 3 4 8 7 5 6

Partitioning: An out-of-place version
FIT2004: Lec-3: Quick Sort and its Analysis

2 1 3 4 8 7 5 6

Array is now correctly partitioned
Algorithm is clearly not in place
FIT2004: Lec-3: Quick Sort and its Analysis

2 1 3 4 8 7 5 6

Array is now correctly partitioned
Algorithm is clearly not in place
Is this algorithm stable?
FIT2004: Lec-3: Quick Sort and its Analysis
Quiz time!
https://flux.qa – 92A2WY

2 1 3 4 8 7 5 6

Array is now correctly partitioned
Algorithm is clearly not in place
Is this algorithm stable? No. Elements which are equal to the pivot end up on the left regardless
FIT2004: Lec-3: Quick Sort and its Analysis

2 8 6 4 1 7 3 5

Partitioning: In place (Hoare’s)
Swap pivot to the front (position 1)
FIT2004: Lec-3: Quick Sort and its Analysis

Partitioning: In place (Hoare’s)
Swap pivot to the front (position 1)
L_bad = 2, R_bad = N
FIT2004: Lec-3: Quick Sort and its Analysis
4 8 6 2 1 7 3 5

Partitioning: In place (Hoare’s)
Swap pivot to the front (position 1)
L_bad = 2, R_bad = N
Repeat until L_bad and R_bad cross
move L_bad right until we find a “bad” element, i.e. > pivot
move R_bad left until we find a “bad” element, i.e. < pivot swap these elements FIT2004: Lec-3: Quick Sort and its Analysis 4 8 6 2 1 7 3 5 41 Partitioning: In place (Hoare’s) Swap pivot to the front (position 1) L_bad = 2, R_bad = N Repeat until L_bad and R_bad cross move L_bad right until we find a “bad” element, i.e. > pivot
move R_bad left until we find a “bad” element, i.e. < pivot swap these elements FIT2004: Lec-3: Quick Sort and its Analysis 4 8 6 2 1 7 3 5 42 Partitioning: In place (Hoare’s) Swap pivot to the front (position 1) L_bad = 2, R_bad = N Repeat until L_bad and R_bad cross move L_bad right until we find a “bad” element, i.e. > pivot
move R_bad left until we find a “bad” element, i.e. < pivot swap these elements FIT2004: Lec-3: Quick Sort and its Analysis 4 8 6 2 1 7 3 5 43 Partitioning: In place (Hoare’s) Swap pivot to the front (position 1) L_bad = 2, R_bad = N Repeat until L_bad and R_bad cross move L_bad right until we find a “bad” element, i.e. > pivot
move R_bad left until we find a “bad” element, i.e. < pivot swap these elements FIT2004: Lec-3: Quick Sort and its Analysis 4 3 6 2 1 7 8 5 44 Partitioning: In place (Hoare’s) Swap pivot to the front (position 1) L_bad = 2, R_bad = N Repeat until L_bad and R_bad cross move L_bad right until we find a “bad” element, i.e. > pivot
move R_bad left until we find a “bad” element, i.e. < pivot swap these elements FIT2004: Lec-3: Quick Sort and its Analysis 4 3 6 2 1 7 8 5 45 Partitioning: In place (Hoare’s) Swap pivot to the front (position 1) L_bad = 2, R_bad = N Repeat until L_bad and R_bad cross move L_bad right until we find a “bad” element, i.e. > pivot
move R_bad left until we find a “bad” element, i.e. < pivot swap these elements FIT2004: Lec-3: Quick Sort and its Analysis 4 3 6 2 1 7 8 5 46 Partitioning: In place (Hoare’s) Swap pivot to the front (position 1) L_bad = 2, R_bad = N Repeat until L_bad and R_bad cross move L_bad right until we find a “bad” element, i.e. > pivot
move R_bad left until we find a “bad” element, i.e. < pivot swap these elements FIT2004: Lec-3: Quick Sort and its Analysis 4 3 6 2 1 7 8 5 47 Partitioning: In place (Hoare’s) Swap pivot to the front (position 1) L_bad = 2, R_bad = N Repeat until L_bad and R_bad cross move L_bad right until we find a “bad” element, i.e. > pivot
move R_bad left until we find a “bad” element, i.e. < pivot swap these elements FIT2004: Lec-3: Quick Sort and its Analysis 4 3 1 2 6 7 8 5 48 Partitioning: In place (Hoare’s) Swap pivot to the front (position 1) L_bad = 2, R_bad = N Repeat until L_bad and R_bad cross move L_bad right until we find a “bad” element, i.e. > pivot
move R_bad left until we find a “bad” element, i.e. < pivot swap these elements FIT2004: Lec-3: Quick Sort and its Analysis 4 3 1 2 6 7 8 5 49 Partitioning: In place (Hoare’s) Swap pivot to the front (position 1) L_bad = 2, R_bad = N Repeat until L_bad and R_bad cross move L_bad right until we find a “bad” element, i.e. > pivot
move R_bad left until we find a “bad” element, i.e. < pivot swap these elements FIT2004: Lec-3: Quick Sort and its Analysis 4 3 1 2 6 7 8 5 50 Partitioning: In place (Hoare’s) Swap pivot to the front (position 1) L_bad = 2, R_bad = N Repeat until L_bad and R_bad cross move L_bad right until we find a “bad” element, i.e. > pivot
move R_bad left until we find a “bad” element, i.e. < pivot swap these elements FIT2004: Lec-3: Quick Sort and its Analysis 4 3 1 2 6 7 8 5 51 Partitioning: In place (Hoare’s) Swap pivot to the front (position 1) L_bad = 2, R_bad = N Repeat until L_bad and R_bad cross move L_bad right until we find a “bad” element, i.e. > pivot
move R_bad left until we find a “bad” element, i.e. < pivot swap these elements swap pivot to R_bad FIT2004: Lec-3: Quick Sort and its Analysis 4 3 1 2 6 7 8 5 52 Partitioning: In place (Hoare’s) Swap pivot to the front (position 1) L_bad = 2, R_bad = N Repeat until L_bad and R_bad cross move L_bad right until we find a “bad” element, i.e. > pivot
move R_bad left until we find a “bad” element, i.e. < pivot swap these elements swap pivot to R_bad FIT2004: Lec-3: Quick Sort and its Analysis 2 3 1 4 6 7 8 5 53 Partitioning: In place (Hoare’s) Pros: Each element only swapped once (except pivot) Simple idea Simple invariant (what is it?) Cons: Very tricky to implement without bugs Termination conditions Edge cases Off by one errors Not stable FIT2004: Lec-3: Quick Sort and its Analysis Quiz time! https://flux.qa - 92A2WY 54 Partitioning: In place (Hoare’s) Pros: Each element only swapped once (except pivot) Simple idea Simple invariant (what is it?) Cons: Very tricky to implement without bugs Termination conditions Edge cases Off by one errors Not stable What about duplicates? FIT2004: Lec-3: Quick Sort and its Analysis 55 Partition and duplicates If the list has many duplicates, then sometimes… One will be chosen as the pivot All the others should go next to the pivot (and therefore not need to be moved any more) But the algorithms we have seen would require them to be sorted in the recursive calls! We want a partition method that does this: FIT2004: Lec-3: Quick Sort and its Analysis

Sort this

Not this!

And this

Dutch National Flag Problem
Given a list of elements and a function that maps them to red, white and blue
Arrange the list to look like the dutch national flag

This is equivalent to our problem
Our function maps elements less than the pivot to blue, equal elements to white, and greater elements to red
FIT2004: Lec-3: Quick Sort and its Analysis

Dutch National Flag Algoithm
boundary1=1,
j=1
boundary2 = n

FIT2004: Lec-3: Quick Sort and its Analysis

Dutch National Flag Algoithm
boundary1=1,
j=1
boundary2 = n
While j <=boundary2 if array[j] is blue swap array[boundary1], array[j] boundary1 += 1 j += 1 elif array[j] is red swap array[j], array[boundary2] boundary2 -= 1 else j += 1 FIT2004: Lec-3: Quick Sort and its Analysis 59 Dutch National Flag Algoithm boundary1=1, j=1 boundary2 = n While j <=boundary2 if array[j] is blue swap array[boundary1], array[j] boundary1 += 1 j += 1 elif array[j] is red swap array[j], array[boundary2] boundary2 -= 1 else j += 1 FIT2004: Lec-3: Quick Sort and its Analysis 60 Dutch National Flag Algoithm boundary1=1, j=1 boundary2 = n While j <=boundary2 if array[j] is blue swap array[boundary1], array[j] boundary1 += 1 j += 1 elif array[j] is red swap array[j], array[boundary2] boundary2 -= 1 else j += 1 FIT2004: Lec-3: Quick Sort and its Analysis 61 Dutch National Flag Algoithm boundary1=1, j=1 boundary2 = n While j <=boundary2 if array[j] is blue swap array[boundary1], array[j] boundary1 += 1 j += 1 elif array[j] is red swap array[j], array[boundary2] boundary2 -= 1 else j += 1 FIT2004: Lec-3: Quick Sort and its Analysis 62 Dutch National Flag Algoithm boundary1=1, j=1 boundary2 = n While j <=boundary2 if array[j] is blue swap array[boundary1], array[j] boundary1 += 1 j += 1 elif array[j] is red swap array[j], array[boundary2] boundary2 -= 1 else j += 1 FIT2004: Lec-3: Quick Sort and its Analysis 63 Dutch National Flag Algoithm boundary1=1, j=1 boundary2 = n While j <=boundary2 if array[j] is blue swap array[boundary1], array[j] boundary1 += 1 j += 1 elif array[j] is red swap array[j], array[boundary2] boundary2 -= 1 else j += 1 FIT2004: Lec-3: Quick Sort and its Analysis 64 Dutch National Flag Algoithm boundary1=1, j=1 boundary2 = n While j <=boundary2 if array[j] is blue swap array[boundary1], array[j] boundary1 += 1 j += 1 elif array[j] is red swap array[j], array[boundary2] boundary2 -= 1 else j += 1 FIT2004: Lec-3: Quick Sort and its Analysis 65 Dutch National Flag Algoithm boundary1=1, j=1 boundary2 = n While j <=boundary2 if array[j] is blue swap array[boundary1], array[j] boundary1 += 1 j += 1 elif array[j] is red swap array[j], array[boundary2] boundary2 -= 1 else j += 1 FIT2004: Lec-3: Quick Sort and its Analysis 66 Dutch National Flag Algoithm boundary1=1, j=1 boundary2 = n While j <=boundary2 if array[j] is blue swap array[boundary1], array[j] boundary1 += 1 j += 1 elif array[j] is red swap array[j], array[boundary2] boundary2 -= 1 else j += 1 FIT2004: Lec-3: Quick Sort and its Analysis 67 Dutch National Flag Algoithm boundary1=1, j=1 boundary2 = n While j <=boundary2 if array[j] is blue swap array[boundary1], array[j] boundary1 += 1 j += 1 elif array[j] is red swap array[j], array[boundary2] boundary2 -= 1 else j += 1 FIT2004: Lec-3: Quick Sort and its Analysis 68 Dutch National Flag Algoithm boundary1=1, j=1 boundary2 = n While j <=boundary2 if array[j] is blue swap array[boundary1], array[j] boundary1 += 1 j += 1 elif array[j] is red swap array[j], array[boundary2] boundary2 -= 1 else j += 1 FIT2004: Lec-3: Quick Sort and its Analysis 69 Dutch National Flag Algoithm boundary1=1, j=1 boundary2 = n While j <=boundary2 if array[j] is blue swap array[boundary1], array[j] boundary1 += 1 j += 1 elif array[j] is red swap array[j], array[boundary2] boundary2 -= 1 else j += 1 FIT2004: Lec-3: Quick Sort and its Analysis 70 Dutch National Flag Algoithm boundary1=1, j=1 boundary2 = n While j <=boundary2 if array[j] is blue swap array[boundary1], array[j] boundary1 += 1 j += 1 elif array[j] is red swap array[j], array[boundary2] boundary2 -= 1 else j += 1 FIT2004: Lec-3: Quick Sort and its Analysis 71 Dutch National Flag Algoithm boundary1=1, j=1 boundary2 = n While j <=boundary2 if array[j] is blue swap array[boundary1], array[j] boundary1 += 1 j += 1 elif array[j] is red swap array[j], array[boundary2] boundary2 -= 1 else j += 1 FIT2004: Lec-3: Quick Sort and its Analysis 72 Dutch National Flag Algoithm boundary1=1, j=1 boundary2 = n While j <=boundary2 if array[j] is blue swap array[boundary1], array[j] boundary1 += 1 j += 1 elif array[j] is red swap array[j], array[boundary2] boundary2 -= 1 else j += 1 Return boundary1, boundary2 FIT2004: Lec-3: Quick Sort and its Analysis 73 Dutch National Flag Algoithm boundary1=1, j=1 boundary2 = n While j <=boundary2 if array[j] is blue swap array[boundary1], array[j] boundary1 += 1 j += 1 elif array[j] is red swap array[j], array[boundary2] boundary2 -= 1 else j += 1 Return boundary1, boundary2 FIT2004: Lec-3: Quick Sort and its Analysis Now quicksort the red and blue parts 74 Partitioning summary FIT2004: Lec-3: Quick Sort and its Analysis Lots to consider State of the art is more complex Objectives Minimise swaps Minimise work in recursive calls Be in place How to make these stable? A question for the tute… 75 Quick Sort and its Analysis FIT2004: Lec-3: Quick Sort and its Analysis Algorithm and partitioning Complexity Analysis Improving Worst-case complexity Quick Select Quick Sort in O(N log N) worst-case Best-case time complexity O(N) O(N) O(N) Best-case Height: O(log N) Best-case complexity: O(N log N) Important: Quicksort is not in-place even when in-place partitioning is used. Why? Recursion depth is at least O(log N) FIT2004: Lec-3: Quick Sort and its Analysis Quicksort Algorithm Choose a pivot Partitioning using pivot Quicksort(LEFT) Quicksort(RIGHT) 77 Worst-case Time Complexity Worst-case Height: O(N) Worst-case Complexity: O(N2) FIT2004: Lec-3: Quick Sort and its Analysis Quicksort Algorithm Choose a pivot Partitioning using pivot Quicksort(LEFT) Quicksort(RIGHT) 78 Average-case Time complexity FIT2004: Lec-3: Quick Sort and its Analysis After partitioning, pivot has 50% probability to be in the green sub-array and has 50% probability to be in one of the two grey sub-arrays. i.e., on average, pivot will be in green half of the time and in grey half of the time N/4 N/4 N/2 Average-case Time complexity FIT2004: Lec-3: Quick Sort and its Analysis If pivot is in grey sub-array The worst-case (most unbalanced) partition sizes will be 1 and N-1 If pivot is in green sub-array The worst-case partition sizes will be N/4 and 3N/4 For the purpose of the following argument, we assume these one of these worst case scenarios always happen The complexity we obtain will therefore be at least as bad as the true complexity Let h be the height when pivot is always in green. N/4 N/4 N/2 Height when pivot always in green FIT2004: Lec-3: Quick Sort and its Analysis Max height is on the branch N/4 N/4 N/2 3N/4 9N/16 27N/64 , Stops when size reaches 1 Height when pivot always in green FIT2004: Lec-3: Quick Sort and its Analysis N/4 N/4 N/2 3N/4 9N/16 27N/64 Average case FIT2004: Lec-3: Quick Sort and its Analysis N/4 N/4 N/2 3N/4 9N/16 In reality, pivot will be in green half the time Previously we had Now this doubles h is still ) Nathan Companez (NC) - Average case Time complexity FIT2004: Lec-3: Quick Sort and its Analysis Therefore, height in average case is O(log N) Like before, the cost at each level is O(N) The average case complexity is thus O(N log N) Does O(loga N) = O(logb N) if a and b are constants? Change of base rule: So the base of the log doesn’t matter for complexity (though it does in practice) Best-case time complexity using recurrence FIT2004: Lec-3: Quick Sort and its Analysis Recurrence relation: T(1) = b T(N) = c*N + T(N/2) + T(N/2) = 2*T(N/2) + c*N Solution (exercise in last week): O(N log N) Quicksort Algorithm Choose a pivot Partitioning using pivot Quicksort(LEFT) Quicksort(RIGHT) Worst-case complexity using recurrence FIT2004: Lec-3: Quick Sort and its Analysis Recurrence relation: T(1) = b T(N) = T(N-1) + c*N Solution: O(N2) Quicksort Algorithm Choose a pivot Partitioning using pivot Quicksort(LEFT) Quicksort(RIGHT) Break Time Problem (not examinable) FIT2004: Lec-3: Quick Sort and its Analysis There are 25 horses (who each run at some different fixed speed and never get tired) We want to find the 3 fastest We can race 5 horses at a time We cannot time the horses, only observe the order in which they finish How many races do we need? 87 Quick Sort and its Analysis FIT2004: Lec-3: Quick Sort and its Analysis Algorithm Complexity Analysis Improving Worst-case complexity Quick Select Quick Sort in O(N log N) worst-case Quicksort with O(N log N) in worst-case FIT2004: Lec-3: Quick Sort and its Analysis Idea: Don’t choose pivot randomly! Instead, always choose median as the pivot. If we can find median in O(N), the worst-case cost of quicksort would be? O(N log N) How do we choose median in O(N)? First, we take a detour and see algorithms to answer k-th order statistics N/2 N/2 Quicksort Algorithm Choose median as a pivot Partitioning using pivot Quicksort(LEFT) Quicksort(RIGHT) K-th Order Statistics FIT2004: Lec-3: Quick Sort and its Analysis Problem: Given an unsorted array, find k-th smallest element in the array If k=1 (i.e., find the smallest), we can easily do this in O(N) using the linear algorithm we saw in the last week. Median can be computed by setting k appropriately (e.g., k = len(array)/2) For general k, how can we solve this efficiently? Sort the elements and return k-th element – takes O(N log N) Can we do better? Yes, Quick Select Quick Sort and its Analysis FIT2004: Lec-3: Quick Sort and its Analysis Algorithm and partitioning Complexity Analysis Improving Worst-case complexity Quick Select Quick Sort in O(N log N) worst-case Quick Select Choose a pivot p Partition the array in two sub-arrays w.r.t. p (same partitioning as in quicksort) LEFT  elements smaller than or equal to p RIGHT  elements greater than p If index(pivot) == k: Return pivot If k > index(pivot)
QuickSelect(RIGHT)
Else:
QuickSelect(LEFT)
20 80 90 10 30 50 70 60

80 90 70 60

20 10 30

In sorted position (at index 4, i.e., 4th smallest)

Pivot
X

In Sorted position
X

Others
FIT2004: Lec-3: Quick Sort and its Analysis
k = 6
k = 3
Best-case time complexity?
O(N)
Worst-case time complexity?
O(N2)
Average-case time complexity?
O(N) – same arguments as for quicksort

Quicksort with O(N log N) in worst-case
FIT2004: Lec-3: Quick Sort and its Analysis
Call Quick Select with k=len(array)/2?
The value returned by Quick Select will be median.
Choose this as the pivot.
What will be the best-case cost of such quick sort?
O(N log N)
What is the worst-case cost?

N/2
N/2

Quicksort Algorithm
Use quick select to find median
Partitioning using median as pivot
Quicksort(LEFT)
Quicksort(RIGHT)

Quick Sort Worst-case when using
Quick Select to choose pivot

N2
Worst-case cost at level k: N2/2k
Total cost: N2 + N2/2 + N2/4 + … + 1 = N2(1 + ½ + ¼ + … )
= O(N2)
FIT2004: Lec-3: Quick Sort and its Analysis
Quicksort Algorithm
Use quick select to find median
Partitioning using median as pivot
Quicksort(LEFT)
Quicksort(RIGHT)
N2/4
N2/2
N2/16
N2/16
N2/16
N2/16
N2/4
N2/4

Where are we?
Trying to make quicksort Nlog(N) in the worst case
Need to find median in O(N)
We have an algorithm (quickselect) which finds median in O(N) in the best case (and average case)…
But it is O(N2) in the worst case (which would make quicksort slower)… sigh
We want to make quickselect always take O(N)
What do we need? A median pivot for quickselect!
FIT2004: Lec-3: Quick Sort and its Analysis

Where are we?
What do we need? A median pivot for quickselect!
But that is what quickselect is meant to do…
Sounds impossible – in order for quickselect to run in O(N) we need to find a good (i.e. median) pivot in O(N), but that was exactly the problem quickselect was meant to solve!
The trick – relax definition of a “good pivot”
A good pivot is anything which cuts the list into fixed fractions
E.g. it would be enough to always cut it 70:30
FIT2004: Lec-3: Quick Sort and its Analysis
Quiz time!
https://flux.qa – 92A2WY

Where are we?
What do we need? A median pivot for quickselect!
But that is what quickselect is meant to do…
Sounds impossible – in order for quickselect to run in O(N) we need to find a good (i.e. median) pivot in O(N), but that was exactly the problem quickselect was meant to solve!
The trick – relax definition of a “good pivot”
A good pivot is anything which cuts the list into fixed fractions
E.g. it would be enough to always cut it 70:30
Even 99:1 would be ok for NlogN, but slower in practice, so the closer to 50:50 the better
FIT2004: Lec-3: Quick Sort and its Analysis

Quick Sort and its Analysis
FIT2004: Lec-3: Quick Sort and its Analysis
Algorithm and partitioning
Complexity Analysis
Improving Worst-case complexity
Quick Select
Quick Sort in O(N log N) worst-case

Median of medians (not examinable)
FIT2004: Lec-3: Quick Sort and its Analysis
1 15 10 10 7 20 8 19 11 2 12 16 12
12 20 5 8 2 6 19 1 15 4 13 20 2
15 17 10 14 13 7 15 7 11 10 16 18 10
7 2 15 4 20 16 18 1 8 17 16 6 17
7 8 16 18 19 20 12 10 11 1 19 13 5

Median of medians (not examinable)
FIT2004: Lec-3: Quick Sort and its Analysis
15 20 16 18 20 20 19 19 15 17 19 20 17
12 17 15 14 19 20 18 10 11 10 16 18 12
7 15 10 10 13 16 15 7 11 4 16 16 10
7 8 10 8 7 7 12 1 11 2 13 13 5
1 2 5 4 2 6 8 1 8 1 12 6 2

Bigger

Smaller

Sort groups of size five

Bigger

Smaller

Sort groups of size five
Find the medians

Median of medians (not examinable)
FIT2004: Lec-3: Quick Sort and its Analysis
17 15 19 16 18 17 15 20 20 19 20 19 20
10 12 10 15 14 12 11 19 17 18 20 16 18
4 7 7 10 10 10 11 13 15 15 16 16 16
2 7 1 10 8 5 11 7 8 12 7 13 13
1 1 1 5 4 2 8 2 2 8 6 12 6

Bigger

Smaller

Sort groups of size five
Find the medians
Find the median of those!
(Note that the columns do not actually get sorted, just shown here in sorted order for clarity)
Bigger

Smaller

Bigger

Smaller

Median of medians is bigger than half the medians
Bigger

Smaller

Bigger

Smaller

Median of medians is bigger than half the medians
So it is bigger than all the red values as well
Bigger

Smaller

Bigger

Smaller

Median of medians is smaller than half the medians
Bigger

Smaller

Bigger

Smaller

Median of medians is smaller than half the medians
So it is smaller than the green values as well
Bigger

Smaller

Quiz time!
https://flux.qa – 92A2WY

Bigger

Smaller

Median of medians is greater than 30% and also less than 30%, so its in the middle 40%
The worst split we can get using the MoM is 70:30!
However, we did need to find the exact median of n/5 items… how?
Bigger

Smaller

Quicksort with O(N log N) in worst-case (not examinable)
FIT2004: Lec-3: Quick Sort and its Analysis
Median_of_medians(list[1..n])
divide into sublists of size 5
medians = [median of each sublist]
use quickselect to find the median of medians

Quicksort with O(N log N) in worst-case (not examinable)
FIT2004: Lec-3: Quick Sort and its Analysis
Median_of_medians(list[1..n])
if n <= 5 use insertion sort to find the median, and return it divide into sublists of size 5 medians = [median of each sublist] use quickselect to find the median of medians Quicksort with O(N log N) in worst-case (not examinable) FIT2004: Lec-3: Quick Sort and its Analysis Median_of_medians(list[1..n]) if n <= 5 use insertion sort to find the median, and return it divide into sublists of size 5 medians = [median of each sublist] return quickselect(medians, (len(medians)+1)/2) Quicksort with O(N log N) in worst-case (not examinable) FIT2004: Lec-3: Quick Sort and its Analysis Quickselect(list, lo, hi, k) if lo > hi
return array[k]
pivot = median_of_medians(list, lo, hi, k)
mid = partition(array, lo, hi, pivot)
if mid > k
return quickselect(array, lo, mid-1, k)
elif k > mid
return quickselect(array, mid+1, hi, k)
else
return array[k]
This call uses quickselect!
But with a weaker pivot

Quicksort with O(N log N) in worst-case (not examinable)
FIT2004: Lec-3: Quick Sort and its Analysis
Quickselect(list, lo, hi, k)
if lo > hi
return array[k]
pivot = median_of_medians(list, lo, hi, k) (
mid = partition(array, lo, hi, pivot) (70:30 pivot in worst)
if mid > k
return quickselect(array, lo, mid-1, k) (n/7 in worst)
elif k > mid
return quickselect(array, mid+1, hi, k) (n/7 in worst)
else
return array[k]
This call uses quickselect!
But with a weaker pivot

Quicksort with O(N log N) in worst-case (not examinable)
FIT2004: Lec-3: Quick Sort and its Analysis
Quickselect time complexity recurrence

for recursing on the list of the medians of groups of 5 (inside the call to median of medians)
for the main recursive call, which is guaranteed to have split the list at least 30:70 (because the pivot was selected by MoM)
for the linear time partition algorithm + time to find medians of groups of five

Solving this give linear time!
So armed with a linear time quickselect, we can now quicksort in NlogN worst case…

Anticlimax (examinable)
FIT2004: Lec-3: Quick Sort and its Analysis
Although using “median of medians” reduces worst-case complexity to O(N log N), in practice choosing random pivots works better.
However, theoretical improvement in worst-case is quite satisfying.

Concluding Remarks
FIT2004: Lec-3: Quick Sort and its Analysis
Summary
Quicksort and its analysis. Quicksort can be made O(N log N) in worst-case which is mostly of theoretical interest but does not usually improve performance in practice.
It is better to do a simple pivot selection which takes less time (like random selection)

Coming Up Next
Dynamic Programming – (super important and powerful tool, assignment 2 is all about dynamic programming)

Things to do before next lecture
Make sure you understand this lecture completely especially the (examinable) average-case complexity analysis of quicksort

FIT2004: Lec-3: Quick Sort and its Analysis
Recurrence relation:
T(N) = ???
For simplicity, assume partitioning costs (N+1) operations
Assume pivot is at index k
Tk(N) = (N+1) + T(N-k) + T(k-1)
Average cost is the average for k being from 1 to N

k
k-1

N-k

T(N-1)
T(N-2)
T(N-3)
…
T(2)
T(1)
T(0)

T(0)
T(1)
T(2)
…
T(N-3)
T(N-2)
T(N-1)

Quicksort Algorithm
Choose a pivot
Partitioning using pivot
Quicksort(LEFT)
Quicksort(RIGHT)
Average-case complexity using recurrence
(NOT EXAMINABLE)

Average-case complexity using recurrence
(NOT EXAMINABLE)
FIT2004: Lec-3: Quick Sort and its Analysis
Recurrence relation:
T(1) = b

Multiplying N on both sides
(A)
(B)
(A) – (B)
Simplify
Divide both sides by N

Average-case complexity using recurrence
(NOT EXAMINABLE)
FIT2004: Lec-3: Quick Sort and its Analysis
Recurrence relation:
T(1) = b
Let’s solve it:

(A)
Replace T(N-1) in (A)
Cost for T(N-1)
Cost for T(N-2)
Replace T(N-2) in (B)
See the pattern for k?
(B)

Average-case complexity using recurrence
(NOT EXAMINABLE)
FIT2004: Lec-3: Quick Sort and its Analysis
Recurrence relation:
T(1) = b
Let’s solve it:

T(N) = O (N log N)

1 2 3 4 5 … N

area under curve

Area of rectangles
N-k =1  k = N-1
Simplify

FIT2004: Lec-3: Quick Sort and its Analysis

Partitioning: In place (Lomuto’s)
Swap pivot to the front (position 1)

FIT2004: Lec-3: Quick Sort and its Analysis
6 3 1 2 4 7 8 5

121

Partitioning: In place (Lomuto’s)
Swap pivot to the front (position 1)
i = 2, swap_pos = 2

FIT2004: Lec-3: Quick Sort and its Analysis
4 8 6 2 1 7 3 5

122

Partitioning: In place (Lomuto’s)
Swap pivot to the front (position 1)
i = 2, swap_pos = 2
While i <= N If array[i] < array[1] (pivot) swap array[i], array[swap_pos] swap_pos += 1 i += 1 FIT2004: Lec-3: Quick Sort and its Analysis 4 8 6 2 1 7 3 5 123 Partitioning: In place (Lomuto’s) Swap pivot to the front (position 1) i = 2, swap_pos = 2 While i <= N If array[i] < array[1] (pivot) swap array[i], array[swap_pos] swap_pos += 1 i += 1 FIT2004: Lec-3: Quick Sort and its Analysis 4 8 6 2 1 7 3 5 124 Partitioning: In place (Lomuto’s) Swap pivot to the front (position 1) i = 2, swap_pos = 2 While i <= N If array[i] < array[1] (pivot) swap array[i], array[swap_pos] swap_pos += 1 i += 1 FIT2004: Lec-3: Quick Sort and its Analysis 4 8 6 2 1 7 3 5 125 Partitioning: In place (Lomuto’s) Swap pivot to the front (position 1) i = 2, swap_pos = 2 While i <= N If array[i] < array[1] (pivot) swap array[i], array[swap_pos] swap_pos += 1 i += 1 FIT2004: Lec-3: Quick Sort and its Analysis 4 2 6 8 1 7 3 5 126 Partitioning: In place (Lomuto’s) Swap pivot to the front (position 1) i = 2, swap_pos = 2 While i <= N If array[i] < array[1] (pivot) swap array[i], array[swap_pos] swap_pos += 1 i += 1 FIT2004: Lec-3: Quick Sort and its Analysis 4 2 6 8 1 7 3 5 127 Partitioning: In place (Lomuto’s) Swap pivot to the front (position 1) i = 2, swap_pos = 2 While i <= N If array[i] < array[1] (pivot) swap array[i], array[swap_pos] swap_pos += 1 i += 1 FIT2004: Lec-3: Quick Sort and its Analysis 4 2 6 8 1 7 3 5 128 Partitioning: In place (Lomuto’s) Swap pivot to the front (position 1) i = 2, swap_pos = 2 While i <= N If array[i] < array[1] (pivot) swap array[i], array[swap_pos] swap_pos += 1 i += 1 FIT2004: Lec-3: Quick Sort and its Analysis 4 2 1 8 6 7 3 5 129 Partitioning: In place (Lomuto’s) Swap pivot to the front (position 1) i = 2, swap_pos = 2 While i <= N If array[i] < array[1] (pivot) swap array[i], array[swap_pos] swap_pos += 1 i += 1 FIT2004: Lec-3: Quick Sort and its Analysis 4 2 1 8 6 7 3 5 130 Partitioning: In place (Lomuto’s) Swap pivot to the front (position 1) i = 2, swap_pos = 2 While i <= N If array[i] < array[1] (pivot) swap array[i], array[swap_pos] swap_pos += 1 i += 1 FIT2004: Lec-3: Quick Sort and its Analysis 4 2 1 8 6 7 3 5 131 Partitioning: In place (Lomuto’s) Swap pivot to the front (position 1) i = 2, swap_pos = 2 While i <= N If array[i] < array[1] (pivot) swap array[i], array[swap_pos] swap_pos += 1 i += 1 FIT2004: Lec-3: Quick Sort and its Analysis 4 2 1 8 6 7 3 5 132 Partitioning: In place (Lomuto’s) Swap pivot to the front (position 1) i = 2, swap_pos = 2 While i <= N If array[i] < array[1] (pivot) swap array[i], array[swap_pos] swap_pos += 1 i += 1 FIT2004: Lec-3: Quick Sort and its Analysis 4 2 1 3 6 7 8 5 133 Partitioning: In place (Lomuto’s) Swap pivot to the front (position 1) i = 2, swap_pos = 2 While i <= N If array[i] < array[1] (pivot) swap array[i], array[swap_pos] swap_pos += 1 i += 1 FIT2004: Lec-3: Quick Sort and its Analysis 4 2 1 3 6 7 8 5 134 Partitioning: In place (Lomuto’s) Swap pivot to the front (position 1) i = 2, swap_pos = 2 While i <= N If array[i] < array[1] (pivot) swap array[i], array[swap_pos] swap_pos += 1 i += 1 FIT2004: Lec-3: Quick Sort and its Analysis 4 2 1 3 6 7 8 5 135 Partitioning: In place (Lomuto’s) Swap pivot to the front (position 1) i = 2, swap_pos = 2 While i <= N If array[i] < array[1] (pivot) swap array[i], array[swap_pos] swap_pos += 1 i += 1 FIT2004: Lec-3: Quick Sort and its Analysis 4 2 1 3 6 7 8 5 136 Partitioning: In place (Lomuto’s) Swap pivot to the front (position 1) i = 2, swap_pos = 2 While i <= N If array[i] < array[1] (pivot) swap array[i], array[swap_pos] swap_pos += 1 i += 1 swap array[1], array[swap_pos - 1] FIT2004: Lec-3: Quick Sort and its Analysis 4 2 1 3 6 7 8 5 137 Partitioning: In place (Lomuto’s) Swap pivot to the front (position 1) i = 2, swap_pos = 2 While i <= N If array[i] < array[1] (pivot) swap array[i], array[swap_pos] swap_pos += 1 i += 1 swap array[1], array[swap_pos - 1] FIT2004: Lec-3: Quick Sort and its Analysis 3 2 1 4 6 7 8 5 138 Partitioning: In place (Lomuto’s) Pros: Easy to implement Also simple invariant, though less elegant Cons: Multiple swaps for some elements (inefficient compared to Hoare’s) Not stable FIT2004: Lec-3: Quick Sort and its Analysis 139 a N N b b a log log log = N ) T(k k) T(N N N N T N T N k N k k å å = = - + - + + = = 1 1 1 ) 1 ( ) ( ) ( N ) T(k k) T(N N N T N k å = - + - + + = 1 1 ) 1 ( ) ( å = - N k k) T(N 1 å = - N k ) T(k 1 1 = å = - + + = N k ) T(k N N N T 1 1 2 ) 1 ( ) ( å = - + + = N k ) T(k N N N T 1 1 2 ) 1 ( ) ( å = - + + = N k ) T(k N N N T N 1 1 2 ) 1 ( ) ( . å - = - + - = - - 1 1 1 2 ) 1 ( ) 1 ( ). 1 ( N k ) T(k N N N T N ) 1 ( 2 2 ) 1 ( ). 1 ( ) ( . - + = - - - N T N N T N N T N ) 1 ( ). 1 ( 2 ) 1 ( ). 1 ( ) 1 ( 2 2 ) ( . - + + = - - + - + = N T N N N T N N T N N T N ) 1 ( 1 2 ) ( - + + = N T N N N T ) 1 ( 1 2 ) ( - + + = N T N N N T ) 2 ( 1 1 ) 1 ( 2 2 )) 2 ( 1 2 ( 1 2 ) ( - - + + + + = - - + + + = N T N N N N N T N N N N N T ) 2 ( 1 2 ) 1 ( - - + = - N T N N N T ) 3 ( 2 1 2 ) 2 ( - - - + = - N T N N N T ) 3 ( 2 ) 1 ( 2 1 ) 1 ( 2 ) 1 ( 2 2 ) ( - - + + - + + + + = N T N N N N N N N T ) ( 1 ) 1 ( 2 2 ) 1 ( 2 ... 2 ) 1 ( 2 1 ) 1 ( 2 ) 1 ( 2 2 ) ( k N T k N N k N N N N N N N N N T - + - + + + - + + + - + + - + + + + = ) ln( ) 1 ( 2 ) 1 ( 2 ) ( N N N b N T + + + + < ) 1 ( 2 ) 1 ( 2 3 ) 1 ( 2 ... 2 ) 1 ( 2 1 ) 1 ( 2 ) 1 ( 2 2 ) ( T N N N N N N N N N T + + + + + - + + - + + + + = ) 1 ( ) 3 1 ... 2 1 1 1 1 )( 1 ( 2 2 ) ( + + + + - + - + + + = N b N N N N N T å = + + + + = N k k N N b N T 3 1 ) 1 ( 2 ) 1 ( 2 ) ( ) ln( 1 1 N dx x N = ò ) ln( 1 3 N k N k å = < å = N k k 3 1 /docProps/thumbnail.jpeg

Related Posts