Python · Синтаксис · Промежуточный

Сортировка и компараторы

10 задач

sorted() и list.sort() с функциями key=, reverse и многоключевыми компараторами.

Краткое введение в тему и пояснения перед упражнениями (упражнения ниже):

sorted() vs list.sort(), key=, reverse= и стабильность сортировки

#
В Python есть две встроенные функции сортировки. Разница важна: ```python nums = [3, 1, 4, 1, 5] sorted(nums) # [1, 1, 3, 4, 5] — возвращает НОВЫЙ список, nums не изменён nums.sort() # изменяет nums НА МЕСТЕ, возвращает None # Распространённая ошибка: result = nums.sort() # result равен None! ``` Используй `sorted()`, когда нужно сохранить оригинал или когда входные данные — любой итерируемый объект (не только список). Используй `.sort()` для сортировки на месте и экономии памяти. **Обратный порядок** ```python sorted([3, 1, 2], reverse=True) # [3, 2, 1] [3, 1, 2].sort(reverse=True) # на месте: [3, 2, 1] # Альтернатива через reversed() — возвращает итератор, не список list(reversed(sorted([3, 1, 2]))) # [3, 2, 1] ``` **key= — сортировка по производному значению** Функция `key` вызывается по одному разу для каждого элемента, результат используется для сравнения: ```python words = ['banana', 'fig', 'apple', 'cherry'] sorted(words, key=len) # ['fig', 'apple', 'banana', 'cherry'] sorted(words, key=str.lower) # алфавитно без учёта регистра sorted(words, key=lambda w: w[-1]) # по последнему символу ``` **Стабильность — равные элементы сохраняют исходный порядок** Сортировка Python является *стабильной*: если два элемента равны при сравнении, они появляются в том же относительном порядке, что и во входных данных. Это гарантировано — не деталь реализации. ```python students = [ {'name': 'Alice', 'grade': 'B'}, {'name': 'Bob', 'grade': 'A'}, {'name': 'Carol', 'grade': 'B'}, ] by_grade = sorted(students, key=lambda s: s['grade']) # [Bob(A), Alice(B), Carol(B)] # Alice стоит перед Carol после сортировки по оценке, # потому что они были в таком порядке изначально. ``` Стабильность важна для многоключевой сортировки: сначала сортируй по вторичному ключу, затем по первичному — стабильность сохраняет вторичный порядок внутри равных первичных. ```python # Сортировка по оценке (первичная), затем по имени (вторичная) step1 = sorted(students, key=lambda s: s['name']) # сначала по имени step2 = sorted(step1, key=lambda s: s['grade']) # затем по оценке (стабильно!) # Результат: внутри одной оценки студенты в алфавитном порядке ```

Ключи-кортежи, operator.itemgetter и многопольная сортировка

#
**Ключи-кортежи — многопольная сортировка за один проход** Когда функция ключа возвращает кортеж, Python сравнивает поэлементно — сначала первое поле, затем второе как критерий разрешения ничьей: ```python students = [ {'name': 'Alice', 'grade': 'B', 'age': 22}, {'name': 'Bob', 'grade': 'A', 'age': 20}, {'name': 'Carol', 'grade': 'B', 'age': 21}, ] # Первичное: оценка по возрастанию, вторичное: возраст по возрастанию sorted(students, key=lambda s: (s['grade'], s['age'])) # [Bob(A,20), Carol(B,21), Alice(B,22)] ``` **operator.itemgetter и operator.attrgetter** Для типичных случаев функции модуля `operator` чище и немного быстрее лямбда: ```python from operator import itemgetter, attrgetter # Сортировка списка словарей по ключу sorted(students, key=itemgetter('grade')) # то же, что lambda s: s['grade'] sorted(students, key=itemgetter('grade', 'age')) # многопольная одним вызовом # Сортировка объектов по атрибуту from dataclasses import dataclass @dataclass class Person: name: str age: int people = [Person('Alice', 30), Person('Bob', 25), Person('Carol', 30)] sorted(people, key=attrgetter('age', 'name')) # по возрасту, затем по имени ``` **Обратный порядок для одного поля в многопольной сортировке** Нет встроенного способа обернуть только одно поле в ключе-кортеже. Стандартный трюк — отрицание числовых полей: ```python # Оценка по возрастанию, возраст по УБЫВАНИЮ sorted(students, key=lambda s: (s['grade'], -s['age'])) # [Bob(A,20), Alice(B,22), Carol(B,21)] ``` Для нечисловых полей используй двухпроходный трюк со стабильной сортировкой из Блока 1. **Сортировка строк без учёта регистра** ```python names = ['banana', 'Apple', 'cherry', 'Date'] sorted(names) # ['Apple', 'Date', 'banana', 'cherry'] (заглавные первыми) sorted(names, key=str.lower) # ['Apple', 'banana', 'cherry', 'Date'] (настоящий алфавит) sorted(names, key=str.casefold) # то же, но лучше для символов с диакритикой ``` **max() и min() используют тот же key=** ```python words = ['banana', 'fig', 'apple'] max(words, key=len) # 'banana' min(words, key=len) # 'fig' youngest = min(students, key=itemgetter('age')) ```

heapq, cmp_to_key и устройство Timsort

#
**heapq — эффективные операции с мин-кучей** `heapq` поддерживает список как мин-кучу. Наименьший элемент всегда по индексу 0. Используй, когда нужен повторный доступ к минимуму, а не полный отсортированный список: ```python import heapq nums = [5, 1, 3, 8, 2] heapq.heapify(nums) # преобразовать список в кучу на месте: [1, 2, 3, 8, 5] heapq.heappush(nums, 0) # добавить 0 и сохранить свойство кучи heapq.heappop(nums) # удалить и вернуть наименьший: 0 heapq.heappop(nums) # следующий наименьший: 1 # Получить N наименьших / наибольших без полной сортировки heapq.nsmallest(3, nums) # [2, 3, 5] — O(n + k log n) heapq.nlargest(3, nums) # [8, 5, 3] # С функцией ключа: tasks = [{'priority': 3, 'name': 'писать тесты'}, {'priority': 1, 'name': 'исправить баг'}] heapq.nsmallest(1, tasks, key=lambda t: t['priority']) # [{'priority': 1, ...}] ``` **functools.cmp_to_key — устаревшие функции сравнения** Старый код (стиль Python 2) может использовать функции сравнения, возвращающие -1/0/1. `cmp_to_key` адаптирует их к современному интерфейсу `key=`: ```python from functools import cmp_to_key def compare_last_char(a, b): if a[-1] < b[-1]: return -1 if a[-1] > b[-1]: return 1 return 0 sorted(['banana', 'fig', 'apple'], key=cmp_to_key(compare_last_char)) # ['banana', 'apple', 'fig'] — по последнему символу: a, e, g ``` По возможности предпочитай функции `key=` — они чище и быстрее. **Timsort — почему сортировка Python быстрая** Встроенная сортировка Python использует **Timsort** — гибрид сортировки слиянием и сортировки вставками. Ключевые свойства: - Время: O(n log n) в худшем случае, O(n) на уже отсортированных данных - Память: O(n) дополнительной памяти - Стабильная: равные элементы сохраняют исходный порядок - Адаптивная: обнаруживает и использует существующие отсортированные последовательности в данных Сортировка почти отсортированного списка значительно быстрее, чем случайного. **Когда использовать heapq vs sorted** ``` Потребность Используй ──────────────────────────────────── ────────────────── Все элементы отсортированы один раз sorted() / .sort() Повторное получение минимума heapq Топ-N из большого потока heapq.nsmallest/nlargest Очередь с приоритетом heapq ```

Упражнения:

01

Сортировка по абсолютному значению

#
Напишите функцию, которая принимает список целых чисел и возвращает их отсортированными по абсолютному значению по возрастанию.
def sort_by_abs(numbers):
    pass


print(sort_by_abs([-5, 3, -1, 4, -2, 8]))
Решение 
def sort_by_abs(numbers):
    return sorted(numbers, key=abs)


print(sort_by_abs([-5, 3, -1, 4, -2, 8]))
02

Сортировка строк без учёта регистра

#
Напишите функцию, которая принимает список строк и возвращает их отсортированными по алфавиту без учёта регистра.
def sort_words(words):
    pass


print(sort_words(["Banana", "apple", "Cherry", "date"]))
Решение 
def sort_words(words):
    return sorted(words, key=str.lower)


print(sort_words(["Banana", "apple", "Cherry", "date"]))
03

Сортировка по фамилии

#
Напишите функцию, которая принимает список полных имён (строки вида 'Имя Фамилия') и возвращает их отсортированными по фамилии по алфавиту.
def sort_by_last_name(names):
    pass


names = ["Alice Smith", "Bob Johnson", "Carol Adams", "Dave Brown"]
print(sort_by_last_name(names))
Решение 
def sort_by_last_name(names):
    return sorted(names, key=lambda name: name.split()[-1])


names = ["Alice Smith", "Bob Johnson", "Carol Adams", "Dave Brown"]
print(sort_by_last_name(names))
04

Сортировка словарей по нескольким полям

#
Напишите функцию, которая принимает список словарей продуктов (с ключами 'category' и 'price') и возвращает их отсортированными сначала по категории (А-Я), затем по цене (возрастающей) внутри каждой категории.
def sort_products(products):
    pass


products = [
    {"name": "Bread", "category": "food", "price": 2},
    {"name": "TV", "category": "electronics", "price": 500},
    {"name": "Milk", "category": "food", "price": 1},
    {"name": "Phone", "category": "electronics", "price": 800},
]
for p in sort_products(products):
    print(p)
Решение 
def sort_products(products):
    return sorted(products, key=lambda p: (p["category"], p["price"]))


products = [
    {"name": "Bread", "category": "food", "price": 2},
    {"name": "TV", "category": "electronics", "price": 500},
    {"name": "Milk", "category": "food", "price": 1},
    {"name": "Phone", "category": "electronics", "price": 800},
]
for p in sort_products(products):
    print(p)
05

Сортировка на месте vs возврат нового

#
Напишите две функции: одну, которая сортирует список чисел на месте (изменяя оригинал) и возвращает None, и другую, которая возвращает отсортированную копию без изменения оригинала.
def sort_inplace(numbers):
    pass


def sort_copy(numbers):
    pass


nums = [3, 1, 4, 1, 5]
sort_inplace(nums)
print(nums)

nums2 = [3, 1, 4, 1, 5]
result = sort_copy(nums2)
print(nums2)
print(result)
Решение 
def sort_inplace(numbers):
    numbers.sort()


def sort_copy(numbers):
    return sorted(numbers)


nums = [3, 1, 4, 1, 5]
sort_inplace(nums)
print(nums)

nums2 = [3, 1, 4, 1, 5]
result = sort_copy(nums2)
print(nums2)
print(result)
06

Топ N

#
Напишите функцию, которая принимает список чисел и целое число n, и возвращает n наибольших чисел в порядке убывания.
def top_n(numbers, n):
    pass


print(top_n([3, 1, 4, 1, 5, 9, 2, 6, 5, 3], 3))
Решение 
def top_n(numbers, n):
    return sorted(numbers, reverse=True)[:n]

# Или эффективнее для больших списков:
def top_n(numbers, n):
    import heapq
    return heapq.nlargest(n, numbers)


print(top_n([3, 1, 4, 1, 5, 9, 2, 6, 5, 3], 3))
07

Сортировка по частоте

#
Напишите функцию, которая принимает список чисел и возвращает их отсортированными по частоте появления — наиболее частые первыми. Элементы с одинаковой частотой должны оставаться в исходном относительном порядке.
def sort_by_frequency(numbers):
    pass


print(sort_by_frequency([4, 2, 2, 8, 3, 3, 1, 3]))
Решение 
def sort_by_frequency(numbers):
    from collections import Counter
    freq = Counter(numbers)
    return sorted(numbers, key=lambda n: -freq[n])


print(sort_by_frequency([4, 2, 2, 8, 3, 3, 1, 3]))
08

Стабильность сортировки

#
Напишите функцию, которая принимает список кортежей (имя, счёт) и возвращает их отсортированными по счёту по убыванию. При равных счётах сохранить исходный порядок имён (стабильная сортировка).
def rank_players(players):
    pass


players = [("Alice", 90), ("Bob", 85), ("Carol", 90), ("Dave", 85)]
print(rank_players(players))
Решение 
def rank_players(players):
    return sorted(players, key=lambda p: -p[1])


players = [("Alice", 90), ("Bob", 85), ("Carol", 90), ("Dave", 85)]
print(rank_players(players))
09

Сортировка с разными направлениями

#
Напишите функцию, которая принимает список кортежей (имя, возраст) и возвращает их отсортированными по имени по возрастанию и по возрасту по убыванию при равных именах.
def sort_people(people):
    pass


people = [("Alice", 30), ("Bob", 25), ("Alice", 25), ("Bob", 35)]
print(sort_people(people))
Решение 
def sort_people(people):
    return sorted(people, key=lambda p: (p[0], -p[1]))


people = [("Alice", 30), ("Bob", 25), ("Alice", 25), ("Bob", 35)]
print(sort_people(people))
10

Пользовательская сортировка через functools.cmp_to_key

#
Напишите функцию, которая правильно сортирует список строк версий (например '1.10.2', '1.9.0') как номера версий, а не как обычные строки. Используйте functools.cmp_to_key.
from functools import cmp_to_key


def sort_versions(versions):
    pass


print(sort_versions(["1.10.2", "1.9.0", "2.0.0", "1.9.10", "1.1.0"]))
Решение 
from functools import cmp_to_key


def sort_versions(versions):
    def compare(a, b):
        a_parts = list(map(int, a.split(".")))
        b_parts = list(map(int, b.split(".")))
        if a_parts < b_parts: return -1
        if a_parts > b_parts: return 1
        return 0
    return sorted(versions, key=cmp_to_key(compare))


print(sort_versions(["1.10.2", "1.9.0", "2.0.0", "1.9.10", "1.1.0"]))