Presented
By
Dr. Rajesh Purkait
Asst. Professor
Dept. of CSE ITER
(S`O’A Deemed To be University)
E-mail:
[email protected] • Review of previous sorting algorithm
• What is Divide-and-Conquer?
• Quick Sort Approach
• Describe Quick Sort Algorithm
• Divide
• Conquer/PARTITION
• Combine
• Analyzing Divide-and Conquer Algorithms
• Time complexity analysis based on partition
• How does partition affect performance?
• Randomized quick sort
• Quick sort in practice
Rajesh Purkait 10/17/2021 2
Insertion sort
◦ Design approach: incremental
◦ Sorts in place: Yes
◦ Best case: (n)
◦ Worst case: (n2)
Bubble Sort
◦ Design approach: incremental
◦ Sorts in place: Yes
◦ Running time: (n2)
Rajesh Purkait 10/17/2021 3
Selection sort
◦ Design approach: incremental
◦ Sorts in place: Yes
◦ Running time: (n2)
Merge Sort
◦ Design approach: divide and conquer
◦ Sorts in place: No O(n)
◦ Running time: O(nlgn)
Quick sort
◦ Design approach: divide and conquer
◦ Sorts in place: Let’s see!!
◦ Running time: Let’s see!!
Rajesh Purkait 10/17/2021 4
Running time insensitive of the input
Advantages:
◦ Guaranteed to run in (nlgn)
Disadvantage
◦ Requires extra space N
Rajesh Purkait 10/17/2021 5
A[p…q] ≤ A[q+1…r]
Sort an array A[p…r]
Divide
◦ Partition the array A into 2 subarrays A[p..q] and A[q+1..r],
such that each element of A[p..q] is smaller than or equal to
each element in A[q+1..r]
◦ Need to find index q to partition the array
Rajesh Purkait 10/17/2021 6
A[p…q] ≤ A[q+1…r]
Conquer
◦ Recursively sort A[p..q] and A[q+1..r] using Quicksort
Combine
◦ Trivial: the arrays are sorted in place
◦ No additional work is required to combine them
◦ The entire array is now sorted
Rajesh Purkait 10/17/2021 7
Initially: p=1, r=n
Alg.: QUICKSORT(A, p, r)
if p < r
then q PARTITION(A, p, r)
QUICKSORT (A, p, q)
QUICKSORT (A, q+1, r)
Recurrence:
T(n) = T(q) + T(n – q) + f(n) PARTITION())
Rajesh Purkait 10/17/2021 8
Choosing PARTITION()
◦ There are different ways to do this
◦ Each has its own advantages/disadvantages
Hoare partition
◦ Select a pivot element x around which to partition
◦ Grows two regions
A[p…i] x x A[j…r]
A[p…i] x
x A[j…r]
i j
Rajesh Purkait 10/17/2021 9
A[p…r] pivot x=5
5 3 2 6 4 1 3 7 5 3 2 6 4 1 3 7
i j i j
3 3 2 6 4 1 5 7 3 3 2 6 4 1 5 7
i j i j
A[p…q] A[q+1…r]
3 3 2 1 4 6 5 7 3 3 2 1 4 6 5 7
i j j i
10/17/2021 10
Rajesh Purkait 10/17/2021 11
Alg. PARTITION (A, p, r)
p r
1. x A[p]
2. ip–1 A: 5 3 2 6 4 1 3 7
3. jr+1
i j
4. while TRUE A[p…q] ≤ A[q+1…r]
5. do repeat j j – 1
A: ap ar
6. until A[j] ≤ x
7. do repeat i i + 1 j=q i
8. until A[i] ≥ x
9. if i < j Each element is
visited once!
10. then exchange A[i] A[j]
Running time: (n)
11. else return j n=r–p+1
Rajesh Purkait 10/17/2021 12
Initially: p=1, r=n
Alg.: QUICKSORT(A, p, r)
if p < r
then q PARTITION(A, p, r)
QUICKSORT (A, p, q)
QUICKSORT (A, q+1, r)
Recurrence:
T(n) = T(q) + T(n – q) + n
Rajesh Purkait 10/17/2021 13
The recurrence is based on the three steps of
the paradigm:
◦ T(n) – running time on a problem of size n
◦ Divide the problem into a subproblems, each of
size n/b: takes D(n)
◦ Conquer (solve) the subproblems aT(n/b)
◦ Combine the solutions C(n)
(1) if n ≤ c
T(n) = aT(n/b) + D(n) + C(n) otherwise
Rajesh Purkait 10/17/2021 14
Divide:
◦ compute q as per the partition method: D(n) = (n)
Conquer:
◦ recursively solve 2 sub-problems, each of size
T(q) and T(n – q)
Combine:
C(n) = 0
◦ No need for combination.
(1) if n =1
T(n) = T(q) + T(n – q) +(n) if n > 1
Rajesh Purkait 10/17/2021 15
Worst-case partitioning
◦ One region has one element and the other has n – 1
elements
◦ Maximally unbalanced n n
1 n-1 n
Recurrence: q=1 n-1
1 n-2
T(n) = T(1) + T(n – 1) + n, n 1 n-3 n-2
T(1) = (1) 1
2 3
T(n) = T(n – 1) + n 1 1 2
n (n2)
= n k 1 ( n ) ( n 2 ) ( n 2 )
k 1
When does the worst case happen?
10/17/2021 16
Best-case partitioning
◦ Partitioning produces two regions of size n/2
Recurrence: q=n/2
T(n) = 2T(n/2) + (n)
T(n) = (nlgn) (Master theorem)
10/17/2021 17
9-to-1 proportional split
Q(n) = Q(9n/10) + Q(n/10) + n
10/17/2021 18
Rajesh Purkait 10/17/2021 19
Rajesh Purkait 10/17/2021 20
Average case
◦ All permutations of the input numbers are equally likely
◦ On a random input array, we will have a mix of well
balanced and unbalanced splits
◦ Good and bad splits are randomly distributed across
throughout the tree
partitioning cost:
n combined partitioning cost: n n = (n)
1 n-1 2n-1 = (n)
(n – 1)/2 + 1 (n – 1)/2
(n – 1)/2 (n – 1)/2
Alternate of a good Nearly well
and a bad split balanced split
• Running time of Quicksort when levels alternate
between good and bad splits is O(nlgn)
Rajesh Purkait 10/17/2021 21
IDEA: Partition around a random element.
Running time is independent of the input order.
No assumption need to be made about the input
distribution.
No specific input elicits the worst case behavior.
The worst case is determined only by the output
of a random-number generator.
Rajesh Purkait 10/17/2021 22
Rajesh Purkait 10/17/2021 23
Quicksort is a great general-purpose sorting
algorithm.
Quicksort is typically over twice as fast as merge
sort.
Quicksort can benefit substantially from code
tuning.
Quicksort behaves well even with caching and
virtual memory.
Rajesh Purkait 10/17/2021 24
Rajesh Purkait 10/17/2021 25
