Skip to content

Instantly share code, notes, and snippets.

@iiison
Created June 16, 2020 08:28
Show Gist options
  • Save iiison/022c1dadd1183e68a92cf6b7429824c3 to your computer and use it in GitHub Desktop.
Save iiison/022c1dadd1183e68a92cf6b7429824c3 to your computer and use it in GitHub Desktop.
basic quicksort implementation in JavaScript
function qs(arr, lf = 0, rt) {
function swap(ix1, ix2){
var temp = arr[ix1]
arr[ix1] = arr[ix2]
arr[ix2] = temp
}
rt = rt || arr.length - 1;
if (rt - lf === 1) {
if (arr[rt] < arr[lf]) {
swap(rt, lf)
}
return arr
}
var pvt = arr[Math.round((lf + rt) / 2)];
for(var i = lf, j = rt; i <= j;) {
for (;pvt > arr[i];){
i++
}
for (;pvt < arr[j];){
j--
}
if (i <= j) {
swap(i, j);
i++;
j--;
}
}
if (lf < i - 1) {
qs(arr, lf, i - 1)
}
if (rt > i) {
qs(arr, i, rt)
}
return arr
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment