Сортировка и выбор лучших элементов

Таблица результатов олимпиады: сначала по убыванию балла, при равном балле — по алфавиту. Слова — по длине. Строки с числами — как числа, а не как текст. Сортировка сравнивает не сами элементы, а их ключи: любой порядок задаётся функцией-ключом, а несколько критериев — кортежем ключей. Ключ — это функция, которую sorted вызывает для каждого элемента, как в уроке о функции как значении.

Сортировать будем слова ["арбуз", "кот", "дом", "окно"] и баллы учеников: по длине, по нескольким критериям, а лучшего выберем без полной сортировки.

sorted возвращает новый список, а sort меняет список на месте.

a = [8, 2, 5]b = sorted(a)print(a)print(b)a.sort(reverse=True)print(a)

sorted принимает перебираемый источник и возвращает новый список. .sort() доступен у списка, меняет его на месте и возвращает None. Параметр reverse=True задаёт обратный порядок.

Строки из цифр сортируются как текст: "100" идёт раньше "20", потому что сначала сравниваются первые символы. Если нужен числовой порядок, преобразуй данные в числа либо задай числовой ключ.

print(sorted(["20", "100", "3"]))print(sorted(["20", "100", "3"], key=int))

Ключ сортировки — значение, по которому сравнивают элемент; сам элемент не меняется.

words = ["арбуз", "кот", "дом", "окно"]print(sorted(words, key=len))

Передаётся функция len, а не результат len(...). При сортировке Python применяет функцию ключа к каждому элементу и использует полученные значения для упорядочивания. Посмотри по шагам, как это происходит:

Ключ решает всё: меняется ключ — меняется порядок, а сами слова остаются теми же. Переключай правила и сравни результаты:

Несколько критериев задают кортежем: кортежи сравниваются слева направо. Кортежи сравниваются лексикографически: сначала первые элементы; если они равны — вторые, и так далее. Это похоже на порядок слов в словаре, но применяется к любым сравнимым элементам.

students = [("Анна", 91), ("Илья", 84), ("Марк", 91)]ordered = sorted(    students, key=lambda student: (-student[1], student[0]))print(ordered)

Балл сортируется по убыванию благодаря минусу: 91 превращается в −91, что меньше −84. При равных баллах имя сортируется по возрастанию. reverse=True для всего кортежа развернул бы оба критерия, поэтому это не то же самое. Как кортежи ключей решают порядок — по шагам:

Сортировка устойчива, а один лучший элемент находят без сортировки. Сортировка Python устойчива: элементы с одинаковым ключом сохраняют взаимный исходный порядок. Например, слова "кот" и "дом" имеют одинаковую длину и остались в исходной последовательности.

Если нужен только лучший элемент, нет необходимости сортировать всё:

words = ["арбуз", "кот", "дом", "окно"]longest = max(words, key=len)print(longest)print(min([], default=None))

max проходит элементы один раз и помнит лучший; при одинаковом ключе лучшим остаётся первый. Для возможно пустого источника можно указать default=None. Как max выбирает — по шагам:

Сквозная задача курса получает продолжение: не одно наибольшее, а два. Для [5, -2, 10, 7] выражение sorted(numbers, reverse=True)[:2] даёт [10, 7] — сортировка по убыванию и срез первых двух.

Сортировка по одному показателю не доказывает, что жадный выбор верен. Выбор «самого выгодного сейчас» называют жадным алгоритмом. Иногда его правильность можно доказать. Например, если нужно купить максимум предметов при ограниченном бюджете и все цены неотрицательны, выгодно брать самые дешёвые: любой набор из k предметов стоит не меньше суммы k минимальных цен.

prices = [50, 20, 70, 10, 40]budget = 100count = 0spent = 0for price in sorted(prices):    if spent + price > budget:        break    spent += price    count += 1print(count, spent)

Самые дешёвые 10, 20 и 40 стоят 70; следующая цена 50 уже не помещается. Никакие четыре предмета не уложатся в 100: четыре самых дешёвых стоят 120.

Но сортировка по одному показателю не решает произвольный выбор оптимального набора. Если у предметов разные цены и полезности, выбор по цене или отношению полезности к цене для неделимых предметов может оказаться неверным. Сначала доказательство подхода, затем код.