Implementation of Quick Sort
Quick Sort can be implemented using two functions described below:
- partition(Array, startIndex, lastIndex)
- quick_sort(Array, startIndex, lastIndex)
Here, in the partition
function, we are dividing the array based upon the selected pivot. In the quick_sort
function, we are re-arranging the elements.
xxxxxxxxxx
44
console.log(quickSort(nums, 0, nums.length - 1))
function partition(arr, low, high) {
let lowIdx = low - 1;
let pivot = arr[high]; // pivot
​
for (let j = low; j < high; j++) {
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot) {
// Increment index of left/smaller element
lowIdx = lowIdx + 1;
// Swap
const temp = arr[lowIdx];
arr[lowIdx] = arr[j];
arr[j] = temp;
}
}
​
const temp = arr[lowIdx + 1];
arr[lowIdx + 1] = arr[high];
arr[high] = temp;
​
return lowIdx + 1
}
​
function quickSort(arr, low, high) {
if (arr.length === 1) {
// Base case
return arr;
}
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment