Select Git revision
kthSmallest.js
kthSmallest.js 825 B
import { View } from './view.js';
function partition(sequence) {
console.assert(sequence.length > 0, 'Tried to partition an empty sequence.');
const pivot = sequence[0];
let i = 1;
let j = sequence.length - 1;
while (i !== 0) {
while (i < sequence.length && sequence[i] <= pivot) {
++i;
}
while (j > 0 && sequence[j] >= pivot) {
--j;
}
if (i >= j) {
i = 0;
}
const swap = sequence[i];
sequence[i] = sequence[j];
sequence[j] = swap;
}
return [
new View(sequence, 0, j),
sequence[j],
new View(sequence, j + 1, sequence.length),
];
}
export function kthSmallest(sequence, k) {
console.assert(
k >= 0 && k < sequence.length,
'Tried to find the kth smallest element when k is out of bounds.',
);
return sequence[0]; // TODO: stub
}