This repository has been archived by the owner on Dec 12, 2023. It is now read-only.
-
-
Notifications
You must be signed in to change notification settings - Fork 0
/
QuickSortInPlace.js
76 lines (67 loc) · 2.62 KB
/
QuickSortInPlace.js
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
import Sort from '../Sort';
export default class QuickSortInPlace extends Sort {
/** Sorting in place avoids unnecessary use of additional memory, but modifies input array.
*
* This process is difficult to describe, but much clearer with a visualization:
* @see: http://www.algomation.com/algorithm/quick-sort-visualization
*
* @param {*[]} originalArray
* @param {number} inputLowIndex
* @param {number} inputHighIndex
* @return {*[]}
*/
sort(originalArray, inputLowIndex, inputHighIndex) {
// Destructures array on initial passthrough, and then sorts in place.
const array = inputLowIndex === undefined ? [...originalArray] : originalArray;
/**
* Partition array segment and return index of last swap
*
* @param {number} lowIndex
* @param {number} highIndex
* @return {number}
*/
const partition = (lowIndex, highIndex) => {
/**
* @param {number} leftIndex
* @param {number} rightIndex
*/
const swap = (leftIndex, rightIndex) => {
const tempVariable = array[leftIndex];
array[leftIndex] = array[rightIndex];
array[rightIndex] = tempVariable;
};
const pivot = array[highIndex];
this.callbacks.visitingCallback(array[pivot]);
let firstRunner = lowIndex - 1;
for (let secondRunner = lowIndex; secondRunner < highIndex; secondRunner += 1) {
if (this.comparator.lessThan(array[secondRunner], pivot)) {
firstRunner += 1;
swap(firstRunner, secondRunner);
}
}
if (this.comparator.lessThan(pivot, array[firstRunner + 1])) {
swap(firstRunner + 1, highIndex);
}
return firstRunner + 1;
};
/*
* While we can use a default parameter to set `low` to 0, we would
* still have to set `high`'s default within the function as we
* don't have access to `array.length - 1` when declaring paramaters
*/
const lowIndex = inputLowIndex === undefined ? 0 : inputLowIndex;
const highIndex = inputHighIndex === undefined ? array.length - 1 : inputHighIndex;
// Base case is when low and high converge
if (lowIndex < highIndex) {
const partitionIndex = partition(lowIndex, highIndex);
/*
* `partition()` swaps elements of the array based on their comparison to the `hi` parameter,
* and then returns the index where swapping is no longer necessary, which can be best thought
* of as the pivot used to split an array in a non-in-place quicksort
*/
this.sort(array, lowIndex, partitionIndex - 1);
this.sort(array, partitionIndex + 1, highIndex);
}
return array;
}
}