Конспект

Сортировки слиянием и быстрая (Хоара)

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

• Сортировка слиянием (merge sort) требует дополнительной памяти для слияния отсортированных массивов.
• Быстрая сортировка (quick sort) может быть реализована на месте (in-place), но в лекции представлен простой вариант с использованием дополнительных списков.
• Устойчивость сортировки — свойство не менять порядок равных элементов.
• Сортировка массива позволяет эффективно искать в нём элементы с помощью бинарного поиска.

Сортировка слиянием (Merge Sort)

Слияние отсортированных массивов
Функция merge(a, b) принимает два отсортированных списка и возвращает новый отсортированный список c.

Алгоритм слияния:

1. Создать список c длиной len(a) + len(b).
2. Инициализировать индексы i, k, n (для a, b, c) нулями.
3. Пока оба индекса i и k не вышли за границы своих массивов:
   • Сравнить a[i] и b[k].
   • Для обеспечения устойчивости сортировки, если a[i] <= b[k], скопировать a[i] в c[n]. Иначе скопировать b[k].
   • Увеличить индекс (i или k) и индекс n на 1.
4. Когда один из массивов исчерпан, скопировать оставшиеся элементы из второго массива в c.

Рекурсивная сортировка
Функция merge_sort(a):

1. Крайний случай: если длина a <= 1, массив считается отсортированным.
2. Найти середину массива (mid).
3. Рекурсивно вызвать merge_sort для левой (a[:mid]) и правой (a[mid:]) половин.
4. Слить отсортированные половины с помощью merge.
5. Важно: результат слияния (c) нужно поэлементно скопировать обратно в исходный массив a.

Примечание: Для экономии памяти можно реализовать слияние, работающее непосредственно с частями исходного массива, используя индексы.

Быстрая сортировка (Quick Sort)

Алгоритм (простая реализация с дополнительной памятью)
Функция quick_sort(a):

1. Крайний случай: если длина a <= 1, завершить работу.
2. Выбрать барьерный элемент (в примере — первый элемент массива, pivot = a[0]).
3. Создать три пустых списка: L (элементы < pivot), M (элементы == pivot), R (элементы > pivot).
4. Пройти по всем элементам массива a и распределить их по спискам L, M, R.
5. Рекурсивно вызвать quick_sort для L и R.
6. Склеить (переписать) отсортированные L, затем M, затем R обратно в массив a.

Примечание: Более эффективная реализация работает на месте, без создания дополнительных списков, используя индексы и перестановки элементов.

Проверка упорядоченности массива

Функция check_sorted(a, ascending=True) проверяет, отсортирован ли массив по возрастанию или убыванию.

• Проходит по массиву, сравнивая соседние элементы.
• Если встречается пара элементов, нарушающая заданный порядок, возвращает False.
• Параметр ascending определяет направление проверки (по умолчанию — по возрастанию).

Логика сравнения: Для универсальности используется коэффициент s = 2 * int(ascending) - 1, который преобразует True в 1, а False в -1. Условие проверки: s * a[i] > s * a[i+1].

Бинарный поиск в отсортированном массиве

Зачем сортировать? Чтобы искать элементы не линейным перебором (O(n)), а бинарным поиском (O(log n)).

Идея алгоритма:

1. Определяются границы поиска: left (левая) и right (правая).
2. На каждой итерации вычисляется середина: middle = (left + right) // 2.
3. Элемент a[middle] сравнивается с искомым значением.
4. В зависимости от результата сравнения границы поиска сужаются: отбрасывается левая или правая половина текущего интервала.

Важные варианты поиска:

• Поиск левой границы: находит индекс первого вхождения элемента (или индекс элемента, меньшего искомого, если его нет).
• Поиск правой границы: находит индекс последнего вхождения элемента (или индекс элемента, большего искомого, если его нет).

Граничные значения: left не может быть меньше -1, right не может быть больше длины массива n.