Skip to content

Instantly share code, notes, and snippets.

@gladchinda
Last active May 13, 2022 10:28
Show Gist options
  • Save gladchinda/81cce517c76412db89e325a452fcaa3d to your computer and use it in GitHub Desktop.
Save gladchinda/81cce517c76412db89e325a452fcaa3d to your computer and use it in GitHub Desktop.
Three-way partitioning algorithm with ranking function (for JavaScript)
const __valueranking__ = (minvalue, maxvalue = minvalue) => {
if (maxvalue < minvalue) {
const temp = minvalue;
minvalue = maxvalue;
maxvalue = temp;
}
return (value) => +(value >= minvalue ? value > maxvalue : -1);
};
const __reverseranking__ = (rankingfn) => (value) => -rankingfn(value);
const __swap__ = (arr, idx1, idx2) => {
const temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
};
const Ranking = Object.create(null, {
reverse: { value: __reverseranking__ },
value: { value: __valueranking__ }
});
const threewaypartition = (arr, rankingfn) => {
let i = 0, j = 0, k = arr.length - 1;
while (j <= k) {
const rank = rankingfn(arr[j]);
if (rank === 0) { j++; continue; }
rank < 0 ? __swap__(arr, i++, j++) : __swap__(arr, k--, j);
}
return [i, k];
};
export { Ranking };
export default threewaypartition;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment