Skip to content

Instantly share code, notes, and snippets.

@shuboc shuboc/quick-select.js Secret
Last active Mar 18, 2019

Embed
What would you like to do?
function quickSelect(arr, left, right, k) {
if (left === right) {
return arr[left];
}
const pivotIdx = partition(arr, left, right);
if (pivotIdx === k) {
return arr[k];
} else if (k < pivotIdx) {
return quickSelect(arr, left, pivotIdx - 1);
} else {
return quickSelect(arr, pivotIdx + 1, right, k)
}
}
function partition(arr, start, end) {
const pivot = arr[end];
let nextLeftIdx = start;
for (let i = start; i < end; ++i) {
if (arr[i] < pivot) {
swap(arr, nextLeftIdx, i);
nextLeftIdx++;
}
}
swap(arr, nextLeftIdx, end);
return nextLeftIdx;
}
function swap(arr, i, j) {
const tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
const arr = [9, 4, 1, 6, 7, 3, 8, 2, 5];
quickSelect(arr, 0, arr.length - 1, 4); // 5
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.