/
quick-sort.ts
54 lines (47 loc) · 1.15 KB
/
quick-sort.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
import { swapArrayItems } from "../../utils";
/**
* Quick sort algorithm
*
* @description
* Time complexity: Best O(n * log(n)); Avg O(n * log(n)); Worst O(n ^2)
* @description
* Memory complexity: Worst case: O(1)
*/
export const quickSort = (arr: Array<number>): Array<number> => {
const partition = (
arr: Array<number>,
leftIndex: number,
rightIndex: number
): number => {
const pivot = arr[leftIndex];
let leftWall = leftIndex;
let rightWall = rightIndex;
while (leftWall <= rightWall) {
while (arr[rightWall] > pivot) {
rightWall--;
}
while (arr[leftWall] < pivot) {
leftWall++;
}
if (leftWall <= rightWall) {
swapArrayItems(arr, leftWall, rightWall);
rightWall--;
leftWall++;
}
}
return leftWall;
};
const sort = (
arr: Array<number>,
leftIndex = 0,
rightIndex: number = arr.length - 1
): Array<number> => {
if (leftIndex < rightIndex) {
const pivot = partition(arr, leftIndex, rightIndex);
sort(arr, leftIndex, pivot - 1);
sort(arr, pivot, rightIndex);
}
return arr;
};
return sort(arr);
};