Skip to content

Instantly share code, notes, and snippets.

@ungarson
Created February 5, 2019 13:29
Show Gist options
  • Save ungarson/d49ee28f489d6e5eb07a1089d918b470 to your computer and use it in GitHub Desktop.
Save ungarson/d49ee28f489d6e5eb07a1089d918b470 to your computer and use it in GitHub Desktop.
Quick sort in javascript
function arr_union(arr1, arr2) {
return arr1.concat(arr2);
}
function quicksort(array) {
let pivot = 0;
let compared = array.length - 1;
if (array.length <= 1) return array;
while (true) {
if (array[pivot] > array[compared]) {
if (compared > pivot) {
[array[pivot], array[compared]] = [array[compared], array[pivot]]; // swaping
[pivot, compared] = [compared, pivot + 1]; // swaping but compared = pivot + 1
} else compared += 1;
} else if (array[pivot] < array[compared]){
if (pivot > compared) {
[array[pivot], array[compared]] = [array[compared], array[pivot]]; // swaping
[pivot, compared] = [compared, pivot - 1]; // swaping but compared = pivot - 1
} else compared -= 1;
} else {
if (pivot > compared) compared += 1;
else if (compared > pivot) compared -= 1;
}
if (compared == pivot) break;
}
// if array[0] is already the smallest number
if (pivot === 0) return arr_union(array.slice(0, 1), quicksort(array.slice(1)));
// and if it's not the smallest
else return arr_union(quicksort(array.slice(0, pivot)), quicksort(array.slice(pivot)));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment