By Legend


2011-07-07 23:56:57 8 Comments

I have a list of strings like this:

X = ["a", "b", "c", "d", "e", "f", "g", "h", "i"]
Y = [ 0,   1,   1,   0,   1,   2,   2,   0,   1 ]

What is the shortest way of sorting X using values from Y to get the following output?

["a", "d", "h", "b", "c", "e", "i", "f", "g"]

The order of the elements having the same "key" does not matter. I can resort to the use of for constructs but I am curious if there is a shorter way. Any suggestions?

15 comments

@Amelio Vazquez-Reina 2020-05-15 16:30:34

This is an old question but some of the answers I see posted don't actually work because zip is not scriptable. Other answers didn't bother to import operator and provide more info about this module and its benefits here.

There are at least two good idioms for this problem. Starting with the example input you provided:

X = ["a", "b", "c", "d", "e", "f", "g", "h", "i"]
Y = [ 0,   1,   1,   0,   1,   2,   2,   0,   1 ]

Using the "Decorate-Sort-Undecorate" idiom

This is also known as the Schwartzian_transform after R. Schwartz who popularized this pattern in Perl in the 90s:

# Zip (decorate), sort and unzip (undecorate).
# Converting to list to script the output and extract X
list(zip(*(sorted(zip(Y,X)))))[1]                                                                                                                       
# Results in: ('a', 'd', 'h', 'b', 'c', 'e', 'i', 'f', 'g')

Note that in this case Y and X are sorted and compared lexicographically. That is, the first items (from Y) are compared; and if they are the same then the second items (from X) are compared, and so on. This can create unstable outputs unless you include the original list indices for the lexicographic ordering to keep duplicates in their original order.

Using the operator module

This gives you more direct control over how to sort the input, so you can get sorting stability by simply stating the specific key to sort by. See more examples here.

import operator    

# Sort by Y (1) and extract X [0]
list(zip(*sorted(zip(X,Y), key=operator.itemgetter(1))))[0]                                                                                                 
# Results in: ('a', 'd', 'h', 'b', 'c', 'e', 'i', 'f', 'g')

@pylang 2017-08-04 19:53:59

more_itertools has a tool for sorting iterables in parallel:

Given

from more_itertools import sort_together


X = ["a", "b", "c", "d", "e", "f", "g", "h", "i"]
Y = [ 0,   1,   1,    0,   1,   2,   2,   0,   1]

Demo

sort_together([Y, X])[1]
# ('a', 'd', 'h', 'b', 'c', 'e', 'i', 'f', 'g')

@1-ijk 2015-03-15 21:47:02

I like having a list of sorted indices. That way, I can sort any list in the same order as the source list. Once you have a list of sorted indices, a simple list comprehension will do the trick:

X = ["a", "b", "c", "d", "e", "f", "g", "h", "i"]
Y = [ 0,   1,   1,    0,   1,   2,   2,   0,   1]

sorted_y_idx_list = sorted(range(len(Y)),key=lambda x:Y[x])
Xs = [X[i] for i in sorted_y_idx_list ]

print( "Xs:", Xs )
# prints: Xs: ["a", "d", "h", "b", "c", "e", "i", "f", "g"]

Note that the sorted index list can also be gotten using numpy.argsort().

@Jesse Kerr 2020-06-21 00:56:57

Do you know if there is a way to sort multiple lists at once by one sorted index list? Something like this? X1= ["a", "b", "c", "d", "e", "f", "g", "h", "i"] X2 = ["a", "b", "c", "d", "e", "f", "g", "h", "i"] X1s, X2s = [X1[i], X2[i] for i in sorted_y_idx_list ]

@nackjicholson 2018-08-17 23:07:03

I actually came here looking to sort a list by a list where the values matched.

list_a = ['foo', 'bar', 'baz']
list_b = ['baz', 'bar', 'foo']
sorted(list_b, key=lambda x: list_a.index(x))
# ['foo', 'bar', 'baz']

@nackjicholson 2020-02-12 16:56:29

No clue. Report back what you find.

@Richard 2020-06-01 00:37:17

This is a bad idea. index will perform an O(N) search on list_a resulting in an O(N² log N) sort.

@VANI 2018-02-16 05:03:54

list1 = ['a','b','c','d','e','f','g','h','i']
list2 = [0,1,1,0,1,2,2,0,1]

output=[]
cur_loclist = []

To get unique values present in list2

list_set = set(list2)

To find the loc of the index in list2

list_str = ''.join(str(s) for s in list2)

Location of index in list2 is tracked using cur_loclist

[0, 3, 7, 1, 2, 4, 8, 5, 6]

