Главная :: Алгоритмы :: Алгоритмы сортировки
Иисус изменил твою жизнь. Сохранить(Да/Нет) ?

Алгоритмы сортировки

Основная задача сортировки: Пусть имеется массив численных значений A[n+1]. Необходимо упорядочить элементы массива в порядке возрастания.

Все алгоритмы сортировки делятся на четыре группы:

Иногда один и тот же метод сортировки может быть отнесен к разным группам, т.е. разделение на группы условно.

Ниже приводятся алгоритмы этих методов сортировки и результат их исполнения. Тексты соответствующих программ приведены в приложении.

Алгоритм простых вставок

Идея метода: Пусть элементы A0 … Aj-1 уже отсортированы, т.е. A0 < A1 < … < Aj-1. Тогда сравниваем элемент Aj с элементами Aj-1, Aj-2, … до тех пор, пока не обнаружим, что Aj надо вставить между Ai и Ai+1. Тогда элементы Ai+1, …, Aj-1 сдвигаются вправо на 1 и новый элемент вставляется на место Ai+1.

Алгоритм:

Среднее время работы алгоритма t = n2.

Метод Шелла (сортировка с убывающим шагом)

Идея метода. Сократить длину перемещения элементов при сортировке. В методе простых вставок средняя длина пути элемента равна N / 3 позиций. В методе Шелла процесс сортировки управляется вспомогательной последовательностью шагов hm, hm-1, …, h1, h0 = 1. Соответственно, массив A[n+1] последовательно делится на hm групп, затем на hm-1 групп и т.д. с шахматным чередованием элементов. В пределах каждой группы на каждом шаге выполняется сортировка простыми вставками. На последнем этапе сортируется весь массив, но длина пути перемещения элементов в среднем будет значительно меньше, чем в методе простых вставок.

Алгоритм:

Оптимальная последовательность шагов hj+1 = 3 hj + 1, j = 0, 1, …, m. Число m выбирается из условия hm+1 ≥ n.

Среднее время работы t = n1.25.

Обменная сортировка: метод пузырька

Идея метода: Сравнить A0 и A1 и поменять их местами, если A0 ≥ A1. Затем проделать то же самое с парами A1 и A2 и т.д. В результате этой процедуры элементы с наибольшими значениями сдвигаются вправо (всплывают как пузырек).

Простейший алгоритм:

Оптимизированный алгоритм:

Среднее время работы t ∼ n2.

Обменная сортировка: быстрая сортировка

Идея метода: Пусть имеются два указателя i и j, причем вначале i = 0 и j = n, т.е. i и j вначале указывают на граничные элементы массива A. Сравним Ai и Aj. Если обмен не требуется, то уменьшим j на 1 и повторим процесс. После нового обмена увеличим i на 1 и продолжим увеличение i до следующего обмена. Тогда снова будем уменьшать j. Когда i = j, исходный элемент A1 займет свою окончательную позицию. В результате массив окажется разделенным на два подмассива, причем в левом все элементы будут меньше A1, а в правом - больше. К каждому из этих подмассивов применяется тот же метод, пока размеры подмассивов не станут достаточно малыми (меньше некоторого значения M), после чего к ним можно применить метод простых вставок.

Сортировка посредством выбора: метод простого выбора

Идея метода: выбирается наибольший элемент и перемещается на последнюю позицию и т.д.

Алгоритм:

Среднее время t ∼ n2.

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

Идея метода: сравнить попарно элементы и в случае когда 1-й больше 2-го увеличить значение счетчика (ключа) у первого на n-1. Окончательно размещение осуществляется по значению ключей.

Алгоритм: