Repository navigation
Expand file tree
/
Copy pathquick.mjs
More file actions
83 lines (69 loc) · 2.05 KB
/
Copy pathquick.mjs
File metadata and controls
83 lines (69 loc) · 2.05 KB
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
// a slightly modified version of:
// https://raw.github.com/nzakas/computer-science-in-javascript/master/algorithms/sorting/quicksort/quicksort.js
export default function quick(AS) {
const partition = function (left, right) {
const pivotIndex = Math.floor((right + left) / 2);
const pivotValue = AS.get(pivotIndex);
let i = left;
let j = right;
AS.clearHighlight();
AS.play(i, j);
AS.mark(i, j);
AS.highlight(i, j, pivotIndex);
// while the two indices don't match
while (i <= j) {
// if the item on the left is less than the pivot, continue right
while (AS.lt(AS.get(i), pivotValue)) {
AS.play(i, j);
AS.mark(i, j);
i++;
}
// if the item on the right is greater than the pivot, continue left
while (AS.gt(AS.get(j), pivotValue)) {
AS.play(i, j);
AS.mark(i, j);
j--;
}
// if the two indices still don't match, swap the values
if (i <= j) {
AS.play(i, j);
AS.mark(i, j);
AS.swap(i, j);
// change indices to continue loop
i++;
j--;
}
}
AS.clearHighlight();
// this value is necessary for recursion
return i;
};
const quickSort = function (left, right) {
const len = AS.length();
// performance - don't sort an array with zero or one items
if (len > 1) {
// fix left and right values - might not be provided
left = typeof left !== "number" ? 0 : left;
right = typeof right !== "number" ? len - 1 : right;
AS.mark(left, right);
// split up the entire array
const index = partition(left, right);
// if the returned index
if (left < index - 1) {
quickSort(left, index - 1);
}
if (index < right) {
quickSort(index, right);
}
}
};
quickSort();
}
quick.display = "Quick";
quick.stable = false;
quick.best = "nlogn";
quick.average = "nlogn";
quick.worst = "n^2";
// Worst-case auxiliary stack space; balanced partitions use O(log n).
quick.memory = "n";
quick.method = "exchanging";