for i in list_set:
cur_loc = list_str.find(str(i))

while cur_loc >= 0:
    cur_loclist.append(cur_loc)
    cur_loc = list_str.find(str(i),cur_loc+1)

print(cur_loclist)

for i in range(0,len(cur_loclist)):
output.append(list1[cur_loclist[i]])
print(output)

@TMC 2013-10-15 13:21:29

Another alternative, combining several of the answers.

zip(*sorted(zip(Y,X)))[1]

In order to work for python3:

list(zip(*sorted(zip(B,A))))[1]

@pgmank 2018-03-26 15:12:12

I have created a more general function, that sorts more than two lists based on another one, inspired by @Whatang's answer.

def parallel_sort(*lists):
    """
    Sorts the given lists, based on the first one.
    :param lists: lists to be sorted

    :return: a tuple containing the sorted lists
    """

    # Create the initially empty lists to later store the sorted items
    sorted_lists = tuple([] for _ in range(len(lists)))

    # Unpack the lists, sort them, zip them and iterate over them
    for t in sorted(zip(*lists)):
        # list items are now sorted based on the first list
        for i, item in enumerate(t):    # for each item...
            sorted_lists[i].append(item)  # ...store it in the appropriate list

    return sorted_lists

@Iraklis Moutidis 2018-03-02 15:57:10

Here is Whatangs answer if you want to get both sorted lists (python3).

X = ["a", "b", "c", "d", "e", "f", "g", "h", "i"]
Y = [ 0,   1,   1,    0,   1,   2,   2,   0,   1]

Zx, Zy = zip(*[(x, y) for x, y in sorted(zip(Y, X))])

print(list(Zx))  # [0, 0, 0, 1, 1, 1, 1, 2, 2]
print(list(Zy))  # ['a', 'd', 'h', 'b', 'c', 'e', 'i', 'f', 'g']

Just remember Zx and Zy are tuples. I am also wandering if there is a better way to do that.

Warning: If you run it with empty lists it crashes.

@Evan Lalo 2018-01-09 20:49:11

A quick one-liner.

list_a = [5,4,3,2,1]
list_b = [1,1.5,1.75,2,3,3.5,3.75,4,5]

Say you want list a to match list b.

orderedList =  sorted(list_a, key=lambda x: list_b.index(x))

This is helpful when needing to order a smaller list to values in larger. Assuming that the larger list contains all values in the smaller list, it can be done.

@Aryeh Leib Taurog 2018-03-18 12:43:41

This does not solve the OP’s question. Did you try it with the sample lists X and Y?

@Richard 2020-06-01 00:37:40

This is a bad idea. index will perform an O(N) search on list_b resulting in an O(N² log N) sort.

@Binyamin Even 2018-01-07 23:53:00

You can create a pandas Series, using the primary list as data and the other list as index, and then just sort by the index:

import pandas as pd
pd.Series(data=X,index=Y).sort_index().tolist()

output:

['a', 'd', 'h', 'b', 'c', 'e', 'i', 'f', 'g']

@Whatang 2011-07-08 00:02:14

Shortest Code

[x for _,x in sorted(zip(Y,X))]

Example:

X = ["a", "b", "c", "d", "e", "f", "g", "h", "i"]
Y = [ 0,   1,   1,    0,   1,   2,   2,   0,   1]

Z = [x for _,x in sorted(zip(Y,X))]
print(Z)  # ["a", "d", "h", "b", "c", "e", "i", "f", "g"]

Generally Speaking

[x for _, x in sorted(zip(Y,X), key=lambda pair: pair[0])]

Explained:

  1. zip the two lists.
  2. create a new, sorted list based on the zip using sorted().
  3. using a list comprehension extract the first elements of each pair from the sorted, zipped list.

For more information on how to set\use the key parameter as well as the sorted function in general, take a look at this.


@gms7777 2014-01-17 20:33:16

This is correct, but I'll add the note that if you're trying to sort multiple arrays by the same array, this won't neccessarily work as expected, since the key that is being used to sort is (y,x), not just y. You should instead use [x for (y,x) in sorted(zip(Y,X), key=lambda pair: pair[0])]

@MasterControlProgram 2017-10-06 14:31:59

good solution! But it should be: The list is ordered regarding the first element of the pairs, and the comprehension extracts the 'second' element of the pairs.

@Hatefiend 2019-06-30 16:27:44

This solution is poor when it comes to storage. An in-place sort is preferred whenever possible.

@Tom 2014-01-12 16:18:40

Also, if you don't mind using numpy arrays (or in fact already are dealing with numpy arrays...), here is another nice solution:

