Quicksort

We take a look at quicksort and how it bipartitions an array then recurses to sort the left and right half (or almost half) from the pivot after partitioning.

Table of Contents

Code Sample

/*
Quicksort. Picking the pivot is 'pivotal' to the
algorithm's performance ;)
This version picks the last item in the partition space
as the pivot everytime, there are many other ways to choose
a pivot item.
The video to explain this code is here: https://www.youtube.com/watch?v=uXBnyYuwPe8
*/
/*
Top-level helper to help the caller pass less arguments in. We know that
quicksort will start with considering the whole array
*/
public void quicksort(int arr[]) {
quicksort(arr, 0, arr.length - 1);
}
/*
Top level function that calls 'partition' and splits the data based on
where 'partition' leaves the choosen pivot value
*/
private void quicksort(int arr[], int left, int right) {
if (left < right) {
/*
Partition the array from left to right and find where the
selected pivot belongs
*/
int pivotFinalRestingPosition = partition(arr, left, right);
/*
Call quicksort to the left and to the right of the pivot
*/
quicksort(arr, left, pivotFinalRestingPosition - 1);
quicksort(arr, pivotFinalRestingPosition + 1, right);
}
}
/*
The partition function that chooses a pivot, partitions the array around
the pivot, places the pivot value where it belongs, and then returns the
index of where the pivot finally lies
*/
private int partition(int arr[], int left, int right) {
/*
In this implementation of quicksort we pick the last item in the
partition space as the pivot everytime. This can turn out very good
or very badly
*/
int pivot = arr[right];
/*
i will keep track of the "tail" of the section of items less than
the pivot so that at the end we can "sandwich" the pivot between the
section less than it and the section greater than it
*/
int i = left - 1;
/*
j will scan for us.
*/
for (int j = left; j < right; j++) {
/*
If this item is less than the pivot it needs to be moved to the section
of items less than the pivot
*/
if (arr[j] <= pivot) {
/*
Move i forward so that we can swap the value at j into the
tail of the items less than the pivot
*/
i++;
/*
Execute the swap. We "throw" the item at j back into the section
of items less than the pivot
*/
swap(arr, i, j);
}
}
/*
Swap the pivot value right after the section of items
less than the pivot. i keeps the tail of this section
*/
swap(arr, i + 1, right);
return i + 1; // Return the pivot's final resting position
}
private void swap(int[] arr, int first, int second) {
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
view raw Quicksort.java hosted with ❤ by GitHub