Repository navigation
Expand file tree
/
Copy pathquick-sort.js
More file actions
65 lines (56 loc) · 1.51 KB
/
Copy pathquick-sort.js
File metadata and controls
65 lines (56 loc) · 1.51 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
const { swap } = require('./sorting-common');
// tag::partition[]
/**
* Linear-time Partitioning
* Chooses a pivot and re-arrage the array that
* everything on the left is <= pivot and
* everything on the right is > pivot
*
* Runtime: O(n)
* @param {*} array
* @param {*} low start index
* @param {*} high end index
* @returns {integer} pivot index
*/
function partition(array, low, high) {
const pivotInitialIndex = high; // <1>
let pivotIndex = low; // <2>
for (let current = low; current < high; current += 1) { // <3>
if (array[current] <= array[pivotInitialIndex]) { // <4>
swap(array, current, pivotIndex);
pivotIndex += 1;
}
}
swap(array, pivotInitialIndex, pivotIndex);
return pivotIndex;
}
// end::partition[]
// tag::quickSort[]
/**
* QuickSort - Efficient in-place recursive sorting algorithm.
* Avg. Runtime: O(n log n) | Worst: O(n^2)
* @param {*} array
* @param {*} low
* @param {*} high
*/
function quickSort(array, low = 0, high = array.length - 1) {
if (low < high) { // <4>
const partitionIndex = partition(array, low, high); // <1>
quickSort(array, low, partitionIndex - 1); // <2>
quickSort(array, partitionIndex + 1, high); // <3>
}
return array;
}
// end::quickSort[]
// tag::sort[]
/**
* Quick sort
* Runtime: O(n log n)
* @param {Array|Set} collection elements to be sorted
*/
function quickSortWrapper(collection) {
const array = Array.from(collection); // <1>
return quickSort(array);
}
// end::sort[]
module.exports = quickSortWrapper;