Конспект

Сортировки: от квадратичных до линейных

Ключевые тезисы

• Списки Python (list) — это динамические массивы, которые скрывают управление памятью и размером.
• Для понимания базовых операций важно уметь работать со статическим массивом, отслеживая его заполнение вручную.
• Существуют три классические квадратичные сортировки (O(n²)): вставками, выбором и пузырьком.
• Сортировка подсчётом — линейный алгоритм (O(n)), применимый при небольшом диапазоне возможных значений.

Работа со списками и массивами в Python

Статический массив (ручное управление)

• Требует отдельной переменной (n) для хранения текущего количества элементов.
• Добавление в конец: a[n] = x; n += 1.
• Удаление с конца: n -= 1.

Динамический массив (список list)

• Автоматически управляет памятью и размером.
• Добавление в конец: a.append(x).
• Удаление с конца с возвратом значения: x = a.pop().
• Текущая длина: len(a).

List comprehension (генерация списков)

• Лаконичный и быстрый способ создания списков.
• Синтаксис: [<выражение> for <переменная> in <итерируемый объект>].
• Пример: [x**2 for x in range(10)] создаёт список квадратов.
• Поддерживает фильтрацию: [x**2 for x in a if x % 2 == 0].
• В выражении можно использовать тернарный оператор: [0 if x < 0 else x**2 for x in a].

Квадратичные сортировки (O(n²))

Сортировка вставками (Insertion Sort)

• Идея: Часть массива (слева) поддерживается отсортированной. Новый элемент последовательно "вставляется" в эту часть, сдвигая более крупные элементы вправо.
• Инвариант: Элементы слева от текущей позиции всегда отсортированы.
• Реализация: Внешний цикл берёт элементы начиная со второго. Внутренний цикл (while) сдвигает выбранный элемент влево, пока он меньше соседа слева и не достиг начала.

Сортировка выбором (Selection Sort)

• Идея: Массив делится на отсортированную левую часть и неотсортированную правую. На каждом шаге в отсортированную часть выбирается минимальный элемент из неотсортированной и ставится на своё место.
• Инвариант: Элементы слева от текущей позиции стоят на своих окончательных местах.
• Реализация: Внешний цикл перебирает позиции для вставки минимума. Внутренний цикл ищет минимальный элемент в неотсортированной части и меняет его с элементом на текущей позиции.

Сортировка пузырьком (Bubble Sort)

• Идея: Последовательно проходим по массиву, сравнивая соседние элементы. Если они стоят в неправильном порядке, меняем их местами. За один проход "всплывает" самый крупный элемент.
• Инвариант: После k проходов k самых крупных элементов стоят на своих окончательных местах в конце массива.
• Оптимизация: Не нужно проходить по уже отсортированному "хвосту" массива.

Практика программирования: TDD-подход

Методология

1. Сначала пишется тестирующая функция, которая проверяет корректность работы алгоритма на различных наборах данных.
2. Затем реализуется сам алгоритм в виде функции.
3. Запуск тестов гарантирует корректность реализации.

Пример тестирующей функции

def test_sort(sort_algorithm):
    a = [4, 2, 5, 1, 3]
    a_sorted = [1, 2, 3, 4, 5]
    sort_algorithm(a)
    print("OK" if a == a_sorted else "FAIL")

Сортировка подсчётом (Count Sort) — O(n)

• Условие применимости: Необходимо знать небольшой диапазон возможных значений элементов (например, цифры от 0 до 9).
• Идея: Вместо перестановок элементов используется частотный анализ.
  1. Создаётся массив-счётчик f размером с диапазон значений, инициализированный нулями.
  2. За один проход по исходным данным для каждого элемента x увеличивается счётчик f[x] += 1.
  3. Результирующий отсортированный массив формируется путём вывода каждого значения d количество раз, равное f[d].
• Преимущество: Линейная скорость, не требует попарных сравнений элементов.
• Недостаток: Требует дополнительной памяти, пропорциональной диапазону значений.