people = ['Jim', 'Pam', 'Micheal', 'Dwight']
ages = [27, 25, 4, 9]

import numpy
people = numpy.array(people)
ages = numpy.array(ages)
inds = ages.argsort()
sortedPeople = people[inds]

I found it here: http://scienceoss.com/sort-one-list-by-another-list/

@MasterControlProgram 2017-10-06 14:53:16

For bigger arrays / vectors, this solution with numpy is beneficial!

@Aaron Bramson 2018-06-12 08:50:11

If they are already numpy arrays, then it's simply sortedArray1= array1[array2.argsort()]. And this also makes it easy to sort multiple lists by a particular column of a 2D array: e.g. sortedArray1= array1[array2[:,2].argsort()] to sort array1 (which may have multiple columns) by the values in the third column of array2.

@riza 2011-07-08 05:07:57

zip, sort by the second column, return the first column.

zip(*sorted(zip(X,Y), key=operator.itemgetter(1)))[0]

@Keith 2017-09-29 20:18:29

Note: the key=operator.itemgetter(1) solves the duplicate issue

@raphael 2020-02-13 11:56:59

zip is not subscriptable... you must actually use list(zip(*sorted(zip(X,Y), key=operator.itemgetter(1))))[0]

@Josh 2020-05-15 15:38:19

@Keith what duplicate issue?

@Keith 2020-05-15 21:44:34

If there is more than one matching it gets the first

@senderle 2011-07-08 00:02:32

The most obvious solution to me is to use the key keyword arg.

>>> X = ["a", "b", "c", "d", "e", "f", "g", "h", "i"]
>>> Y = [ 0,   1,   1,    0,   1,   2,   2,   0,   1]
>>> keydict = dict(zip(X, Y))
>>> X.sort(key=keydict.get)
>>> X
['a', 'd', 'h', 'b', 'c', 'e', 'i', 'f', 'g']

Note that you can shorten this to a one-liner if you care to:

>>> X.sort(key=dict(zip(X, Y)).get)

@Jack Peng 2019-03-04 19:04:14

Does this require that the values in X are unqiue?

@Ned Batchelder 2011-07-08 00:03:04

Zip the two lists together, sort it, then take the parts you want:

>>> yx = zip(Y, X)
>>> yx
[(0, 'a'), (1, 'b'), (1, 'c'), (0, 'd'), (1, 'e'), (2, 'f'), (2, 'g'), (0, 'h'), (1, 'i')]
>>> yx.sort()
>>> yx
[(0, 'a'), (0, 'd'), (0, 'h'), (1, 'b'), (1, 'c'), (1, 'e'), (1, 'i'), (2, 'f'), (2, 'g')]
>>> x_sorted = [x for y, x in yx]
>>> x_sorted
['a', 'd', 'h', 'b', 'c', 'e', 'i', 'f', 'g']

Combine these together to get:

[x for y, x in sorted(zip(Y, X))]

@John La Rooy 2017-08-23 05:05:47

This is fine if X is a list of str, but be careful if there is a possibility that < is not defined for some pairs of items in X, eg - if some of them were None

@Ash Upadhyay 2018-01-23 12:57:42

When we try to use sort over a zip object, AttributeError: 'zip' object has no attribute 'sort' is what I am getting as of now.

@Ned Batchelder 2018-01-23 16:38:04

You are using Python 3. In Python 2, zip produced a list. Now it produces an iterable object. sorted(zip(...)) should still work, or: them = list(zip(...)); them.sort()

Related Questions

Sponsored Content

47 Answered Questions

[SOLVED] Sort array of objects by string property value

30 Answered Questions

[SOLVED] Finding the index of an item in a list

  • 2008-10-07 01:39:38
  • Eugene M
  • 3949780 View
  • 3237 Score
  • 30 Answer
  • Tags:   python list indexing

22 Answered Questions

[SOLVED] How to iterate over rows in a DataFrame in Pandas

40 Answered Questions

[SOLVED] How to make a flat list out of list of lists?

19 Answered Questions

[SOLVED] Convert bytes to a string

27 Answered Questions

[SOLVED] How do I check if a list is empty?

  • 2008-09-10 06:20:11
  • Ray
  • 2932115 View
  • 3234 Score
  • 27 Answer
  • Tags:   python list

27 Answered Questions

[SOLVED] Why not inherit from List<T>?

36 Answered Questions

[SOLVED] How can I pair socks from a pile efficiently?

34 Answered Questions

[SOLVED] How do I sort a dictionary by value?

18 Answered Questions

Sponsored Content