Quicksort, a Divide and Conquer Sorting Algorithm.
Quicksort is an efficient divide-and-conquer sorting algorithm.
We pick a pivot from the array to be sorted. We can pick at random, or choose the beginning, midpoint, or endpoint. In this case, we choose the midpoint, Math.floor((left+right)/2).
Now that we have a pivot, we sort all elements in the array into two groups: one group of elements less than the pivot, and one group of elements greater than the pivot.
We do this with a partition function that:
- Swaps the pivot to the front of the array
- Iterates from left-to-right (
i++) and right-to-left (j--) through the array.
- When arr[i] > pivot, we stop, saving position
i. - When arr[j] < pivot, we stop, saving position
j. We swap positionsiandj, since they are out of place with respect to the pivot.
When j>i, all of the elements are ordered with respect to the pivot (smaller to the left, larger to the right).
We can now swap the pivot back into the middle of the array and return the index of the pivot.
Quicksort uses this index to recursively sort the smaller & larger subarrays using partition.
We initially invoke qSort like this: qSort(arr, 0, arr.length-1). As the array reaches its sorted state, the left and right indices grow closer together. When the left index is greater than or equal to the right index, we know the array is sorted, because the pivot is already put in its proper place, and the lengths of the unsorted subarrays on either side of the pivot are zero.
function qSort(arr, left, right) {
if (left >= right) {
return;
}
let pivot = partition(arr, left, right);
qSort(arr, left, pivot - 1);
qSort(arr, pivot + 1, right);
return arr;
}
function partition(arr, left, right) {
const swap = (a, b) => {
let temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
};
let mid = Math.floor((right + left) / 2);
let pivot = arr[mid];
swap(mid, left);
let i = left + 1;
let j = right;
while (i <= j) {
while (i <= j && arr[i] <= pivot) {
i++;
}
while (i <= j && arr[j] > pivot) {
j--;
}
if (i < j) {
swap(i, j);
}
}
swap(i - 1, left);
return i - 1;
}