Сортировки

Cортировка выбором

Сортировка выбором работает по следующему принципу. Сначала из всего массива выбирается минимальный элемент и меняется с нулевым элементом. Далее мы выбираем второй по величине элемент и меняем его с первым элементом. После этого проделываем похожую операцию со второй ячейкой массива и т.д. Таким образом мы получим отсортированный массив. Выбор элемента для очередной ячейки массива выпол-няется за O(n), всего таких выборов n − 1. Итого, время работы алгоритма – O(n²). Сортировка выбором является неустойчивой.

Cортировка вставками

Сортировка вставками очень похожа на сортировку пузырьком, однако между ними различие есть, и не стоит их путать. На каждой итерации алгоритма будет выполняться сортировка только первых i элементов. Пусть уже первые i − 1 элементов отсортированы, и мы добавили в конец новый элемент. Этот новый элемент нужно передвинуть на правильное место, чтобы снова получить отсортированный массив. Будем просто пытаться обменивать его местами с соседом слева, если этот сосед больше нового элемента. Эта сортировка – устойчивая, время работы – O(n²).

Глупая сортировка или сортировка дурака

Алгоритм этой сортировки заключается в следующих шагах. Просматриваем массив слева-направо и по пути сравниваем соседей. Если мы встретим пару взаимно неотсортированных элементов, то меняем их местами и возвращаемся в начало массива. И так далее, пока массив не будет отсортирован, что можно проверить, сравнивая на итерации количество пропусков перестановки с длиной массива. Такой алгоритм потребует O(n³) времени.

Сортировка пузырьком

Попробуем улучшить алгоритм глупой сортировки.

Теперь, когда мы встретили пару взаимно неотсортированных элементов и поменяли их местами, мы не возвращаемся в начало, а продолжаем двигаться по массиву. Таким образом, выполнив один проход по массиву, мы вытолкнем в его конец максимальный элемент. После второго прохода мы вытолкнем второй по величине элемент и так далее. Всего надо будет сделать O(n²) операций. Данная сортировка является устойчивой.

Существует множество оптимизаций алгоритма пузырька, одна из простейших заключается в заведении флаговой переменной, которая проверяет, осуществлялась ли перестановка. Так как мы уверены, что справа в правильном порядке расположены наибольшие, "всплывшие ранее" элементы, а очередной сортируемый элемент не "всплывает" наверх, то и оставшиеся справа элементы сортировать не нужно.

Сортировка подсчётом

Данный алгоритм сортировки не является универсальным. Для него необходимо заранее знать диапазон сортируемых значений. Например, это могут быть цифры, буквы или слова. Алгоритм является однопроходным и состоит в следующем.

Для наглядности будем считать, что сортируем массив A произвольного размера, состоящего только из десятичных цифр. Диапазон значений (ключей) известен keys = {0, 1, .., 9}, всего 10 элементов. Заведём счётчики counter_key, где key ∈ keys, под каждый ключ и инициируем их нулями. Затем совершим проход по массиву, подсчитывая количество каждого ключа, и записывая это количество в нужный счётчик counter_k. Наконец, перезапишем исходный массив, помещая на первые counter₀ позиций нули, на следующие counter₁ позиций единицы, и так далее.

Стадия подсчёта занимает n = len(A) операций, стадия формирования отсортированного массива m = len(keys) операций. Таким образом, сортировка подсчётом требует O(n + m) операций.

Поразрядная сортировка

Ещё одна не универсальная сортировка. Применяется для целых чисел без длинной арифметики и коротких строк.

Её инвариантом является упорядоченность элементов по разрядам. Т.е. после i итерации числа отсортированы во всём массиве, если "смотреть" только на разряды правее i.

Например, для сортировки целых чисел, заводим всего 10 буферов buffer_i, по одному на цифру. Совершая первый проход по массиву, в buffer_0 заносим числа, оканчивающиеся на 0, в buffer_1 оканчивающиеся на 1 и так далее. Затем пересобираем исходный массив, занося в него числа сначала из buffer_0, затем из buffer_1... После сборки очищаем буферы. Во втором проходе будем работать с обновлённым массивом и заполним буферы по тому же принципу, но смотреть будем на второй младший разряд (разряд десятков). После прохода обновим массив, склеивая его из буферов, а затем очищая их. Всего нам понадобится столько проходов, сколько разрядов у наибольшего по абсолютному значению числа.

Данная сортировка линейна по времени O(n).

Контест №6

Контест заключается в реализации описанных выше алгоритмов сортировки и решении нескольких дополнительных задач.

Участвовать в контесте. (Альтернативная ссылка)