-
Notifications
You must be signed in to change notification settings - Fork 0
/
quickSort.ts
59 lines (48 loc) · 1.42 KB
/
quickSort.ts
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import { swap } from "../helpers";
function partition(
items: number[],
lowIndex: number,
highIndex: number,
): number {
// both lowIndex and highIndex are inclusive
const pivot = items[highIndex];
let index = lowIndex;
for (let i = lowIndex; i <= highIndex - 1; i++) {
if (items[i] <= pivot) {
// Found an array item less than or equal to the pivot value
// This item must be placed at the left of the pivot
swap(items, index, i);
index++;
}
}
// put the pivot in the right place
swap(items, index, highIndex);
// return the pivot place
return index;
}
function sortSubArray(
items: number[],
lowIndex: number,
highIndex: number,
): void {
// base case is sorting an empty array or an array of length 1
if (lowIndex >= highIndex) {
return; // in the base case the array is already sorted
}
// recursive case
const pivotIndex = partition(items, lowIndex, highIndex);
// sort the sub array before the pivot
sortSubArray(items, lowIndex, pivotIndex - 1);
// sort the sub array after the pivot
sortSubArray(items, pivotIndex + 1, highIndex);
}
/**
* Sorts the provided array in place, by applying the quick sort algorithm.
* @param { number[] } items - The array to be sorted
*/
function quickSort(items: number[]): void {
const lowIndex = 0;
const highIndex = items.length - 1;
sortSubArray(items, lowIndex, highIndex);
}
export default quickSort;