-
Notifications
You must be signed in to change notification settings - Fork 118
/
quick-sort.js
33 lines (25 loc) · 965 Bytes
/
quick-sort.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Quick sort
// Quick sort is an O(n * log(n)) algorithm (Worst case - O(n^2).
// Pivot is always the first element
function pivot(arr, start = 0, end = arr.length - 1) {
let pivotIndex = start;
for (let i = start + 1; i <= end; i++) {
if (arr[start] > arr[i]) {
pivotIndex++;
[arr[i], arr[pivotIndex]] = [arr[pivotIndex], arr[i]];
}
}
if (pivotIndex !== start) [arr[pivotIndex], arr[start]] = [arr[start], arr[pivotIndex]];
return pivotIndex;
}
function quickSort(arr, start = 0, end = arr.length - 1) {
if (start < end) {
const pivotIndex = pivot(arr, start, end);
quickSort(arr, start, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, end);
}
return arr;
}
const nums = [4, 3, 5, 3, 43, 232, 4, 34, 232, 32, 4, 35, 34, 23, 2, 453, 546, 75, 67, 4342, 32];
console.log(quickSort(nums)); // [2, 3, 3, 4, 4, 4, 5, 23, 32, 32, 34, 34, 35, 43, 67, 75, 232, 232, 453, 546, 4342]
console.log(quickSort([])); // []