/*

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 }