20
\$\begingroup\$

Given a list of indices and zero or more lists of integers, output the lists of integers, sorted in ascending order, with the key priority from the first input.

Example

Let the keys input be [1, 0, 2], and the lists input be [[5, 3, 4], [6, 2, 1], [5, 2, 1]]. Those lists need to be sorted by their second element, then first element, then third element, in ascending order:

  1. First, we sort by the values at index 1: [[6, 2, 1], [5, 2, 1], [5, 3, 4]]
  2. Next, we break any ties from the first sort using the values at index 0: [[5, 2, 1], [6, 2, 1], [5, 3, 4]]
  3. Finally, we break any remaining ties with the vlues at index 2 (this doesn't actually change anything, because there are no ties remaining).

Details

  • Sorting is stable: if two elements compare equal with respect to the given sort keys, they must remain in the same relative order in the output. For example, if A and B are equal under the given sort keys, and the input was [..., A, ..., B, ...], A must be placed before B in the output.
  • A sort key will never reference a non-existant element in one of the input lists.
  • No sort key will be repeated. Thus, [1, 2, 1] is not a valid list of sort keys.
  • Any elements not referenced by the sort keys do not factor into the sorting order. Only the initial relative order and the values of the elements referenced by the sort keys determine the output order.
  • You may choose whether the sort keys are zero-indexed or one-indexed.
  • There will be no negative values in the sort keys. If you choose to use one-indexing, there will be no zeroes in the sort keys either.
  • Integer values will not exceed your language's natively-representable range. If your chosen language is natively capable of arbitrary-precision integers (like Python), then any integer value can be present in the input, subject to memory constraints.

Reference Implementation (Python 2)

#!/usr/bin/env python

keys = input()
lists = input()

print sorted(lists, key=lambda l:[l[x] for x in keys])

Try it online

Test Cases

Format: keys lists -> output. All sort keys are zero-indexed.

[1, 0, 2] [[5, 3, 4], [6, 2, 1], [5, 2, 1]] -> [[5, 2, 1], [6, 2, 1], [5, 3, 4]]
[1, 2] [[5, 3, 4], [6, 2, 1], [5, 2, 1]] -> [[6, 2, 1], [5, 2, 1], [5, 3, 4]]
[0, 1] [[1, 2], [2, 1]] -> [[1, 2], [2, 1]]
[1, 0] [[1, 2], [2, 1]] -> [[2, 1], [1, 2]]
[0] [[4], [10, 11, -88], [-2, 7]] -> [[-2, 7], [4], [10, 11, -88]]
[2] [[-1, -5, 8, -1, -4, -10, -5, 4, 4, 6, -8, 4, 2], [-7, 6, 2, -8, -7, 7, -3, 3, 0, -6, 1], [-9, 8, -5, -1, -7, -8, -5, -6, 5, -6, 6]] -> [[-9, 8, -5, -1, -7, -8, -5, -6, 5, -6, 6], [-7, 6, 2, -8, -7, 7, -3, 3, 0, -6, 1], [-1, -5, 8, -1, -4, -10, -5, 4, 4, 6, -8, 4, 2]]
[2, 1] [[9, 2, -2, -10, -6], [3, -4, -2]] -> [[3, -4, -2], [9, 2, -2, -10, -6]]
[2, 4, 8] [[5, -3, 4, -6, -1, -2, -2, -4, 5], [-2, -3, 6, -4, -1, -4, -4, -5, 8, 9, 9, -3, 3, -9, -3], [2, 0, 10, -10, -1, 2, -1, 5, -1, 10, -5], [-7, -8, -6, 7, 3, 8, 6, -7, -2, 0, -6, -4, 4, -3, 2, -3]] -> [[-7, -8, -6, 7, 3, 8, 6, -7, -2, 0, -6, -4, 4, -3, 2, -3], [5, -3, 4, -6, -1, -2, -2, -4, 5], [-2, -3, 6, -4, -1, -4, -4, -5, 8, 9, 9, -3, 3, -9, -3], [2, 0, 10, -10, -1, 2, -1, 5, -1, 10, -5]]
[1, 2, 3, 4, 5] [[-7, 3, -8, 3, 5, -1, 6, -6, 9, 8], [-9, -1, -7, -9, -10, -2, -8, -10, -10, -3], [5, 3, -6, -5, -4, -4, -8, 2], [9, -4, 1, -1, -3, -2], [-6, -10, 4, -10, 6, 6, -1, 3, 0, 0], [1, -2, -7, -6, -7, -7, -1, 0, -4, 3, 3], [7, -1, -7, 2, -2, 9, 7, 5, -6, -8], [1, -5, -3, -10, -7, 9, -8, -5, -1], [-9, 4, -1, -1, 2, 4]] -> [[-6, -10, 4, -10, 6, 6, -1, 3, 0, 0], [1, -5, -3, -10, -7, 9, -8, -5, -1], [9, -4, 1, -1, -3, -2], [1, -2, -7, -6, -7, -7, -1, 0, -4, 3, 3], [-9, -1, -7, -9, -10, -2, -8, -10, -10, -3], [7, -1, -7, 2, -2, 9, 7, 5, -6, -8], [-7, 3, -8, 3, 5, -1, 6, -6, 9, 8], [5, 3, -6, -5, -4, -4, -8, 2], [-9, 4, -1, -1, 2, 4]]
[8, 7, 3, 2, 4, 9, 1] [[8, -5, 1, -6, -1, -4, 6, 10, 10, 6, 9, 5], [4, -8, 6, -10, -2, -3, 2, -6, 9, 5, 4, 10, 2, 3], [10, -1, 3, 0, -4, 1, -5, -4, -1, -7, 9, -9, -1, -5, 7, 8, 9, 6, -3], [0, -9, -7, -2, 2, -5, 7, 4, 6, -4, 1, 8, -7, 10], [5, 6, -9, 0, -1, 5, 4, 7, 5, 10, 2, 5, 7, -9]] -> [[10, -1, 3, 0, -4, 1, -5, -4, -1, -7, 9, -9, -1, -5, 7, 8, 9, 6, -3], [5, 6, -9, 0, -1, 5, 4, 7, 5, 10, 2, 5, 7, -9], [0, -9, -7, -2, 2, -5, 7, 4, 6, -4, 1, 8, -7, 10], [4, -8, 6, -10, -2, -3, 2, -6, 9, 5, 4, 10, 2, 3], [8, -5, 1, -6, -1, -4, 6, 10, 10, 6, 9, 5]]
\$\endgroup\$
  • \$\begingroup\$ Some of the test cases seem obnoxiously long. \$\endgroup\$ – Fatalize Sep 29 '16 at 12:59
  • \$\begingroup\$ @Fatalize They're meant to cover cases where there are few sort keys compared to the lengths of the lists, and cases where there are many sort keys. \$\endgroup\$ – Mego Sep 29 '16 at 13:00
  • 1
    \$\begingroup\$ @Fatalize That's why we have copy and paste. If necessary, use Retina to change the format to something you can use. \$\endgroup\$ – mbomb007 Sep 29 '16 at 14:03
  • \$\begingroup\$ Can we assume all rows will have the same length if that's the natural data type in our language (i.e. a matrix)? \$\endgroup\$ – Luis Mendo Sep 29 '16 at 16:02
  • \$\begingroup\$ @LuisMendo No. You must be able to support jagged arrays. \$\endgroup\$ – Mego Sep 29 '16 at 16:03

18 Answers 18

6
\$\begingroup\$

Jelly, 4 bytes

⁴ị$Þ

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Have you got a breakdown of how that works? \$\endgroup\$ – JamEngulfer Sep 29 '16 at 21:41
  • \$\begingroup\$ @JamEngulfer: It should have been specified in the answer, but: Þ is "sort with specified sort key", ⁴ị uses the second command-line argument to reorder the array (producing a sort key which works like the question asks), and $ overrides the precedence so that the program parses correctly. \$\endgroup\$ – user62131 May 8 '17 at 15:38
5
\$\begingroup\$

CJam, 13 bytes

{W%{{X=}$}fX}

An unnamed block which expects the list of lists and the list of priorities on top of the stack and replaces them with the sorted list of lists.

Try it online! (As a test suite.)

Explanation

Sorting with tie breakers can be implemented by repeatedly sorting the entire list stably going from the lowest-priority key to the highest-priority key.

W%      e# Reverse priority list.
{       e# For each priority X...
  {     e#   Sort the lists by the result of this block...
    X=  e#     Extract the Xth element from the current list.
  }$
}fX
\$\endgroup\$
4
\$\begingroup\$

Ruby, 35 bytes

->k,a{a.sort_by{|e|e.values_at *k}}

See it on eval.in: https://eval.in/652574

\$\endgroup\$
4
\$\begingroup\$

Haskell, 38 bytes

import Data.List
sortOn.flip(map.(!!))

Usage example: ( sortOn.flip(map.(!!)) ) [2,1] [[9,2,-2,-10,-6], [3,-4,-2]] -> [[3,-4,-2],[9,2,-2,-10,-6]].

Non-pointfree: f k v=sortOn(\x->map(\y->x!!y)k)v.

\$\endgroup\$
4
\$\begingroup\$

Mathematica, 22 19 bytes

SortBy[Extract/@#]&

Uses 1-based indices. This unnamed function is curried, so the calling convention is:

SortBy[Extract/@#]&[{2, 1, 3}][{{5, 3, 4}, {6, 2, 1}, {5, 2, 1}}]

Mathematica's SortBy can take a list of functions in which case the individual functions are used as successive tie-breakers, so that's just what we want. All we need to do is create a list of functions which return the corresponding list element. This can be done with Extract. Extract is normally a binary function Extract[list, index] which returns a list element. However if used unarily, then Extract[index] returns a function which retrieves the element at index from a list passed to it. In other words, the index parameter of Extract can be curried. We make use of this by mapping Extract over the list of indices we're given, which creates the list of functions we need.

\$\endgroup\$
  • \$\begingroup\$ Shouldn't Extract/@# be Extract/@(#+1)? The index of the input starts at 0. \$\endgroup\$ – JungHwan Min Sep 29 '16 at 14:09
  • 2
    \$\begingroup\$ @JHM "You may choose whether the sort keys are zero-indexed or one-indexed." \$\endgroup\$ – Martin Ender Sep 29 '16 at 14:10
  • \$\begingroup\$ I stand corrected. \$\endgroup\$ – JungHwan Min Sep 29 '16 at 14:14
  • \$\begingroup\$ (Unsprisingly) elegant! But given that you're 1-indexing, shouldn't [{1, 0, 2}] be [{2, 1, 3}] in your example? Indeed, currently it seems to be sorting by first element, then head, then second element. \$\endgroup\$ – Greg Martin Sep 29 '16 at 16:31
  • \$\begingroup\$ @GregMartin sorry, copy/paste fail. \$\endgroup\$ – Martin Ender Sep 29 '16 at 16:32
3
\$\begingroup\$

Python, 50 bytes

lambda l,k:sorted(l,key=lambda x:[x[y]for y in k])

This is a trivially-golfed version of the reference implementation. l is the lists parameter, and k is the sort keys parameter. l can be any iterable, so long as its elements are subscriptable by integers (like lists, tuples, or int-keyed dicts). k can be any iterable.

\$\endgroup\$
3
\$\begingroup\$

Brachylog, 29 bytes

tT,?hg:Tz:{:2f}o:ta
heI,?t:Im

Try it online!

Explanation

We use the fact that o - Order can be used with an additionnal predicate as input: we order the lists by using for each [Keys, a list] the list of the elements of a list which are at index a key in the order that they appear in Keys.

                          Input = [Keys, List of lists]

tT,                       Call the Keys T
   ?hg:T                  Create the list [[T], List of lists]
        z                 Zip [T] with the list of lists
         :{   }o          Order by the output of this predicate
                :ta       Keep only the last element of each sublist in the Output

           :2f            Find all outputs of the predicate below

heI,                      Take a key I
    ?t:Im                 Output is the Ith element of the sublist
\$\endgroup\$
3
\$\begingroup\$

CJam (12 bytes)

{{1$\f=}$\;}

Online demo. This is an anonymous block (function) which takes the arguments in the order given for the test cases and leaves the sorted value on the stack. It relies on the built-in sort $ being stable, but the official interpreter guarantees that.

Dissection

{          e# Define a block. Stack: orders values-to-sort
  {        e#   Sort by...
    1$\f=  e#     Copy orders from the stack, and map array lookup
  }$
  \;       e#   Pop the orders to leave just sorted-values
}
\$\endgroup\$
3
\$\begingroup\$

J, 6 bytes

]/:{&>

Keys are zero-indexed. The LHS is the list of keys and the RHS is an array of values. Since J doesn't support ragged arrays, each array must be boxed.

Usage

   f =: ]/:{&>
   < 1 0 2
┌─────┐
│1 0 2│
└─────┘
   5 3 4 ; 6 2 1 ; 5 2 1
┌─────┬─────┬─────┐
│5 3 4│6 2 1│5 2 1│
└─────┴─────┴─────┘
   (< 1 0 2) f  5 3 4 ; 6 2 1 ; 5 2 1
┌─────┬─────┬─────┐
│5 2 1│6 2 1│5 3 4│
└─────┴─────┴─────┘
   (< 1 2) f  5 3 4 ; 6 2 1 ; 5 2 1
┌─────┬─────┬─────┐
│6 2 1│5 2 1│5 3 4│
└─────┴─────┴─────┘
   (< 0) f 4 ; 10 11 _88 ; _2 7
┌────┬─┬─────────┐
│_2 7│4│10 11 _88│
└────┴─┴─────────┘

Explanation

]/:{&>  Input: keys (LHS), values (RHS)
   {&>  Select from values at each index in keys
]       Get the values
 /:     Sort up the values using the ones selected with the keys
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 55 bytes

(k,l)=>k.reduceRight((l,i)=>l.sort((a,b)=>a[i]-b[i]),l)

The ECMAscript standard doesn't guarantee that the underlying sort is stable, so the following 68-byte code doesn't make that assumption:

(k,l)=>l.sort(g=(a,b,i=0)=>i<k.length?a[k[i]]-b[k[i]]||g(a,b,i+1):0)
\$\endgroup\$
2
\$\begingroup\$

Pyth, 5 4 bytes

@LDF

Try it online: Demonstration or Test Suite

Thanks to @Maltysen for one byte.

Explanation:

@LDFQ   Q (=input) added implicitly. 
  D     sort a list of lists by
@L         the sublists generated by some indices
   FQ   executes ^ with the the input as parameter

I was really surprised that this worked. It's a really strange syntax.

\$\endgroup\$
  • \$\begingroup\$ I think you can save by replacing QE by F \$\endgroup\$ – Maltysen Sep 29 '16 at 19:48
  • \$\begingroup\$ @Maltysen Thanks. I thought that was only possible with a regular one-token method. \$\endgroup\$ – Jakube Sep 29 '16 at 19:56
  • 1
    \$\begingroup\$ the rules for sugar are very adhoc and inconsistent, the best is unfortunately just to try out if a particular thing works. \$\endgroup\$ – Maltysen Sep 29 '16 at 19:59
2
\$\begingroup\$

JavaScript (ES6) 46

k=>l=>l.sort((a,b)=>k.some(i=>v=a[i]-b[i])&&v)

At each comparison during the sort, scan the key indices to find the right order

Test

f=k=>l=>l.sort((a,b)=>k.some(i=>v=a[i]-b[i])&&v)

;`[1, 0, 2] [[5, 3, 4], [6, 2, 1], [5, 2, 1]] -> [[5, 2, 1], [6, 2, 1], [5, 3, 4]]
[1, 2] [[5, 3, 4], [6, 2, 1], [5, 2, 1]] -> [[6, 2, 1], [5, 2, 1], [5, 3, 4]]
[0, 1] [[1, 2], [2, 1]] -> [[1, 2], [2, 1]]
[1, 0] [[1, 2], [2, 1]] -> [[2, 1], [1, 2]]
[0] [[4], [10, 11, -88], [-2, 7]] -> [[-2, 7], [4], [10, 11, -88]]
[2] [[-1, -5, 8, -1, -4, -10, -5, 4, 4, 6, -8, 4, 2], [-7, 6, 2, -8, -7, 7, -3, 3, 0, -6, 1], [-9, 8, -5, -1, -7, -8, -5, -6, 5, -6, 6]] -> [[-9, 8, -5, -1, -7, -8, -5, -6, 5, -6, 6], [-7, 6, 2, -8, -7, 7, -3, 3, 0, -6, 1], [-1, -5, 8, -1, -4, -10, -5, 4, 4, 6, -8, 4, 2]]
[2, 1] [[9, 2, -2, -10, -6], [3, -4, -2]] -> [[3, -4, -2], [9, 2, -2, -10, -6]]
[2, 4, 8] [[5, -3, 4, -6, -1, -2, -2, -4, 5], [-2, -3, 6, -4, -1, -4, -4, -5, 8, 9, 9, -3, 3, -9, -3], [2, 0, 10, -10, -1, 2, -1, 5, -1, 10, -5], [-7, -8, -6, 7, 3, 8, 6, -7, -2, 0, -6, -4, 4, -3, 2, -3]] -> [[-7, -8, -6, 7, 3, 8, 6, -7, -2, 0, -6, -4, 4, -3, 2, -3], [5, -3, 4, -6, -1, -2, -2, -4, 5], [-2, -3, 6, -4, -1, -4, -4, -5, 8, 9, 9, -3, 3, -9, -3], [2, 0, 10, -10, -1, 2, -1, 5, -1, 10, -5]]
[1, 2, 3, 4, 5] [[-7, 3, -8, 3, 5, -1, 6, -6, 9, 8], [-9, -1, -7, -9, -10, -2, -8, -10, -10, -3], [5, 3, -6, -5, -4, -4, -8, 2], [9, -4, 1, -1, -3, -2], [-6, -10, 4, -10, 6, 6, -1, 3, 0, 0], [1, -2, -7, -6, -7, -7, -1, 0, -4, 3, 3], [7, -1, -7, 2, -2, 9, 7, 5, -6, -8], [1, -5, -3, -10, -7, 9, -8, -5, -1], [-9, 4, -1, -1, 2, 4]] -> [[-6, -10, 4, -10, 6, 6, -1, 3, 0, 0], [1, -5, -3, -10, -7, 9, -8, -5, -1], [9, -4, 1, -1, -3, -2], [1, -2, -7, -6, -7, -7, -1, 0, -4, 3, 3], [-9, -1, -7, -9, -10, -2, -8, -10, -10, -3], [7, -1, -7, 2, -2, 9, 7, 5, -6, -8], [-7, 3, -8, 3, 5, -1, 6, -6, 9, 8], [5, 3, -6, -5, -4, -4, -8, 2], [-9, 4, -1, -1, 2, 4]]
[8, 7, 3, 2, 4, 9, 1] [[8, -5, 1, -6, -1, -4, 6, 10, 10, 6, 9, 5], [4, -8, 6, -10, -2, -3, 2, -6, 9, 5, 4, 10, 2, 3], [10, -1, 3, 0, -4, 1, -5, -4, -1, -7, 9, -9, -1, -5, 7, 8, 9, 6, -3], [0, -9, -7, -2, 2, -5, 7, 4, 6, -4, 1, 8, -7, 10], [5, 6, -9, 0, -1, 5, 4, 7, 5, 10, 2, 5, 7, -9]] -> [[10, -1, 3, 0, -4, 1, -5, -4, -1, -7, 9, -9, -1, -5, 7, 8, 9, 6, -3], [5, 6, -9, 0, -1, 5, 4, 7, 5, 10, 2, 5, 7, -9], [0, -9, -7, -2, 2, -5, 7, 4, 6, -4, 1, 8, -7, 10], [4, -8, 6, -10, -2, -3, 2, -6, 9, 5, 4, 10, 2, 3], [8, -5, 1, -6, -1, -4, 6, 10, 10, 6, 9, 5]]`
.split('\n').map(row=>{
  var [keys,list,expected]=row.split(/] -?>? ?\[/)
  keys=eval(keys+']');
  list=eval('['+list+']');
  expected=eval('['+expected);
  var result=f(keys)(list);
  var ok=result.join`|`==expected.join`|`;
  console.log(ok?'OK':'KO',keys+' '+list.join`|`+' -> ' +expected.join`|`,ok?'':result.join`|`)
})

\$\endgroup\$
2
\$\begingroup\$

PHP, 212 170 bytes

function m(&$i,$k){foreach($i as$a=>$y)for($b=-1;++$b<$a;){for($p=0;$p<count($k)&!$r=$i[$b][$x=$k[$p++]]-$i[$b+1][$x];);if($r>0){$s=$i[$b+1];$i[$b+1]=$i[$b];$i[$b]=$s;}}}

PHP has no stable sort built in anymore; picking an older version there is no way to do a recursive callback with the required specification. But nevermind: using the recursive callback iterator would cost tons; so I didn´t even check if that could do it.

The inner loop could be replaced with another foreach; that would save some bytes on the swapping. But without a check for $b<$a (or $b<count($i)), that will result in an infinite loop. And with that check, The foreach costs as much as the swapping wins.

I first did the comparison recursively; but iteration saves tons of bytes:

breakdown

// bubble sort
function m(&$i,$k)
{
    foreach($i as$a=>$y)
        for($b=-1;++$b<$a;)
        {
            // comparison:
            for($p=0;$p<count($k)                       // loop through keys
                &
                !$r=$i[$b][$x=$k[$p++]]-$i[$b+1][$x]    // while element equals its successor
            ;);
            // if element is larger than its successor, swap them
            if($r>0)
            {
                $s=$i[$b+1];$i[$b+1]=$i[$b];$i[$b]=$s;
            }
        }
}
\$\endgroup\$
  • \$\begingroup\$ Your whole if($r>0){$s=$i[$b+1];$i[$b+1]=$i[$b];$i[$b]=$s;} can be written as $r>0&&$i[$b+1]^=$i[$b]^=$i[$b+1]^=$i[$b];, saving you 7 bytes. This uses a XOR swap with abuse of short-circuit evaluation to emulate an if(){ ... }. The swap is only executed if and only if $r>0. This uses the same trick that is (sometimes) used with databases. Often, you will see mysqli_connect( ... ) or die('Cannot connect');. \$\endgroup\$ – Ismael Miguel Oct 2 '16 at 15:23
  • \$\begingroup\$ @IsmaelMiguel XOR swap does not work for arrays. And it would save 10 bytes, because I could make it the post-condition of the $b loop. ;) \$\endgroup\$ – Titus Oct 3 '16 at 11:01
  • \$\begingroup\$ I tested the XOR swap and it worked (I didn't test with the rest of the code). I wrote 2 test cases: sandbox.onlinephpfunctions.com/code/… (you code) and sandbox.onlinephpfunctions.com/code/… (XOR swap). According to text-compare.com, the output is identical. \$\endgroup\$ – Ismael Miguel Oct 3 '16 at 11:22
  • \$\begingroup\$ @IsmaelMiguel To test the function You should execute it: insert m($i,$k); before the var_dump and Your version will produce garbage. \$\endgroup\$ – Titus Oct 3 '16 at 12:47
  • \$\begingroup\$ :/ I didnt even noticed that I didn't execute the function... :/ But it was a cool idea! \$\endgroup\$ – Ismael Miguel Oct 3 '16 at 12:58
1
\$\begingroup\$

R 40 bytes

for(i in rev(il)){dd=dd[order(dd[,i]),]}

Explanation:

List of lists is best represented as a data.frame in R:

ll2 = list(c(5,3,4), c(5,3,7), c(6,2,1), c(6,1,3), c(5,2,1))
dd = data.frame(do.call(rbind, ll2))
dd
      X1 X2 X3
    1  5  3  4
    2  5  3  7
    3  6  2  1
    4  6  1  3
    5  5  2  1

If index list is il (indexing is from 1):

il = list(1, 2, 3)

Sorting can be done with following code:

for(i in rev(il)){dd = dd[order(dd[,i]),]}

Output:

dd
  X1 X2 X3
5  5  2  1
1  5  3  4
2  5  3  7
4  6  1  3
3  6  2  1
\$\endgroup\$
1
\$\begingroup\$

Perl 6  23 20  19 bytes

->\a,\b{b.sort:{.[|a]}}
{$^a;$^b.sort:{.[|$a]}}
{$^b.sort: *.[|$^a]}
{$^b.sort: *[|$^a]}
\$\endgroup\$
1
\$\begingroup\$

Racket 218 bytes

(λ(il ll)(define qsl(λ(l i)(if(null? l)l(let*((h(first l))(t(rest l))(g(λ(ff)(filter(λ(x)(ff(list-ref x i)
(list-ref h i)))t))))(append(qsl(g <)i)(list h)(qsl(g >=)i))))))(for((i(reverse il)))(set! ll(qsl ll i)))ll)

Ungolfed (il=index list; ll=list of lists; qsl= quicksort for list of lists; h=head (first element); t=tail (rest or remaining elements); g=modifiable filter fn):

(define qsl
  (λ(l i)
    (if (null? l)
        l
        (let* ((h (first l))
               (t (rest  l))
               (g (λ(ff) (filter (λ(x) (ff (list-ref x i) (list-ref h i))) t))))
          (append (qsl (g <) i)
                  (list h)
                  (qsl (g >=) i)
                  )))))
(define f
  (λ(il ll)
    (for ((i (reverse il)))
      (set! ll (qsl ll i)))
    ll))

Testing:

(f (list 0 1 2) (list (list 5 3 4) (list 5 3 7) (list 6 2 1) (list 6 1 3) (list 5 2 1)))
(f [list 1 2] [list [list 5 3 4] [list 6 2 1] [list 5 2 3]])

Output:

'((5 2 1) (5 3 4) (5 3 7) (6 1 3) (6 2 1))
'((6 2 1) (5 2 3) (5 3 4))
\$\endgroup\$
1
\$\begingroup\$

PHP, 139 Bytes

use the new spaceship operator and usort

<?$a=$_GET[a];function c($x,$y,$i=0){$k=$_GET[k];return$x[$k[$i]]-$y[$k[$i]]?:($k[++$i]?c($x,$y,$i):0);}usort($a,c);echo json_encode($a);

Instead of $x[$k[$i]]<=>$y[$k[$i]] you can use $x[$k[$i]]-$y[$k[$i]] under a PHP Version greater 7 - 2 Bytes

version with create an own index 197 Bytes like in a real library

<?$m=min(array_map(min,$a=$_GET[a]));foreach($a as$p=>$v){$k="";foreach($s=$_GET[s]as$f){$k.=str_pad($v[$f]-$m,5,0,0);}$k.=str_pad($p,5,0,0);$r[$k]=$v;}ksort($r);echo json_encode(array_values($r));
\$\endgroup\$
  • \$\begingroup\$ You can try to use <?function c($x,$y,$i=0){$k=$_GET[k];return $x[$k[$i]]<=>$y[$k[$i]]?:($k[++$i]?c($x,$y,$i):0);}usort($a=$_GET[a],c);echo json_encode($a);. $_GET is a superglobal: it means that it is already a global everywhere. Remove the global$k;, move the assignment inside the function and you're done. Also, since this is using $_GET, you have to use <?. With this, you save 10 bytes. It will (hopefully) work. \$\endgroup\$ – Ismael Miguel Oct 2 '16 at 10:36
  • \$\begingroup\$ @IsmaelMiguel I feel like an idiot that I'd not seen that I use the global only inside the function. \$\endgroup\$ – Jörg Hülsermann Oct 2 '16 at 13:40
  • \$\begingroup\$ PHP sort functions use quicksort; that´s not stable. Apart from that, you can save two bytes with - instead of <=> and two with an anonyomous callback for usort. \$\endgroup\$ – Titus Oct 2 '16 at 14:08
  • \$\begingroup\$ @Titus An anonymous function can't be used because of c($x,$y,$i) at the end of the body of the function. \$\endgroup\$ – Ismael Miguel Oct 2 '16 at 14:13
  • \$\begingroup\$ @JörgHülsermann Don't worry, we all make silly mistakes. \$\endgroup\$ – Ismael Miguel Oct 2 '16 at 14:14
0
\$\begingroup\$

Clojure, 29 bytes

#(sort-by(fn[c](mapv c %))%2)

Nicely sort-by is stable and knows how to sort vectors, and vectors can operate as functions. ([4 6 9 7] 2) is 9 (0-based indexing).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.