3

I'm not interested in any particular algorithm; I just want to know if doing that has a common name that I'm just not aware of.

To be specific, say I have X = [42, 0, 99] and Y = ["a", "b", "c"]. What is it called when I reorder Y in the same way that I have to reorder X to make X a sorted list, winding up with ["b", "a", "c"]?

What about the reordering itself, which is kind of a list - i.e. [<2nd>, <1st>, <3rd>] - does that have a common name too?

It seems like that would be the kind of operation that would have a name that I should know, with its own Wikipedia page and everything (or an entry in the NIST's Dictionary of Algorithms and Data Structures: http://xw2k.nist.gov/dads/). I'm probably going to feel like a dummy when someone answer this.

double-beep
  • 5,031
  • 17
  • 33
  • 41
jtolle
  • 7,023
  • 2
  • 28
  • 50
  • 1
    just invent a name (the more complicated you make it, the smarter you sound :) how about proxy-sort-permutation. then write your own wiki, and once its on wikipedia, it must be true! and there you go. – davin Feb 07 '11 at 23:51
  • Although to be serious, it looks like you're implementing parallel arrays and making life hard; if those items are 1-1 like that they probably belong in an object/pair/list which itself should be an element in a single array, but maybe your constraints/considerations are different – davin Feb 07 '11 at 23:54
  • @davin, I'm actually not implementing anything in particular right now. I think you're right in general about not using parallel lists. But surely there are still situations where genius-proxy-sort-permute is worth breaking out as a discrete concept. Say you have one X but a bunch of Ys. You just need to sort X once to get the permutation, and then use it to reorder all of the Ys. It wouldn't make sense to construct a bunch of pairs and then sort them all on pair-x. – jtolle Feb 08 '11 at 00:04

4 Answers4

2

The reordering itself is called a permutation(see sidenote).

I am not aware of a special term for the situation, but you could say that you're applying the permutation that sorts the list X, to the list Y.

Sidenote: Note that the word "permutation" can refer to both a particular ordering of a group of elements, for instance with the ordered list [3, 1, 2] being a permutation of the numbers {1, 2, 3}, as well as a reordering of elements (as in, the transformation itself), for instance the one that permutes the ordered list [3, 1, 2] to the ordered list [1, 2, 3].

Sebastian Paaske Tørholm
  • 49,493
  • 11
  • 100
  • 118
  • Thanks. As predicted, I do feel like a bit of a dork, since I certainly know the word "permutation". I think this is probably the correct answer, in that it's a good description of the operation I'm talking about, but that there isn't a commonly accepted name for it. I'll probably accept it soon unless someone comes up with something definitive. (For reference, here is a link for a more accessible defintion of "permutation" in a algorithm context than the Wikipedia page: http://xw2k.nist.gov/dads//HTML/permutation.html ) – jtolle Feb 08 '11 at 01:11
  • This answer on stackoverflow uses your same terminology, although I found it based on the answer from @Jim Balter: http://stackoverflow.com/questions/1903462/how-can-i-zip-sort-parallel-numpy-arrays/1903579#1903579 – jtolle Feb 08 '11 at 05:41
  • And that answer refers to use of numpy.argsort, which returns an array of indices that would sort an array: http://docs.scipy.org/doc/numpy/reference/generated/numpy.argsort.html – jtolle Feb 08 '11 at 06:02
  • @jtolle Your SO ref calls this "zip sort", which might well be the best answer to your original question, if it weren't for the fact that it would most likely be interpreted as referring to zip codes. – Jim Balter Feb 08 '11 at 06:39
  • I think the various answers I got show that there isn't an obvious common phrase for the "sort on e list by another" part, and @Sebastian's answer of "apply the permutation that sorts one list to the other one" is concise and precise. Thanks, everyone! – jtolle Feb 09 '11 at 05:37
1

I've mostly known it as an "indexed sort". X is the index you use to sort Y.

cabbey
  • 226
  • 3
  • 14
  • Searching on this led me to this stackoverflow post that refers to an "index-based sort": http://stackoverflow.com/questions/659866/is-there-c-support-for-an-index-based-sort. I also notice that the Wikipedia article on sorting uses the term "tag sort". – jtolle Feb 08 '11 at 01:13
  • But X is **not** the index used to sort Y -- X could just as well be [e, -1, pi] or ["Paul", "Mary", "Peter"] – Jim Balter Feb 08 '11 at 04:40
  • @jtolle A tag sort is quite different from your question. The purpose of a tag sort is to avoid moving large records, or records on secondary storage, during the sort. – Jim Balter Feb 08 '11 at 04:45
  • @Jim, in the example given, X={42,0,99} Y={'a','b','c'} output={'b','a','c'}; so the indexed array would be {42=>'a',0=>'b',99=>'c'} sort those by the "X" value and you get {0=>'b',42=>'a',99=>'c'}... just what was asked for. Not sure how you consider X not the index used to sort Y there. – cabbey Feb 08 '11 at 05:31
  • @Jim, Thanks. So the term "tag sort" would specifically refer to a particular use case. Otherwise, it seems similar: "A sorting procedure in which the key fields are sorted first to create the correct order, and then the actual data records are placed into that order" (pcmag.com encyclopedia via Wikipedia). – jtolle Feb 08 '11 at 05:56
  • @cabbey 42 and 99 are not indices of Y, so X cannot be an index array of Y. It is, rather, a key array. – Jim Balter Feb 08 '11 at 06:26
  • @jtolle In the sort procedure you describe, the sort is applied to records containing both a key and an index, and then the data records are ordered according to the indices. In a tag sort, you have only the indices, and the keys are found in the indexed records. They are indeed quite similar. – Jim Balter Feb 08 '11 at 06:31
1

As far as I know, there is no term for this specific situation, but you are applying the same transformation to lists X and Y, and you create the transformation such that it transforms list X into a sorted list.

Eric Finn
  • 8,629
  • 3
  • 33
  • 42
1

You could call this a parallel key sort, since X contains the sort keys and Y contains the values. In a functional language, e.g., Scala, this could be implemented as X.zip(Y).sortWith((a,b) => a._1 < b._1).map(a => a._2)

Jim Balter
  • 16,163
  • 3
  • 43
  • 66