Skip to content

Instantly share code, notes, and snippets.

@tylerneylon
Created April 29, 2023 21:15
Show Gist options
  • Save tylerneylon/4d0b628bba4149518f76b23cb4d4d296 to your computer and use it in GitHub Desktop.
Save tylerneylon/4d0b628bba4149518f76b23cb4d4d296 to your computer and use it in GitHub Desktop.
Sort an array using a partial order, ie, using a cmp() function which may return "not sure" as an answer.
// The inputArr is an array of any kind of values.
// The inputCmp() function accepts two values, x and y; with the return
// value indicating the relationship as such:
//
// If: then cmp(x, y) returns:
// x < y '<'
// x > y '>'
// x = y '='
// x ? y null
//
// This breaks precendent with the cmp interface in other settings, such
// as the compareFn() used by Array.sort(), but I find this interface to
// be much more intuitive.
//
// The inputCmp() function is internally memoized since it may be expensive,
// and otherwise we would call it redundantly.
function sortWithPartialOrder(inputArr, inputCmp) {
// 1. Set up memoization for inputCmp().
let objectIdCounter = 0;
const objectIdMap = new Map();
function objectId(obj) {
if (!objectIdMap.has(obj)) {
objectIdMap.set(obj, ++objectIdCounter);
}
return objectIdMap.get(obj);
}
const cache = new Map();
function cmp(a, b) {
let [aId, bId] = [objectId(a), objectId(b)];
let key = aId + ':' + bId;
if (cache.has(key)) return cache.get(key);
let result = inputCmp(a, b);
cache.set(key, result);
let newKey = bId + ':' + aId;
let newResult = result;
if (result === '<') newResult = '>';
if (result === '>') newResult = '<';
cache.set(newKey, newResult);
return result;
}
// 2. Sort `arr`, using the memoized comparison function cmp().
let arr = [...inputArr]; // Make a copy that we can modify.
let sorted = [];
while (arr.length > 0) {
// Ensure the first element in `arr` is minimal.
while (true) {
let didChange = false;
for (let i in arr) {
if (cmp(arr[0], arr[i]) == '>') {
didChange = true;
arr.unshift(...arr.splice(i, 1));
}
}
if (!didChange) break;
}
// Append that to `sorted`.
sorted.push(...arr.splice(0, 1));
}
return sorted;
}
@tylerneylon
Copy link
Author

I created this gist as a first pass, and then realized a couple things:

  • The problem I'm solving is not strictly about what a mathematician would call a "partial order" because I'm not assuming that the user-given comparison function is transitively closed. I am assuming it is internally consistent, but, for example, it's ok with me if inputCmp() reports that a < b and b < c but then says a ? c. In a sense, this problem is harder to solve because I'm given less information and have to use less structured clues.
  • The code can be more efficient. This code is a little like bubble sort. In particular, this code does not try so hard to reuse previously known comparisons.

With those two things in mind, I created an updated version of this algorithm here.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment