Medium Sorting
Quicksort
Receives an array of integers and sorts it in ascending order using quicksort, a divide-and-conquer algorithm. For each range it picks a pivot (the last element) and partitions the range so that every value smaller than the pivot ends up to its left and every larger-or-equal value to its right; the pivot then sits in its final sorted position. The two sides are sorted the same way recursively until every range has at most one element. Returns a new array with the values in ascending order.
Visualization
- Input
- Result
Algorithm code
// Quicksort — a single pure function. Receives an array of integers and
// returns a new array sorted in ascending order, using divide-and-conquer
// quicksort with Lomuto partitioning (the last element of each range is the
// pivot).
/**
* @param {number[]} arr - array of integers to sort
* @returns {number[]} a new array with the values in ascending order
*/
export function quickSort(arr) {
const result = [...arr];
sort(result, 0, result.length - 1);
return result;
}
function sort(arr, lo, hi) {
if (lo >= hi) {
return;
}
const pivotIndex = partition(arr, lo, hi);
sort(arr, lo, pivotIndex - 1);
sort(arr, pivotIndex + 1, hi);
}
function partition(arr, lo, hi) {
const pivot = arr[hi];
let boundary = lo;
for (let j = lo; j < hi; j += 1) {
if (arr[j] < pivot) {
swap(arr, boundary, j);
boundary += 1;
}
}
swap(arr, boundary, hi);
return boundary;
}
function swap(arr, a, b) {
const temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}FUNCTION quickSort(arr):
result ← copy(arr)
sort(result, 0, length(result) - 1)
RETURN result
FUNCTION sort(arr, lo, hi):
IF lo ≥ hi:
RETURN
pivotIndex ← partition(arr, lo, hi)
sort(arr, lo, pivotIndex - 1)
sort(arr, pivotIndex + 1, hi)
FUNCTION partition(arr, lo, hi):
pivot ← arr[hi]
boundary ← lo
FOR j ← lo TO hi - 1:
IF arr[j] < pivot:
swap(arr, boundary, j)
boundary ← boundary + 1
swap(arr, boundary, hi)
RETURN boundary
FUNCTION swap(arr, a, b):
temp ← arr[a]
arr[a] ← arr[b]
arr[b] ← temp