# How to sort list of mixed types of elements with each type a specified canonical order?

For example, here is a list

{{1, "u"}, {6, "d"}, {3, "u"}, {4, "d"}, {2, "u"}, {5, "u"}, {3,
"d"}, {1, "d"}, {4, "u"}, {2, "d"}, {5, "d"}, {6, "u"}}


The default canonical order for integer is 1,2,3,4

The default canonical order for letters is a,b,c,d,

But now I want to sort this list according to canonical integer order while "u" should be ordered before "d", how to achieve this easily?

The example list I gave here has a good structure, so can be solved with specific tricks. But the problem is general. How to sort list of mixed types of elements with each type a specified canonical order?

• I'd define a function which assigns appropriate "weights" to elements then use SortBy or KeySortBy after casting the List as an Association (which I expect is faster, but haven't verified empirically). – IPoiler Nov 2 '15 at 2:39
• SortBy[list, {First, Switch[#[[2]], "u", -1, "d", 1] &}] for your particular example works. – J. M.'s ennui Nov 2 '15 at 2:57
• Will your real world usage always only be "u" and "d" or will it be other letters of the alphabet? – Mike Honeychurch Nov 2 '15 at 5:07
• Are you by any chance building a Wick Contraction generator? – evanb Nov 3 '15 at 0:53
• @MikeHoneychurch other letter is possible, and even strings, they serve as labels – matheorem Nov 3 '15 at 0:57

SortBy[l, {First@#, -ToCharacterCode@Last@#} &]
(*{{1, "u"}, {1, "d"}, {2, "u"}, {2, "d"}, {3, "u"}, {3, "d"}, {4,
"u"}, {4, "d"}, {5, "u"}, {5, "d"}, {6, "u"}, {6, "d"}}*)


Or the same, but slightly shorter code

SortBy[l, {#, -ToCharacterCode@#2} &@@#&]


Edit

The following uses the same sorting strategy but is much faster (by using this):

fns = {1000 # &, ToCharacterCode@# &};

• using ToCharacterCode! upvote – matheorem Nov 2 '15 at 4:48

A simple approach giving the requested result is

SortBy[list, (#[[2]] /. {"u" -> 0, "d" -> 1}) + 100 #[[1]] &]
(* {{1, "u"}, {1, "d"}, {2, "u"}, {2, "d"}, {3, "u"}, {3, "d"}, {4, "u"},
{4, "d"}, {5, "u"}, {5, "d"}, {6, "u"}, {6, "d"}} *)


In fact, even simpler is

SortBy[list, (# /. {"u" -> 0, "d" -> 1}) &]


Simpler yet is

SortBy[list, (# /. "u" -> 0) &]


Revised AbsoluteTiming with two new solutions

With so many solutions, it may be of interest to know their respective AbsoluteTimings, based on

list = Riffle[Map[{#, "u"} &, RandomSample[Range[100000]]],
Map[{#, "d"} &, RandomSample[Range[100000]]]];


Mike Honeychurch 0.397657

J.M. (comment) 0.468703

bbgodfrey (third solution) 0.589428

belisarius is forth (first solution) 0.811408

Jack LaVigne 11.2244

Modifications of solutions by J.M. and Mike Honeychurch, respectively, are even faster.

SortBy[list, {First, Switch[#, "u", -1, "d", 1] &}]  (* 0.385315 *)

Flatten[Reverse[Partition[Sort[list], 2], 2], 1]  (* 0.25386 *)

• I like this this one, clever! But why "d" -> 1/10, "d" -> 1 is OK. A mistake? – matheorem Nov 2 '15 at 4:23
• @matheorem You are correct. "d" assigned any number bigger than that assigned to "u" works. I carried forward the logic of my first solution without thinking. Thanks for the correction. I have simplified my solution accordingly. – bbgodfrey Nov 2 '15 at 5:05
• For large lists Sort can often be slow. Using Ordering could possibly speed up my solution for your large test sample. – Mike Honeychurch Nov 2 '15 at 23:37

Your limited example implies that you want to reverse the canonical order for the letters in position 2 so that "u" will appear before "d". I've assumed that all letters of the alphabet could appear in position 2 so if that is the case then this would do it:

Flatten[Reverse[GatherBy[Sort[list], First], 2], 1]


...but there is probably a more straight forward method, perhaps using SortBy.

Edit

As mentioned in comments with @bbgodfrey it is often more efficient to use Ordering for large lists rather than Sort. Also @bbgodfrey notes that Partition could be used instead of GatherBy.

Flatten[Reverse[Partition[list[[Ordering[list]]], 2], 2], 1]

• Straightforward or not, your solution is remarkably fast, especially when GatherBy is replaced by Partition. – bbgodfrey Nov 2 '15 at 14:14
• I just noticed a typo in my earlier comment, which is why I deleted it. Ordering[list] should have been enclosed in double-brackets, not single ones. I corrected my error in your answer. Unfortunately, with the correction list[[Ordering[list]]] offers no advantage over Sort[list], although Partition still does. Sorry. – bbgodfrey Nov 3 '15 at 0:14
• @bbgodfrey yes you're right. Maybe Sort has been rewritten in recent versions. Certainly in older version Ordering  used to smash Sort. – Mike Honeychurch Nov 3 '15 at 0:34
• On the other hand, list[[Flatten[Reverse[Partition[Ordering[list], 2], 2]]]] offers a noticeable speed advantage, probably because Reverse is acting on indices rather than on list elements. Of course, your original solution with GatherBy offers a flexibility that most other solutions lack. – bbgodfrey Nov 3 '15 at 1:02
• @bbgodfrey I think there is enough information now to satisfy the OP – Mike Honeychurch Nov 3 '15 at 1:08

I think a general solution is to perform the first test followed by the second test in case of ties.

Sort[list, first[test] || tie[first] && second[test]]


list = {{1, "u"}, {6, "d"}, {3, "u"}, {4, "d"}, {2, "u"}, {5, "u"},
{3, "d"}, {1, "d"}, {4, "u"}, {2, "d"}, {5, "d"}, {6, "u"}}


With the integers sorted on the first element and then "u" preceding "d" for the second element this translates to:

Sort[list, #1[[1]] < #2[[1]] ||
(#1[[1]] == #2[[1]] && OrderedQ[{#2[[2]], #1[[2]]}]) &]


which gives

{{1, "u"}, {1, "d"}, {2, "u"}, {2, "d"}, {3, "u"}, {3, "d"},
{4, "u"}, {4, "d"}, {5, "u"}, {5, "d"}, {6, "u"}, {6, "d"}}

• I believe bbgodfrey's answer is better. I see that in the documentation for SortBy it states. SortBy[list, {f1, f2}...} breaks ties by successively using the values obtained from the fi. – Jack LaVigne Nov 2 '15 at 3:55

To actually answer the question (not the specific example), you could create a recursive function. It would take a list of comparison functions, compare the first elements using the first function, and only use the rest if the first elements are the same.

ClearAll[compare];
compare[a_, b_, test_] /; Length@a == 1 := test[[1]][a[[1]], b[[1]]];
compare[a_, b_, test_] := test[[1]][a[[1]], b[[1]]] ||
a[[1]] == b[[1]] && compare[Rest@a, Rest@b, Rest@test];


In action:

Sort[list, compare[##, {Less, Greater}] &]


{{1, "u"}, {1, "d"}, {2, "u"}, {2, "d"}, {3, "u"}, {3, "d"}, {4, "u"}, {4, "d"}, {5, "u"}, {5, "d"}, {6, "u"}, {6, "d"}}

And it works with elements of any length, with any sort of comparison, e.g.

r = RandomInteger[{0, 10}, {1000, 3}];
Sort[r, compare[##, {Less, Greater, Abs[5 - #1] < Abs[5 - #2] &}] &]