В Python сортировка производится встроенной функцией sorted. Первым аргументом она принимает итерируемый объект. Это может быть список, кортеж, генератор, итератор и т.п. Возвращает отсортированный список.
>>> sorted([4, 2, 3, 1, 0]) [0, 1, 2, 3, 4] >>> sorted((3, 1, 2)) [1, 2, 3] >>> sorted(x * x for x in range(-5, 6)) [0, 1, 1, 4, 4, 9, 9, 16, 16, 25, 25]
Для словаря вернет сортированный список ключей:
>>> sorted({1: "abc", 3: "foo", -1: "baz"}) [-1, 1, 3]
Если хотим значение, надо прямо это указать:
>>> sorted({1: "abc", 3: "foo", -1: "baz"}.values()) ['abc', 'baz', 'foo']
Можно сортировать в обратном порядке:
>>> 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.
Вот пример использования этих функций:
import operator class Item: def __init__(self, name, price, qty): self.name = name self.price = price self.qty = qty def total_cost(self): return self.price * self.qty def __repr__(self): return f'({self.name} ${self.price} x {self.qty} = ${self.total_cost()})' items = [ Item("iPhone", 999, 5), Item("iMac", 2999, 2), Item("iPad", 599, 11) ] def print_items(title, item_list): print(title) print(*item_list, sep=', ', end='\n\n') print_items('Original:', items) items_by_price = sorted(items, key=operator.attrgetter('price')) print_items('Sorted by price:', items_by_price) items_by_total_cost = sorted(items, key=operator.methodcaller('total_cost')) print_items('Sorted by total cost:', items_by_total_cost) """ Original: (iPhone $999 x 5 = $4995), (iMac $2999 x 2 = $5998), (iPad $599 x 11 = $6589) Sorted by price: (iPad $599 x 11 = $6589), (iPhone $999 x 5 = $4995), (iMac $2999 x 2 = $5998) Sorted by total cost: (iPhone $999 x 5 = $4995), (iMac $2999 x 2 = $5998), (iPad $599 x 11 = $6589) """
Для списков (list) определен метод sort()
, который модифицирует исходный список, выстраивая элемента по порядку.
>>> arr = [3, 4, 1, 2, 5, 6, 0] >>> arr.sort() >>> arr [0, 1, 2, 3, 4, 5, 6]
Сортировка в Python – устойчива. Это значит, что порядок элементов с одинаковыми ключами будет сохранен в сортированной последовательности:
>>> names = ["John", "Tim", "Bill", "Max"] >>> sorted(names, key=len) ['Tim', 'Max', 'John', 'Bill']
Tim и Max — оба длины 3, Tim был перед Max, так и осталось. John остался перед Bill. Зачем это нужно? Чтобы можно было сортировать сначала по одному признаку, потому по другому (если первый совпадает).
📎 Пример. Первичный признак – оценка ученика. Вторичный – имя. Внимание: сначала сортируем по вторичному, потому по первичному:
>>> students = [(3, "Xi"), (5, "Kate"), (5, "Max"), (3, "Fil"), (5, "Abby")] >>> students_by_name = sorted(students, key=operator.itemgetter(1)) >>> sorted(students_by_name, key=operator.itemgetter(0)) [(3, 'Fil'), (3, 'Xi'), (5, 'Abby'), (5, 'Kate'), (5, 'Max')]
Внутри Python использует Timsort – гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием. Смысл в том, что в реальном мире часто встречаются частично отсортированные данные, на которых Timsort работает ощутимо быстрее прочих алгоритмов сортировки. Сложность по времени: O(n log n) в худшем случае и O(n) – в лучшем.
⚠️ CPython: не пытайтесь модифицировать сортируемый список во время сортировки. Эффект непредсказуем.
Специально для канала @pyway.