В Python сортировка производится встроенной функцией sorted. Первым аргументом она принимает итерируемый объект. Это может быть список, кортеж, генератор, итератор и т.п. Возвращает отсортированный список.
>>> sorted([4, 2, 3, 1, 0])
[0, 1, 2, 3, 4]>>> sorted(x * x for x in range(-5, 6))
[0, 1, 1, 4, 4, 9, 9, 16, 16, 25, 25]Можно сортировать в обратном порядке:
>>> sorted([4, 2, 3, 1, 0], reverse=True)
[4, 3, 2, 1, 0]
Если сортируемые элементы – списки, словари или объекты, то воспользуемся параметром key. Мы передаем в key нечто вызываемое (имя функции, lambda и т.п), и при сортировки элементы сравниваются по результату вызова key на элементе. Результатом key должно быть число, строка или что-то другое сравнимое между собой.
📎 Пример. Сортировка списка строк по длине строки:
>>> sorted(["foo", "bazooka", "", "game"], key=len)
['', 'foo', 'game', 'bazooka']
📎 Пример. Сортировка списка кортежей по 0 или 1 элементу каждого.
>>> people = [("Bill", "Gates"), ("Tim", "Cook"), ("Donald", "Trump")]
>>> sorted(people, key=lambda t: t[0])
[('Bill', 'Gates'), ('Donald', 'Trump'), ('Tim', 'Cook')]
>>> sorted(people, key=lambda t: t[1])
[('Tim', 'Cook'), ('Bill', 'Gates'), ('Donald', 'Trump')]Для этой же цели удобно использовать функцию operator.itemgetter:
>>> import operator
>>> sorted(people, key=operator.itemgetter(0))
[('Bill', 'Gates'), ('Donald', 'Trump'), ('Tim', 'Cook')]
Еще полезные функции из operator:
• attrgetter(name) – для получение значения атрибута объекта с именем name
• methodcaller(name[, args...]) – для получения результата вызова метода name у объекта. Опционально с аргументами args.
Вот пример кода с attrgetter и methodcaller.
Для списков (list) определен метод sort(), который модифицирует исходный список, выстраивая элемента по порядку.
>>> arr = [3, 4, 1, 2, 5, 6, 0]
>>> arr.sort()
>>> arr
[0, 1, 2, 3, 4, 5, 6]
Сортировка в Python – устойчива. Это значит, что порядок элементов с одинаковыми ключами будет сохранен в сортированной последовательности. Пример.
Внутри Python использует Timsort – гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием. Смысл в том, что в реальном мире часто встречаются частично отсортированные данные, на которых Timsort работает ощутимо быстрее прочих алгоритмов сортировки. Сложность по времени: O(n log n) в худшем случае и O(n) – в лучшем.
⚠️ CPython: не пытайтесь модифицировать сортируемый список во время сортировки. Эффект непредсказуем.
@python_job_interview