Quick Sort
Description
The quick sort algorith uses a pivot element as reference to order the array. The basic idea is that we grab a random pivot element from the array, and we make an array with all the elements that are lower that the pivot and an array with the elements that are higher than the pivot. We repeat this with all the sub arrays until it's comppletly ordered.
1. Verbose implmentation
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const quickSort = (array: number[]): number[] => {
if(array.length < 2) {
return array;
}
const pivot = array.shift();
const leftArray: number[] = [];
const rightArray: number[] = [];
while(array.length) {
const element = array.shift();
if(element && pivot) {
if(element < pivot) {
leftArray.push(element);
} else {
rightArray.push(element);
}
}
}
if(pivot)
return [...quickSort(leftArray), pivot, ...quickSort(rightArray)];
else
return [...quickSort(leftArray), ...quickSort(rightArray)];
};
1. Minimal implmentation
0
1
2
3
4
5
6
7
const mQuickSort = (array: number[]): number[] => {
if(array.length < 2) return array; // if the array is only 1, it's ordered
const [pivot, ...rest] = array; // grab first element as pivot and the rest of the array
const left = rest.filter(element => element <= pivot); // get the left elements
const right = rest.filter(element => element > pivot); // get the right elements
return [...mQuickSort(left), pivot, ...mQuickSort(right)]; // iterate and create the array
}