Theory and Tasks for Students - Spring 2019
Сортировки - Шелла, Быстрая

Сортировка "Шелла" (Shell Sort)

Эта сортировка является небольшой модификацией сортировки Вставками - разница в том, что добавляется цикл, делящий элементы массива на группы и каждый раз сортируются только элементы внутри одной группы. Например:

Исходный массив делится на группы с расстоянием(шагом) N / 2 между элементами - т.е. каждая группа состоит из двух элементов:
8 4 6 8 2 3 5 4
Каждая группа сортируется Вставками:
2 3 5 4 8 4 6 8

Теперь шаг между элементами делится на 2, т.е. k = 4 / 2 = 2 - две группы по 4 элемента:
2 3 5 4 8 4 6 8
Каждая группа снова сортируется Вставками:
2 3 5 4 6 4 8 8

Шаг снова делится на два, объединяя все элементы в одну группу:
2 3 5 4 6 4 8 8
Последний проход Вставками:
2 3 4 4 5 6 8 8

Кроме деления пополам существуют другие последовательности, с помощью которых можно объединять элементы в группы, например, числа Фибоначчи - некоторые такие последовательности улучшают время работы алгоритма. Код:

int j, t; for (int k = arr.Length / 2; k > 0; k /= 2) { for (int i = k; i < arr.Length; i++) { t = arr[i]; j = i; while ((j >= k) && (arr[j - k] > t)) { arr[j] = arr[j - k]; j -= k; } arr[j] = t; } }

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

Это рекурсивная сортировка со сложностью от O(N log N) до O(N2) и её работа сводится к двум операциям: упорядочивание элементов относительно некоторого значения, разделяя массив чисел таким образом на две части(partition) и запуск сортировки рекурсивно от каждой из этих двух частей.
Массив A отсортирован относительно числа M, если существует некоторое i, такое что для любого j <= i, Aj <= M, и для любого j > i, Aj > M. Например, массив чисел 8 3 9 5 7 2 8 4 отсортированный относительно числа 6 может выглядеть следующим образом - 4 3 2 5 7 9 8 8 - очевидно, что таких перестановок может быть больше одной.

Для оптимального деления массива на две части значение M должно быть медианой A - однако подсчёт такого значения требует O(N) операций. Для простоты значение M часто выбирают следующими способами:

  • Центральный элемент массива - этот способ хорош на "почти упорядоченных" наборах, однако является уязвимым к подбору данных, т.к. если центральный элемент в каждой части всегда будет локальным минимумом, сложность работы алгоритма становится O(N2)
  • Медиана первого, центрального и последнего элементов - к этому способу сложнее подобрать "анти-тест".
  • Случайный элемент массива - на одних и тех же набора данных время работы алгоритма будет меняться, однако в среднем оно будет стремиться к O(N log N).

Распространённым методом разделения массива на две таких части является метод Хоара: имеются левая и правая границы, сдвигающиеся навстречу друг другу до тех пор, пока очередной граничный элемент не находится в правильной половине - т.е. для правой границы такой элемент меньше M, для левой - больше. Такие два элемента меняются местами, итерации продолжаются до тех пор, пока границы не встретятся, образуя две половины массива. Код: int m = arr[(left + right) / 2]; // важно запомнить именно значение, а не индекс элемента int c; int l = left, r = right; while (l <= r) { while (arr[l] < m) { // сдвиг левой границы l++; } while (arr[r] > m) { // сдвиг правой границы r--; } if (l <= r) { // перестановка производится даже если это один и тот же элемент c = arr[l]; // это делается для дальнейшего сдвига границ arr[l] = arr[r]; arr[r] = c; l++; r--; } } Таким образом, после разбиения, сначала будут идти элементы меньше M, потом равные M и большие M. Полный код сортировки метода QSort выглядит следующим образом:

void QSort(int[] arr, int left, int right) { if (left >= right) { // нечего сортировать return; } int m = arr[(left + right) / 2]; int c; int l = left, r = right; while (l <= r) { while (arr[l] < m) { l++; } while (arr[r] > m) { r--; } if (l <= r) { c = arr[l]; arr[l] = arr[r]; arr[r] = c; l++; r--; } } QSort(arr, left, r); // левая граница l всегда будет правее правой границы r на 1 или 2 индекса, QSort(arr, l, right); // поэтому требуется два значения и проще добавить рекурсивные вызовы в этот метод }

Существует модификация этого разбиения, называемая "толстым разбиением" - в таком случае элементы, равные по значению опорному элементу, будут находиться между двумя получившимися половинами массива, т.е. массив будет, в общем случае, делиться на три части. Для этого создаётся три индекса - левая граница, правая граница и текущий рассматриваемый элемент. Например:
M = 4
4 6 2 4 7 3 8 4
4 4 2 4 7 3 8 6
2 4 4 4 7 3 8 6
2 4 4 4 7 3 8 6
2 4 4 4 8 3 7 6
2 4 4 4 3 8 7 6
2 3 4 4 4 8 7 6

Код сортировки: void QSort(int[] arr, int left, int right) { if (left >= right) { return; } int m = arr[(left + right) / 2]; int c; int curLeft = left; // граница curLeft(curRight) указывает на элемент, int curRight = right; // слева(справа) от которого элементы находятся в правильной части, int cur = left; // не включая сам этот элемент while (cur <= curRight) { if (arr[cur] == m) { cur++; } else if (arr[cur] < m) { c = arr[curLeft]; arr[curLeft] = arr[cur]; arr[cur] = c; curLeft++; cur++; } else { c = arr[curRight]; arr[curRight] = arr[cur]; arr[cur] = c; curRight--; } } QSort(arr, left, curLeft - 1); QSort(arr, curRight + 1, right); }