Created
October 8, 2021 20:07
-
-
Save misterpoloy/f7bf14644536797087c9c15c34c41516 to your computer and use it in GitHub Desktop.
Quick Sort implementation recursive in Javascript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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