-
Notifications
You must be signed in to change notification settings - Fork 8
/
QuickSort.ts
96 lines (79 loc) · 2.83 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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
function swap(arr: number[], i: number, j: number): void {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
function partition(items: number[], left: number, right: number): number {
// Find the pivot by adding the two indexes together
// and dividing by two (the middle element, effectively).
const pivot = items[Math.floor((right + left) / 2)];
let l = left;
let r = right;
console.log('** pivot is: ', pivot);
console.log('** left is: ', items[left]);
console.log('** right is: ', items[right]);
// Once the left reference is greater than the right reference,
// we have finished sorting this set of items, and we can return.
while (l <= r) {
// If the left pointer is less than the pivot, increment it.
// In other words, move the pointer to the right.
while (items[l] < pivot) {
l++;
console.log('l is now pointing to: ', items[l]);
}
// If the right pointer is greater than the pivot, decrement it.
// In other words, move the pointer to the left.
while (items[r] > pivot) {
r--;
console.log('r is now pointing to: ', items[r]);
}
// If the left pointer is larger than the pivot, and the right
// pointer is not bigger than the pivot, swap the two elements.
if (l <= r) {
console.log('** now swapping l and r pointers: ', items[l], items[r]);
swap(items, l, r);
// After swapping, increment/decrement the pointers respectively.
l++;
r--;
// console.log('l is now pointing to: ', items[l]);
// console.log('r is now pointing to: ', items[r]);
}
}
// The left item becomes the new pivot element.
return l;
}
function quickSort(items, leftIndex = 0, rightIndex = items.length - 1) {
// Declare an index that will be our pivot reference.
var pivotIndex;
// If the array has only one item, it's already sorted!
// If it has no items, we don't want to try to sort it!
if (items.length > 1) {
// As long as the array has two items, we can parition it.
pivotIndex = partition(items, leftIndex, rightIndex);
console.log('** pivot is: ', items[pivotIndex]);
// If the left reference hasn't been incremented to
// reach the pivot yet, we want to keep comparing it.
if (leftIndex < pivotIndex - 1) {
quickSort(items, leftIndex, pivotIndex - 1);
}
// If the right reference hasn't reached the
// pivotIndex yet, we need to keep comparing it.
if (pivotIndex < rightIndex) {
quickSort(items, pivotIndex, rightIndex);
}
}
return items;
}
// console.log(quickSort([2, 1, 3, 5, 0]));
function partition(arr, lo, hi) {
const pivot = arr[hi];
let i = lo - 1;
for (let j = lo; j < hi; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
if (arr[hi] < arr[i + 1]) {
[arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
}
return i + 1;
}