Recall Mergesort, worst case O(n log(n)) time.
Quicksort is worst case O(n²) time. But on average, it takes n log(n).
Quicksort does not use extra memory; it is an inplace algorithm.
Algorithm overview:
Choose a pivot element and partition the array around the pivot, that is, each element in the first part is less than the pivot and each element in the second part is greater than the pivot.
Sort the two parts.
Implementation:
void quicksort(int[] A, int begin, int end) {
if (begin == end) { // base case, empty
return; // do nothing
} else {
int pivot_pos = partition(A, begin, end);
quicksort(A, begin, pivot_pos);
quicksort(A, pivot_pos+1, end);
}
}
The partition function chooses the pivot and then rearranges the
array around the pivot so that every element less or equal to the
pivot is to the left of the pivot and every element greater than the
pivot is to the right of the pivot.
The choice of pivot is important because it controls the size of the left and right-hand sides.
An even split of the array is good because it leads to a balanced tree of recursive procedure calls.
There are many ways to choose the pivot element. One of the simplest is to choose the last element, but that doesn’t guarantee an even split.
Simple implementation:
static int partition_ez(int[] A, int begin, int end) {
ArrayList<Integer> L = new ArrayList<Integer>();
ArrayList<Integer> R = new ArrayList<Integer>();
int pivot = A[end - 1];
for (int i = begin; i != end - 1; ++i) {
if (A[i] ≤ pivot) { L.add(A[i]); } // O(1)
else { R.add(A[i]); }
}
int pivot_loc = copy(L, A, begin);
A[pivot_loc] = pivot;
copy(R, A, pivot_loc + 1);
return pivot_loc;
}
Time complexity: O(n) Space complexity: O(n)
But we can be more space efficient by reusing A for L and R.
Example run of the partition algorithm:
[2,8,7,1,3,5,6,4] (draw with extra space between the numbers)
The last element is the pivot:
[2,8,7,1,3,5,6|4]
We move from left to right, separating the elements into those less than 4 and those greater than 4.
[||2,8,7,1,3,5,6|4]
[2||8,7,1,3,5,6|4]
[2|8|7,1,3,5,6|4]
[2|8,7|1,3,5,6|4]
swap 1 with 8 (the front of the sequence of greater-than elements)
[2,1|7,8|3,5,6|4]
swap 3 with 7
[2,1,3|8,7|5,6|4]
[2,1,3|8,7,5|6|4]
[2,1,3|8,7,5,6||4]
To finish off, we need to put 4 (the pivot) into the middle. swap 4 with 8
[2,1,3|4|7,5,6,8]
Looking at a half-way point in the run gives us a good idea for what the algorithm needs to do.
[2,1|7,8|3,5,6|4]
i j
if A[j] ≤ pivot, swap it with first greater-than elt., increment i and j
[2,1,3|8,7|5,6|4]
i j
if A[j] > pivot, just move on to the next j
[2,1,3|8,7,5|6|4]
i j
Space-efficient implementation:
int partition(int[] A, int begin, int end) {
int pivot = A[end-1];
int i = begin;
for (int j = begin; j != end-1; ++j) {
if (A[j] ≤ pivot) {
swap(A, i, j);
++i;
}
}
swap(A, i, end-1);
return i;
}
Apply quicksort to the array, write the state of the array after each step within the partitioning
[6,1,2,3]
quicksort(A, 0, 4)
partition around 3
[|6|1,2|3] [1|6|2|3] [1,2|6|3] [1,2|3|6] 0 1 2 3 4
partition around 2
[||1|2]
[1|||2]
[1|2|]
partition around 1
| [ | 1] | ||
| [ | 1 | ] |
partition around 6
[|||6]
[|6|]
A better way to choose the pivot is to choose an element at random.
This makes it difficult for a hacker to take advantage of quicksort in a denial-of-service attack.
Also, the probability of the random choice landing at the far ends of the array is low, so the splits are even enough to make the probabilistic “expected” time complexity to be O(n log(n)).
Let L be the region [begin..i) (L for “less or equal”)
Let G be the region [i,j) (G for “greater”)
Let T be the region [j,end-1) (T for “to-do”)
The postcondition that we want to prove is:
let pivot_loc = partition(A, start, end)
for i in [start,pivot_loc), A[i] ≤ A[pivot_loc]
for i in [pivot_loc+1,end), A[pivot_loc] < A[i]
loop invariant:
Recipe for checking a loop invariant:
At the start of the loop:
|||--T--|p|
i j
L and G are both empty, so the loop invariant holds trivially
In the loop:
|--L--|--G--|--T--|p|
i j
|--L--||--T--|p|
i
j
there are two cases to consider
A[j] ≤ pivot
Here we have two cases to consider, whether G is empty or not. The same code runs in either case, but the reason why it is correct is different in each case.
a) Suppose G is not empty. We add A[j] to the L region by swapping it with the first element x of G (at i) and incrementing i. Because A[j] ≤ pivot, we have that every elt. of L is less than pivot. Also, we want to keep x in G, so we increment j. The elements in G haven’t changed, so they are all still greater than pivot.
b) Suppose G is empty. We still swap A[j] with i , but that’s a no-op because j == i. We increment i and j, thereby adding A[j] to L. G remains empty.
A[j] > pivot
|--L--|--G--|--T--|p|
i j
We add A[j] to the G region by incrementing j. We have A[j] > pivot and the rest of G hasn’t changed, so every elt. of G is greater than pivot. We haven’t changed L, so every elt. of L is less than pivot.
After the loop:
We have L = [start,i), G = [i,end-1), and T = [j, end-1) but loop condition says j == end-1.
|---L---|---G---|p|
i
We swap the pivot p with the first elt. of G (at i)
|---L---|p|---G---|
Let pivot_loc = i.
Now we have L = [start,pivot_loc), G = [pivot+1,end).
Every element of L is less than A[pivot].
Every element of G is greater than A[pivot].
So the proof is complete.
Suppose that each time we partition, it turns out that everything ends up in L. So the recursive call to sort L is T(n-1) and G is T(0).
T(0) = 1
T(n) = T(n-1) + T(0) + n
T(n) = T(n-1) + T(o) + n
= (T(n-2) + T(0) + n-1) + T(o) + n
= T(n-2) + 2 + n + n-1
= T(n-3) + 3 + n + n-1 + n-2
T(n) in O(n²)
Suppose that each time we partition, L and G come out the same size.
T(n) = T(n/2) + T(n/2) + Θ(n) = 2 T(n/2) + Θ(n)
T(n) in O(n log(n))