Sort list in place using another list of index

Question

given

a = [1,4,5,3,2,6,0]
b = ['b','e','f','d','c','g','a']

order b in place, the expected order of b is available in the corresponding positional element of a.

output will be

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

try for other similar input sets.

a = [4,0,1,3,2]
b = ['E','A','B','D','C']

I can get it done using a third list, even sorted() creates a third list, but the key is to sort b in place

print sorted(b,key=lambda bi : a[b.index(bi)])

core of the problem is how to prevent iterating over items in b that were already iterated.

`B = dict((v, i) for i, v in enumerate(b))` can help you, if you have unique elements in your list — m.wasowski, Mar 27 '14 at 12:09
You can conduct a simple bubble sort on both lists simultaneously. — Abhishek Bansal, Mar 27 '14 at 12:10
Don't forget that b.index(bi) runs in O(n), which slows the sorting down to O(n^2 log n). That's worse than bubble sort. In addition, it doesn't work if `a` contains duplicate items. — Danstahr, Mar 27 '14 at 12:12
See also http://stackoverflow.com/questions/6618515/sorting-list-based-on-values-from-another-list — fredtantini, Mar 27 '14 at 12:12
Interestingly, it seems there is no algorithm which can accomplish your requirement under the restriction that a[] should come out unchanged - given that "in place" means the usual algorithmic "O(c) additional space" and not the pythonic "result is written back to input list". Additional O(n) space seems necessary if the key comes exterior to the data items - can someone with a background in sorting algorithms enlighten me? — Vroomfondel, Mar 27 '14 at 14:25

score 6 · Answer 1 · edited May 23 '17 at 10:26

6

Try this:

zip(*sorted(zip(a, b)))[1]

Should give:

('a', 'b', 'c', 'd', 'e', 'f', 'g')

Since during sorting the b itself appears to be empty (see my question about that), you can use that piece of code to do it in-place:

b.sort(key=lambda x, b=b[:]: a[b.index(x)])

This uses a copy of the b to search in during sorting. This is certainly not very good for performance, so don't blame me ;-)

edited May 23 '17 at 10:26

Community

1
1

answered Mar 27 '14 at 12:11

Alfe

56,346
20
107
159

1

But that's not in-place for `b`, of course. So you might not want to use it. – Alfe Mar 27 '14 at 12:12
1

That's strange. I tried `b.sort(key=lambda x: a[b.index(x)])` and found that during being sorted, b appears to be an empty list. – Alfe Mar 27 '14 at 12:17
I posted this effect as a [new question](http://stackoverflow.com/questions/22687515/list-appears-to-be-empty-during-sorting). – Alfe Mar 27 '14 at 12:23
That's right b is made empty while it is being sorted – nr.o Mar 27 '14 at 12:23
I'd like to discuss that, and would like to give points, so please visit the Q mentioned above :) – Alfe Mar 27 '14 at 12:24
Interesting. Then my Q should be flagged as a duplicate. – Alfe Mar 27 '14 at 12:33

John La Rooy · Accepted Answer · 2014-03-27T12:39:05.693

5

The key is to realise that the items in b aren't much use to the key function. You are interested in their counterparts in a. To do this inplace, means you can't just use zip to pair the items up. Here I use the default argument trick to get an iterator over a into the lambda function.

>>> a = [1,4,5,3,2,6,0]
>>> b = ['b','e','f','d','c','g','a']
>>> b.sort(key=lambda x, it=iter(a): next(it))
>>> b
['a', 'b', 'c', 'd', 'e', 'f', 'g']

edited Mar 27 '14 at 12:39

answered Mar 27 '14 at 12:30

John La Rooy

295,403
53
369
502

1

Is there any guarantee made by `.sort` that the key function will be called both in order and only once per item? – Eric Mar 27 '14 at 12:58
I'd like to strongly support @Eric's question (hence this comment). Is there such a guarantee? Otherwise this solution just works due to implementation details of the sorting algorithm. Actually I'm surprised that the key function is used just in this (here neatly fitting) way. – Alfe Mar 28 '14 at 01:14
@Alfe, it's a good question. I haven't the time to look for an authoritative answer just now. Maybe you can open a new question and get a bigger audience than just me. I'm interested in the answer too. – John La Rooy Mar 28 '14 at 02:01

score 1 · Answer 3 · answered Mar 27 '14 at 12:40

1

def sorter(a,b):
    for i in range(len(a)):
        while i != a[i]:
            ai = a[i]
            b[i], b[ai], a[i], a[ai] = b[ai], b[i], a[ai], a[i]
    return b

answered Mar 27 '14 at 12:40

M4rtini

13,186
4
35
42

Nice, this orders both a and b. What if we want to do just b – nr.o Mar 27 '14 at 13:28
@nr.o I think it's not possible. You need to keep track of the cycles that you already sorted and as their number is O(n) you need that many places. Otherwise, nice solution M4rtini, it took me a while to dig out the algorithm 101 from my memory which got lost over the years :D – Vroomfondel Mar 27 '14 at 13:57

score 0 · Answer 4 · answered Mar 27 '14 at 12:20

0

Simple bubble sort:

for i in range( len(a) ):
    for j in range(len(a)-1-i):
         if (a[j] > a[j+1]):
             #swap a[j] & a[j+1]
             #swap b[j] & b[j+1]

answered Mar 27 '14 at 12:20

Abhishek Bansal

12,589
4
31
46

Sort list in place using another list of index

4 Answers4