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

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

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

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

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

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

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

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

Алгоритм:

1. Организуется цикл по j = 1, 2, …, n, в котором выполняются пункты 2-5.
2. Присвоить i = j - 1, B = A_j.
3. Пока B ≤ A_i или i ≥ 0 выполнять пункт 4, иначе перейти к пункту 5.
4. Присвоить A_{i + 1} = A_i, i = i - 1.
5. A_{i + 1} = B.

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

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

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

Алгоритм:

1. Присваиваем g = 2^m+1 и организуем цикл по k = (m, 0) для пунктов 2-6.
2. g = g / 2. Цикл по j = (g, n) для пунктов 3-6.
3. Присвоить B = A_j, i = j - g.
4. Пока B ≤ A_i и i ≥ 0 выполнять пункт 5.
5. Присвоить A_i+g = A_i, i = i - g.
6. Присвоить A_i+g = B.

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

Среднее время работы t = n^1.25.

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

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

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

Цикл по i = (0, n-1).
Цикл по j = (0, n-1).
Сравнить A_j и A_j+1. Если A_j > A_j+1, то меняем элементы местами B = A_j, A_j = A_j+1, A_j+1 = B.

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

1. Присвоить k = n (k — индекс самого верхнего элемента, о котором еще не известно, занял ли он свое место).
2. Присвоить i = -1.
3. Цикл по j = (0, k-1).
4. Если A_j > A_j+1, то B = A_j, A_j = A_j+1, A_j+1 = B, i = j.
Если i = -1, то завершить работу цикла. Иначе присвоить k = i и вернуться к пункту 2.

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

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

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

1. Присвоить l = 0, r = n (границы).
2. Если r - l < M, то перейти к пункту 8. Иначе присвоить i = l, j = r, B = A_l.
3. Если B < A_j, то j = j - 1 и повторить этот шаг.
4. Если j ≤ i, то A_i = B и перейти к пункту 7. В противном случае A_i = A_j и i = i + 1.
5. Если A_i < B, то i = i + 1 и повторить этот шаг.
6. Если j ≤ i, то A_j = B и i = j. В противном случае A_j = A_i, j = j - 1 и перейти пункту 3.
7. Если r - i ≥ i - l, то запомнить пару чисел (i + 1, r) и установить r = i - 1. В противном случае запомнить (l,i - 1) и установить l = i + 1. Вернуться к пункту 2.
8. Сортировка простыми вставками подмассива от l + 1 до r.
9. Взять последнюю запомненную пару (l′,r′), присвоить l = l′, r = r′ и вернуться к шагу 2. Если больше пар не осталось, то сортировка завершена.

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

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

Алгоритм:

Цикл по j = (n,1).
Найти наибольший из элементов A_j, A_j-1, …, A₀. Пусть это элемент A_i.
Поменять местами A_i и A_j: B = A_i, A_i = A_j, A_j = B.

Среднее время t ∼ n².

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

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

Алгоритм:

Занулить массив ключей k_i = 0, i = (0, n).
Цикл по i = (n, 1).
Цикл по j = (i-1, 0).
Если A_i < A_j, то k_j = k_j + 1 иначе k_i = k_i + 1.
Завершить циклы i и j.
Переместить элемент A_j на позицию k_j. Для этого лучше использовать новый массив: B[k_j] = A[j].