2021-10-07 09:03:38 +02:00
|
|
|
/**
|
2021-11-27 16:50:09 +05:30
|
|
|
* @function QuickSort
|
|
|
|
|
* @description Quick sort is a comparison sorting algorithm that uses a divide and conquer strategy.
|
|
|
|
|
* @param {Integer[]} items - Array of integers
|
|
|
|
|
* @return {Integer[]} - Sorted array.
|
|
|
|
|
* @see [QuickSort](https://en.wikipedia.org/wiki/Quicksort)
|
|
|
|
|
*/
|
|
|
|
|
function quickSort (items) {
|
2021-05-21 11:16:11 +05:30
|
|
|
const length = items.length
|
2017-09-29 21:34:28 +02:00
|
|
|
|
|
|
|
|
if (length <= 1) {
|
2020-05-03 09:05:12 +02:00
|
|
|
return items
|
2017-09-29 21:34:28 +02:00
|
|
|
}
|
2021-05-21 11:16:11 +05:30
|
|
|
const PIVOT = items[0]
|
|
|
|
|
const GREATER = []
|
|
|
|
|
const LESSER = []
|
2017-09-29 21:34:28 +02:00
|
|
|
|
2021-05-21 11:16:11 +05:30
|
|
|
for (let i = 1; i < length; i++) {
|
2017-09-29 21:34:28 +02:00
|
|
|
if (items[i] > PIVOT) {
|
2020-05-03 09:05:12 +02:00
|
|
|
GREATER.push(items[i])
|
2017-09-29 21:34:28 +02:00
|
|
|
} else {
|
2020-05-03 09:05:12 +02:00
|
|
|
LESSER.push(items[i])
|
2017-09-29 21:34:28 +02:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2021-11-27 16:50:09 +05:30
|
|
|
const sorted = [...quickSort(LESSER), PIVOT, ...quickSort(GREATER)]
|
2020-05-03 09:05:12 +02:00
|
|
|
return sorted
|
2017-09-29 21:34:28 +02:00
|
|
|
}
|
2021-11-27 16:50:09 +05:30
|
|
|
|
|
|
|
|
export { quickSort }
|
