Repository navigation
Expand file tree
/
Copy pathQuickSortRecursive.js
More file actions
65 lines (60 loc) · 2.16 KB
/
Copy pathQuickSortRecursive.js
File metadata and controls
65 lines (60 loc) · 2.16 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
/*
Quicksort is the most popular sorting algorithm and there have
lots of different implementations but the "recursive" or "Partition in place"
is one of the most efficient implementations below we have discussed how to
implement it.
Partition in place => "in place" Partition in place indicates that we
do not need any other space to store the auxiliary array and the term
"partition" denotes that we split the list into two parts one is less
than the pivot and the other is greater than the pivot and repeats this
process recursively and breaks the problem into sub-problems and makes
it singular so that the behavior or "divide and conquer" get involved
too.
Problem & Source of Explanation => https://www.cs.auckland.ac.nz/software/AlgAnim/qsort1a.html
*/
/**
* Partition in place QuickSort.
* @param {number[]} inputList list of values.
* @param {number} low lower index for partition.
* @param {number} high higher index for partition.
*/
const quickSort = (inputList, low, high) => {
if (!Array.isArray(inputList)) {
throw new TypeError('Please input a valid list or array.')
}
if (low < high) {
// get the partition index.
const pIndex = partition(inputList, low, high)
// recursively call the quickSort method again.
quickSort(inputList, low, pIndex - 1)
quickSort(inputList, pIndex + 1, high)
}
return inputList
}
/**
* Partition In Place method.
* @param {number[]} partitionList list for partitioning.
* @param {number} low lower index for partition.
* @param {number} high higher index for partition.
* @returns {number} `pIndex` pivot index value.
*/
const partition = (partitionList, low, high) => {
const pivot = partitionList[high]
let pIndex = low
for (let index = low; index <= high - 1; index++) {
if (partitionList[index] < pivot) {
// swap variables using array destructuring
;[partitionList[index], partitionList[pIndex]] = [
partitionList[pIndex],
partitionList[index]
]
pIndex += 1
}
}
;[partitionList[pIndex], partitionList[high]] = [
partitionList[high],
partitionList[pIndex]
]
return pIndex
}
export { quickSort }