Sorting tuples in python and keeping the relative order

Question

Input = [("M", 19), ("H", 19), ("A", 25)]

Output =[("A", 25), ("M" ,19), ("H", 19)]

It should sort alphabetically but when the second value is equal then it should remain in place without changing their respective places. Here M and H both have value as 19 so it is already sorted.

IIUC, you essentially want to group tuples based on the second item then sort the groups based on the letter of the first tuple in these groups? What happens if two tuples have the same letter and the number doesn't equal the number of any other tuple? — busybear, Apr 16 '20 at 05:08
This seems underspecified. Where would `("J", 30)` sort in your example, since it's between `H` and `M` in alphabetical order? If `("Z", 25)` was added, how would it effect things? Does it matter if tuples containing the same number are adjacent to each other in the input, or should the result be the same as long as they're in the same order relative to each other, regardless of where other items (with other numbers) are? — Blckknght, Apr 16 '20 at 05:39
Is a "stable sort" what you want? A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted. (from https://stackoverflow.com/a/1517824/370695) — ryanc, Apr 16 '20 at 08:01

busybear · Answer 1 · 2020-04-16T05:21:07.617

IIUC, you can group tuples by the second element. First gather them together using sorted based on the tuples' second element, then throw them in a list with groupby based on the second element. This sort will preserve the order you have them in already (this sort may also be unnecessary depending on your data).

import itertools

Input = [('M', 19), ('H', 19), ('A', 25)]
sort1 = sorted(Input, key=lambda x: x[1])
grouped = []
for _, g in itertools.groupby(sort1, lambda x: x[1]):
    grouped.append(list(g))

Then sort these grouped lists based on the first letter and finally "unlist" them.

sort2 = sorted(grouped, key=lambda x: x[0][0])
Output = [tup for sublist in sort2 for tup in sublist]

RoadRunner · Accepted Answer · 2020-04-16T06:19:01.510

You could group the items by the second value of each tuple using itertools.groupby, sort groupings by the first item in each group, then flatten the result with itertools.chain.from_iterable:

from operator import itemgetter
from itertools import groupby, chain

def relative_sort(Input):
    return list(
        chain.from_iterable(
            sorted(
                (
                    tuple(g)
                    for _, g in groupby(
                        sorted(Input, key=itemgetter(1)), key=itemgetter(1)
                    )
                ),
                key=itemgetter(0),
            )
        )
    )

Output:

>>> relative_sort([("M", 19), ("H", 19), ("A", 25)])
[('A', 25), ('M', 19), ('H', 19)]
>>> relative_sort([("B", 19), ("B", 25), ("M", 19), ("H", 19), ("A", 25)])
[('B', 19), ('M', 19), ('H', 19), ('B', 25), ('A', 25)]
>>> relative_sort([("A", 19), ("B", 25), ("M", 19), ("J", 30), ("H", 19)])
[('A', 19), ('M', 19), ('H', 19), ('B', 25), ('J', 30)]

Sorting tuples in python and keeping the relative order

2 Answers2