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 — ефективні операції з мін-купою**
`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
```
Напишіть функцію, яка приймає список словників продуктів (з ключами 'category' і 'price') і повертає їх відсортованими спочатку за категорією (А-Я), а потім за ціною (зростаючою) в межах кожної категорії.
Напишіть дві функції: одну, яка сортує список чисел на місці (змінюючи оригінал) і повертає None, та іншу, яка повертає відсортовану копію без зміни оригіналу.
Напишіть функцію, яка приймає список чисел і повертає їх відсортованими за частотою появи — найчастіші першими. Елементи з однаковою частотою мають залишатися у вихідному відносному порядку.
Напишіть функцію, яка приймає список кортежів (ім'я, рахунок) і повертає їх відсортованими за рахунком за спаданням. При рівних рахунках зберегти початковий порядок імен (стабільне сортування).
Напишіть функцію, яка приймає список кортежів (ім'я, вік) і повертає їх відсортованими за іменем за зростанням і за віком за спаданням при рівних іменах.
Напишіть функцію, яка правильно сортує список рядків версій (наприклад '1.10.2', '1.9.0') як номери версій, а не як звичайні рядки. Використайте functools.cmp_to_key.
Ми використовуємо необхідні cookies для роботи сайту. З вашого дозволу ми також можемо зберігати налаштування сайту та використовувати аналітичні й рекламні cookies, щоб розуміти використання сайту й підтримувати розвиток проєкту.
* Ви завжди можете змінити свій вибір у налаштуваннях сайту.
Оберіть категорії cookies
Налаштування аналітики
Можна вимкнути аналітику використання платформи. Також можна надіслати в Google Analytics запит на видалення даних про використання цього сайту, пов'язаних із цим браузером.
Навчальний workspace
Навчайтеся, читаючи, запускаючи код і розв'язуючи задачі.
Практикуйте програмування з поясненнями тем, вправами, інструментами browser IDE, перевіркою regex і тренуванням друку коду в одному workspace.
Відкривайте інструменти у вкладках.Вправи, IDE-інструменти й тренажери залишаються доступними як вкладки сайту.
Перемикайтеся без втрати контексту.Переходьте між поясненнями, кодом та утилітами, зберігаючи своє місце.
Використовуйте sidebar як карту.Ліві панелі містять навігацію, налаштування, файли, libraries та керування інструментами.
PythonJavaScriptSQLite
Одна IDE, три практичні режими
Python у браузері.Запускайте невеликі скрипти, пробуйте бібліотеки й тренуйте API-запити без встановлення.
JavaScript для швидких експериментів.Перевіряйте код для браузера й порівнюйте ідеї поруч із навчальними матеріалами.
SQLite для практики з даними.Відкривайте оглядач бази даних, переглядайте таблиці, пишіть запити й вивчайте SQL локально.
ТемаIDE
Працюйте поруч у split tabs
Тримайте інструкції перед очима.Відкрийте вправу або довідкову сторінку поруч з IDE, замість постійних перемикань.
Порівнюйте інструменти під час навчання.Розміщуйте перевірки regex, пояснення та експерименти з кодом поруч, коли це потрібно для задачі.
Закрийте split, коли завершите.Workspace повернеться до однієї сфокусованої вкладки, а відкриті вкладки сайту залишаться доступними.
Тренажер друку коду
Або звичайного тексту
Тренажер розрахований на фізичну клавіатуру.Відкрийте цей розділ на ноутбуці або комп'ютері з широким екраном. На телефоні тренування друку не працюватиме коректно.
Швидкість: 0 зн/хв
0 слів/хв
Найкраща швидкість (60с): 0 зн/хв
0 слів/хв
Помилки: 0
Загальний час: 0.0 с
Щоб тренувати сліпий друк, не підглядайте на фізичну клавіатуру.