Skip to content

Instantly share code, notes, and snippets.

@misterpoloy
Created October 8, 2021 20:07
Show Gist options
  • Save misterpoloy/f7bf14644536797087c9c15c34c41516 to your computer and use it in GitHub Desktop.
Save misterpoloy/f7bf14644536797087c9c15c34c41516 to your computer and use it in GitHub Desktop.
Quick Sort implementation recursive in Javascript
function swap(idxA, idxB, array) {
const temp = array[idxA]
array[idxA] = array[idxB]
array[idxB] = temp
}
// A startIdx will search for elements greather than pivor
// B endIdx will search for elements less than pivor
function quickSortHelper(startIdx, endIdx, array) {
if (startIdx >= endIdx) return // Remember or EQUAL
let pivotIdx = startIdx
let leftIdx = startIdx + 1
let rightIdx = endIdx
while (rightIdx >= leftIdx) { // Remember EQUAL
if (array[leftIdx] > array[pivotIdx] && array[rightIdx] < array[pivotIdx]) {
swap(leftIdx, rightIdx, array)
}
// here is the key part to make sense of the next swap (*)
if (array[leftIdx] <= array[pivotIdx]) leftIdx++
if (array[rightIdx] >= array[pivotIdx]) rightIdx--
}
// (*)
swap(pivotIdx, rightIdx, array)
// rightIdx now contains the pivot value and trusted 1th balanced
const leftSide = rightIdx - 1 - startIdx //
const rightSide = endIdx - (rightIdx + 1)
const isLeftSmaller = leftSide < rightSide
if (isLeftSmaller) {
quickSortHelper(startIdx, rightIdx - 1, array)
quickSortHelper(rightIdx + 1, endIdx, array)
} else {
quickSortHelper(rightIdx + 1, endIdx, array)
quickSortHelper(startIdx, rightIdx - 1, array)
}
}
// Divide an conqueer algorithm
function quickSort(array) {
quickSortHelper(0, array.length - 1, array)
return array
}
// Do not edit the line below.
exports.quickSort = quickSort;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment