Skip to content

Instantly share code, notes, and snippets.

@tylerneylon
Last active May 22, 2023 22:45
Show Gist options
  • Save tylerneylon/3d0ac206bc9036882f180bb17ee05241 to your computer and use it in GitHub Desktop.
Save tylerneylon/3d0ac206bc9036882f180bb17ee05241 to your computer and use it in GitHub Desktop.
Sort an array based on a comparison function that can say "order is flexible" for some pairs.
// This will sort the values in `inputArr` according to the comparison data
// provided by calls to `inputCmp()`, which is expected to return the values '='
// (a string), '<', '>', or null; where a null indicates that the comparison
// value is undetermined, and that those two elements may go in any order.
// This function attempts to reduce the number of calls to inputCmp() in several
// ways:
// * It memorizes given return values.
// * It assumes that if a < b then also b > a (otherwise what is happening?).
// * It builds a tree to infer transitive comparisons, and tries to maximize
// the use of that tree.
export function sortWithPartialInfo(inputArr, inputCmp) {
// 1. Set up memoization for inputCmp().
// This serves to both memorize results as well as to allow us to treat the
// input as an array of integers, although inputArr may have any types.
const cache = {};
function cmp(a, b) {
let key = a + ':' + b;
let val = cache[key];
if (val !== undefined) return val;
let result = (a === b) ? '=' : inputCmp(inputArr[a], inputArr[b]);
cache[key] = result;
let otherKey = b + ':' + a;
let otherResult = result;
if (result === '<') otherResult = '>';
if (result === '>') otherResult = '<';
cache[otherKey] = otherResult;
return result;
}
// 2. Sort `arr`, using the memoized comparison function cmp().
let arr = inputArr.map((e, i) => i);
let sorted = [];
let min = arr[arr.length - 1];
let cmpTree = {[min]: []}
while (arr.length > 0) {
let xIdx = -1;
while (true) {
xIdx++;
if (xIdx == arr.length) {
sorted.push(min);
arr.splice(arr.indexOf(min), 1);
for (let i = 1; i < cmpTree[min].length; i++) {
delete cmpTree[cmpTree[min][i]];
}
min = cmpTree[min][0];
// If the order is not fully determined, cmpTree could be empty
// yet we may still have elements left in arr.
if (min === undefined && arr.length > 0) {
min = arr[arr.length - 1];
cmpTree[min] = [];
}
break;
}
let x = arr[xIdx];
if (x in cmpTree) continue;
let c = cmp(x, min);
if (c === '>') {
cmpTree[min].push(x);
cmpTree[x] = [];
}
if (c === '<') {
cmpTree[x] = [min];
min = x;
xIdx = -1;
}
}
}
return sorted;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment