ITM GOI
ACTIVITY 1
Analysis and Design of Algorithm (CS402)
TOPIC – Quicksort
BY- DEEPAK GAUTAM
0905CS201055
TO- Mrs. Neelam Joshi
Quicksort : Basic idea
Pick some number p from the array
Move all numbers less than p to the beginning of the array
Move all numbers greater than (or equal to) p to the end of the
array
Quicksort the numbers less than p
Quicksort the numbers greater than or equal to p
numbers p numbers greater
less than p than or equal to p
2
Quicksort
To sort a[left...right]:
1. if left < right:
1.1. Partition a[left...right] such that:
all a[left...p-1] are less than a[p], and
all a[p+1...right] are >= a[p]
1.2. Quicksort a[left...p-1]
1.3. Quicksort a[p+1...right]
2. Terminate
3
Partitioning (Quicksort)
A key step in the Quicksort algorithm is partitioning the
array
We choose some (any) number p in the array to use as a pivot
We partition the array into three parts:
numbers p numbers greater
less than p than or equal to p
4
Partitioning
Choose an array value (say, the first) to use as the
pivot
Starting from the left end, find the first element
that is greater than or equal to the pivot
Searching backward from the right end, find the
first element that is less than the pivot
Interchange (swap) these two elements
Repeat, searching from where we left off, until
done
5
Partitioning
To partition a[left...right]:
1. Set pivot = a[left], l = left + 1, r = right;
2. while l < r, do
2.1. while l < right & a[l] < pivot , set l = l + 1
2.2. while r > left & a[r] >= pivot , set r = r - 1
2.3. if l < r, swap a[l] and a[r]
3. Set a[left] = a[r], a[r] = pivot
4. Terminate
6
Example of partitioning
choose pivot: 4 3 6 9 2 4 3 1 2 1 8 9 3 5 6
search: 436924312189356
swap: 433924312189656
search: 433924312189656
swap: 433124312989656
search: 433124312989656
swap: 433122314989656
search: 4 3 3 1 2 2 3 1 4 9 8 9 6 5 6 (left > right)
swap with pivot: 133122344989656
7
The partition method
int partition(int[] a, int left, int right) {
int p = a[left], l = left + 1, r = right;
while (l < r) {
while (l < right && a[l] < p) l++;
while (r > left && a[r] >= p) r--;
if (l < r) {
int temp = a[l]; a[l] = a[r]; a[r] = temp;
}
}
a[left] = a[r];
a[r] = p;
return r;
}
8
The quicksort method
void quicksort(int[] array, int left, int right) {
if (left < right) {
int p = partition(array, left, right);
quicksort(array, left, p - 1);
quicksort(array, p + 1, right);
}
}
9
Analysis of quicksort—best case
Suppose each partition operation divides the array
almost exactly in half
Then the depth of the recursion in log2n
Because that’s how many times we can halve n
However, there are many recursions!
How can we figure this out?
We note that
Each partition is linear over its subarray
All the partitions at one level cover the array
10
Partitioning at various levels
11
Best case
We cut the array size in half each time
So the depth of the recursion in log2n
At each level of the recursion, all the partitions at that
level do work that is linear in n
O(log2n) * O(n) = O(n log2n)
Hence in the average case, quicksort has time
complexity O(n log2n)
What about the worst case?
12
Worst case
In the worst case, partitioning always divides the size n
array into these three parts:
A length one part, containing the pivot itself
A length zero part, and
A length n-1 part, containing everything else
We don’t recur on the zero-length part
Recurring on the length n-1 part requires (in the worst
case) recurring to depth n-1
13
Worst case partitioning
14
Worst case for quicksort
In the worst case, recursion may be n levels deep (for
an array of size n)
But the partitioning work done at each level is still n
O(n) * O(n) = O(n2)
So worst case for Quicksort is O(n2)
When does this happen?
There are many arrangements that could make this happen
Here are two common cases:
When the array is already sorted
When the array is inversely sorted (sorted in the opposite order)
15
Typical case for quicksort
If the array is sorted to begin with, Quicksort is
terrible: O(n2)
It is possible to construct other bad cases
However, Quicksort is usually O(n log2n)
The constants are so good that Quicksort is
generally the fastest algorithm known
Most real-world sorting is done by Quicksort
16
