Иногда возникает необходимость сортировать не только числовые последовательности, но и более сложные объекты, а также сохранять при сортировке знание о позиции элемента в исходной последовательности. Всё это в языки Python делается довольно просто и элегантно.
Начнём с того, что Python умеет сравнивать списки:
>>> [1, 2, 3, 4] > [2, 3, 4]
False
>>> [1, 2, 3, 4] > [1, 2, 3, 4]
False
>>> [1, 3, 2, 4] > [1, 2, 3, 4]
True
>>> [1, 2, 3, 4, 5] > [1, 2, 3, 4]
True
>>> [10] > [1, 2, 3, 4]
True
>>> [2, -100] > [1, 2, 3, 4]
True
Сравнивает он их поэлементно (или лексикографически), то есть сначала сравнивает первые элементы.
Владелец большего первого элемента и сам больше.
Если же первые элементы совпадают, то мы сравниваем вторые элементы.
Так мы движемся до тех пор, пока i-й элемент одного списка не станет больше i-го элемента второго списка, тогда первый победит.
Если какой-то список закончился раньше, то он меньше.
А иначе списки совпадают.
Итак, если списки можно сравнивать, то их можно и сортировать.
>>> A = [[1, 2, 3, 4], [2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4, 5], [10], [2, -100], [1, 3, 2, 4], [1, 2, 3, 4]]
>>> sorted(A)
[[1, 2, 3, 4],
[1, 2, 3, 4],
[1, 2, 3, 4],
[1, 2, 3, 4, 5],
[1, 3, 2, 4],
[2, -100],
[2, 3, 4],
[10]]
Конечно же, для того, чтобы такой «сложный» список можно было отсортировать, необходимо, чтобы его элементы можно было сравнить.
>>> sorted([[1, 2], [1, 'a']])
Traceback (most recent call last):
File "< string >", line 301, in runcode
File "< interactive input >", line 1, in < module >
TypeError: unorderable types: str() < int()
Теперь представим себе, что нам нужно отсторировать список, но при этом нужно сохнанить знание о том, где стоял элемент до сортировки.
Для этого можно применить такой трюк: заменим число x на кортеж (x, i), где i — номер элемента в списке.
И после этого отсортируем.
my_list = [39, 12, 21, 77, 21, 51, 48, 21, 42, 76]
for i in range(len(my_list)):
my_list[i] = (my_list[i], i)
my_list.sort()
print(my_list)
[(12, 1), (21, 2), (21, 4), (21, 7), (39, 0), (42, 8), (48, 6), (51, 5), (76, 9), (77, 3)]
Благодаря такой операции мы знаем, что числа 21 стояли на 2, 4 и 7-й позиции в исходном списке, а наибольшее число 77 было на позиции 3. Всё это можно сделать короче с помощью генератора списков:
my_list = [39, 12, 21, 77, 21, 51, 48, 21, 42, 76]
hacked_list = sorted([(my_list[i], i) for i in range(len(my_list))])