-
Notifications
You must be signed in to change notification settings - Fork 0
/
quickSort.js
67 lines (54 loc) · 1.76 KB
/
quickSort.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
// find a pivot (the left most element)
// two sentinels (left, right)
// sentinels start to move toward each other
// left sentinel will look for number that is larger than pivot
// right sentinel will look for number is smaller than pivot
// right sentinel moves first towards the left, if sh/e meet a number, stop
// left sentinel moves now towards the right, if sh/e meet a number, stop
// if left sentinel finds a number and right sentinel also finds one
// swap
// when the left sentinel meets the right sentinel at indexX
// swap the pivot with the number at IndexX
// divide the problem into smaller ones: a left chunk and right chunk
// repeat the above action for the left half
// repeat the above action for the right half
function helper(arr, left, right) {
if (left >= right) {
return;
}
const pivot = arr[left]
const leftBoundary = left //pivot
const rightBoundary = right
// right sentinel moves first towards the left
// if sh/e meet a number that is smaller than pivot, stop
while (left < right) {
while(left < right && arr[right] >= pivot ) {
right--
}
// stops if left = right or arrCopy(right) <= pivot
while(left < right && arr[left] <= pivot) {
left++
}
if (left < right) {
swapEleInArr(arr, left, right)
}
}
swapEleInArr(arr, leftBoundary, right)
helper(arr, leftBoundary, left - 1)
helper(arr,left + 1, rightBoundary)
}
function quickSort (arr) {
if(!Array.isArray(arr)) return []
const arrCopy = arr.slice()
let leftIdx = 0;
let rightIdx = arrCopy.length -1;
helper(arrCopy, leftIdx, rightIdx)
return arrCopy
}
//It's not a pure function
function swapEleInArr(arr, idxA, idxB){
const temp = arr[idxA]
arr[idxA] = arr[idxB]
arr[idxB] = temp
}
module.exports = quickSort;