Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs

Dashboard
Notifications
Mark all as read
Challenges

Generalized Sort

+2
−0

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!


  1. Incidentally, I generated this data with a short script ↩︎

Why does this post require moderator attention?
You might want to add some details to your flag.
Why should this post be closed?

1 comment thread

Questions (3 comments)

5 answers

+2
−0

Scala, 64 bytes

c=>_.sortBy(x=>c.map(_(x)))(math.Ordering.Implicits.seqOrdering)

Try it in Scastie!

A rather crude answer, but I'll come back later to golf it. It's rather simple, though - it simply sorts by the result of applying every comparator function to each of the elements.

Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

+1
−0

Japt -h, 5 bytes

Takes the array to be sorted as input and assigns the array of functions, in reverse order, to variable V.

V£=ñX

Try the names test case

I could save a byte by replacing with just n and tweaking the functions but doing it this way allows me to do something Japt isn't be able to do: work with objects! Each object is limited to maximum of 6 entries, though, and the keys must be one of E or P-T.

Try the objects test case


If that's not an acceptable way to take input of multiple black-box functions then:

Japt -h, 7 bytes

Taking an array of the string representations of the functions as the second input.

V£=ñOvX

Try the names test case
Try the objects test case

Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

+1
−0

JavaScript (Node.js), 52 bytes

(A,...c)=>A.sort((a,b)=>c.map(z=>z(a,b)).find(x=>x))

Try it online!

A golf of the reference code.

If we can assume there will be no ties, 47 is possible in a rather neat way.

Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

+1
−0

Haskell, 29 bytes

import Data.List
foldr sortBy

Try it online!

Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

+0
−0

JavaScript, 25 bytes

Arguments are curried, i.e. f(a)(s), where a is the array to be sorted and s is an array of functions to sort by, in reverse order. Modifies a in place, which I don't know that we have a consensus on here yet - if it's not permitted then add &&a to the end to return the sorted array.

a=>s=>s.map(g=>a.sort(g))

Try it online!

Why does this post require moderator attention?
You might want to add some details to your flag.

1 comment thread

Modifying in-place (1 comment)

Sign up to answer this question »

This community is part of the Codidact network. We have other communities too — take a look!

You can also join us in chat!

Want to advertise this community? Use our templates!