Sorting Algorithms –II
Quick Sort
CSE 2215 - Lecture 5 - Fall 2023
Instructor : Fahmid Al Rifat, Lecturer, Dept. of CSE , UIU
mohaiminul@[Link] 1
Divide & Conquer (revisited)
2
Divide-and-Conquer Technique
Divide-and-Conquer is a general algorithm design paradigm:
o Divide the problem into a number of subproblems that are
smaller
o instances of the same problem
o Conquer the subproblems by solving them recursively
o Combine the solutions to the subproblems into the solution for
the
o original problem
The base case for the recursion are subproblems of constant size
Analysis can be done using recurrence equations
3
Quick Sort
4
Divide-and-Conquer
5
Merge Sort and Quick Sort
• Two well-known sorting algorithms adopt this divide-and-conquer strategy
Merge sort
o Divide step is trivial – just split the list into two equal parts.
o Work is carried out in the conquer step by merging two sorted lists.
Quicksort
o Work is carried out in the divide step using a pivot element.
o Conquer step is trivial.
6
Quick Sort
Another divide-and-conquer algorithm
■ The array A[p..r] is partitioned into two non-empty subarrays A[p..q] and
A[q+1..r]
p q q+1 r
8 15 4 30 25 7 18 12 8 4 7 12 15 30 25 18
Invariant: All elements in A[p..q] are less than all elements in A[q+1..r]
■ The subarrays are recursively sorted by calls to quicksort
■ Unlike merge sort, no combining step: two subarrays form an already-sorted
array
Quick Sort
Quicksort -Simulation
10
Quicksort -Simulation
11
Quicksort -Simulation
12
Quicksort -Simulation
13
Quicksort -Simulation
14
Quicksort -Simulation
15
Quicksort -Simulation
16
Quicksort -Simulation
17
Quicksort -Simulation
18
Quicksort -Simulation
19
Quicksort -Simulation
20
Quicksort -Simulation
21
Quicksort -Simulation
22
Quick Sort (Partition)
Clearly, all the actions take place in the partition()function
■ Rearranges the subarrays in place
■ End result:
Two subarrays
All values in first subarray | pivot | all values in the second subarray
■ Returns the index of the “pivot” element separating the two subarrays
Quick Sort (Analysis)
What will be the worst case for the
algorithm?
■ Partition is always unbalanced
What will be the best case for the algorithm?
■ Partition is perfectly balanced
Which is more likely?
■ The partition is almost balanced …
Will any particular input elicit the worst
case?
■ Yes: Already-sorted input
Quick Sort: Worst case running time
The recurrence for the worst-case running time T(n) is [Partition is always
unbalanced]
Quick Sort: Best case running time
The recurrence for the best-case running time T(n) is [Partition is always
balanced]
Quick Sort: Running Time
Quick Sort: Analysis
The real liability of quicksort is that it runs in O(n2) on already-sorted
input Two solutions:
■ Randomize the input array, OR
■ Pick a random pivot element
How will these solve the problem?
■ By ensuring that no particular input can be chosen to make quick-sort
run in O(n2) time
■ Assuming random input, average-case running time is much closer
to O(nlog n) than O(n2)
Thank You
29