Challenge

We all know and love the generic sort function, right? However, it only sorts based off one criterion - what if we want more? That's where you come in.

Your task is to sort an array based off an arbitrary number of comparison functions c1, c2, c3, etc.; first sort by comparing using c1, if there is a tie then sort by c2, if there is still a tie sort by c3, etc. If there are a set of items that are still tied after all comparisons are made, the order of them with respect to each other can be implemented however you like (including an unstable sort). However, their order with respect to others must be correct. For instance, say we are sorting only using the x property of a list of objects, and we are given an input of

[ { x: 1, y: 2 },
  { x: 2, y: 1 },
  { x: 1, y: 1 } ]

You may output either of

[ { x: 1, y: 2 },
  { x: 1, y: 1 },
  { x: 2, y: 1 } ]

or

[ { x: 1, y: 1 },
  { x: 1, y: 2 },
  { x: 2, y: 1 } ]

Input

You may take input in any format that makes sense, e.g. as an array of functions in either precedence order and the array to sort.

Example

Here is an example in JavaScript:

function sort(array, ...comparators) {
	return array.sort((a, b) =>
		comparators.map(c => c(a, b)) // Apply comparisons
		           .find(r => r != 0)  // Find the first non-zero comparison
	);
}

Try it online!

Test Cases

Here is a test case, sorting first by last name then by first name.^[1]

Christina Johnson
Steward Johnson
Steward White
Steward O'Brian
Steward Smith
Bill Smith
John Johnson
James Smith
Sally Johnson
Christina Meyers
Chris Meyers
Steward Meyers
Bill O'Brian
Zachary Smith
Chris Brown
Zachary O'Brian
Abbey Smith
Zachary Meyers
John Brown
Sally Smith
Zachary Johnson
Chris White

=>

Chris Brown
John Brown
Christina Johnson
John Johnson
Sally Johnson
Steward Johnson
Zachary Johnson
Chris Meyers
Christina Meyers
Steward Meyers
Zachary Meyers
Bill O'Brian
Steward O'Brian
Zachary O'Brian
Abbey Smith
Bill Smith
James Smith
Sally Smith
Steward Smith
Zachary Smith
Chris White
Steward White

Here is another test case sorting first by the x property, then the y property, then the z property:

Comparators:
c1 = (a, b) => a.x - b.x
c2 = (a, b) => a.y - b.y
c3 = (a, b) => a.z - b.z

Input: 
[ { x: 1, y: 2, z: 2 },
  { x: 3, y: 2, z: 3 },
  { x: 2, y: 2, z: 3 },
  { x: 1, y: 1, z: 3 },
  { x: 2, y: 2, z: 1 },
  { x: 1, y: 2, z: 1 },
  { x: 1, y: 2, z: 3 } ]

Output:
[ { x: 1, y: 1, z: 3 },
  { x: 1, y: 2, z: 1 },
  { x: 1, y: 2, z: 2 },
  { x: 1, y: 2, z: 3 },
  { x: 2, y: 2, z: 1 },
  { x: 2, y: 2, z: 3 },
  { x: 3, y: 2, z: 3 } ]

This is code-golf, so the entry with the lowest bytes wins!

posted over 3 years ago

CC BY-SA 4.0

3y ago

Moshi‭

1722 reputation 17 58 204 80