Квадратичные и субквадратичные алгоритмы

Сортировка выбором(SelectSort)
Сортировка пузырьком(BubbleSort) и ее улучшения
Сортировка простыми вставками(InsertSort)
Cортировка Шелла (ShellSort)

Сравнение времени сортировок

Изображенный ниже график иллюстрирует разницу в эффективности изученных алгоритмов.

коричневая линия: сортировка пузырьком; синяя линия: шейкер-сортировка; розовая линия: сортировка выбором; желтая линия: сортировка вставками; голубая линия: сортировка вставками со сторожевым элементом; фиолетовая линия: сортировка Шелла.

Логарифмические и линейные алгоритмы

Пирамидальная сортировка (HeapSort)
Быстрая сортировка(QuickSort)
Поразрядная сортировка(Radix sort)

Простой выбор

Это очень естественный способ сортировки, обычно он первым приходит на ум человеку, столкнувшемуся с необходимостью упорядочения таблицы. Идея его такова. Найдем в таблице элемент с наименьшим значением и поменяем его местами с первым элементом. После этого те же действия проделаем с оставшимися (без первого) N-1 элементами таблицы, затем с N-2 элементами и т. д., пока не останется один элемент - последний. Он будет наибольшим.

На Рис. 2 этот метод отображен для последовательности прямоугольников разной высоты. Два первых элемента уже упорядочены. Затем отыскивается минимальный среди остальных. Если элементы в последовательности могут быть равными, то отыскивается первый (I) среди минимальных (таким образом достигается устойчивость сортировки). Он меняется местами с третьим.

Для составления алгоритма решения этой задачи воспользуемся, как обычно, методом пошаговой детализации. Обратим внимание на то, что для получения результата нам нужно N-1 раз находить минимальное значение в таблице, длина которой уменьшается и определяется тем, в который раз мы приступили к поиску минимума. Так, в 1-й раз мы ищем минимум среди элементов A₁, A₂,..., A_N, во 2-й - среди A₂,..., A_N, в i-й - среди A_i,...,A_N. И еще один важный момент. Поскольку после нахождения минимального элемента его нужно будет поменять местами с другим элементом таблицы, то нужно запомнить номер минимального. Следовательно, первый шаг детализации можно представить таким оператором цикла:

I := 1
пока I<=N-1
нц найти минимальный элемент и его номер в таблице A_i,..., А_N (1)
поменять местами А_i и минимальный элемент (2)
I := I+1
кц

Еще раз приведем разработанный ранее алгоритм поиска минимума.

1. K := I; X := A[I]; J := I+1
пока J<=N
нцесли A[J]<X
то X := A[J];K := J
все
кц

После выполнения этих действий значением переменной Х будет значение минимального среди элементов A_i,...,A_N, а значением К - номер этого элемента. Следовательно, пункт 2 можно записать конкретнее:

поменять местами элементы A₁ и A_K (2)

Известно, что в общем случае для взаимной перестановки в памяти двух переменных нужда третья, вспомогательная:

2. C := A[I]; A[I] := A[K]; A[K] := C.

Заметим, однако, что в нашей конкретной ситуации эта третья переменная не нужна, так как ее роль играет переменная Х из пункта 1:

2. A[K] := A[I]; A[I] := X.

Мы сэкономили одно присваивание, но это немало, так как действия выполняются в цикле многократно.

Теперь можно записать полностью алгоритм сортировки простым выбором.

алг ВЫБОР(цел N, вещтабA[1:N])
арг A, N
рез A
начвещ X, цел I, J, К
I := 1
пока I<=N-1
нц K := I; X := A[I]; J := I+1
покаJ<=N
нцесли A[J]<X
то X := a[J];K := J
все
J := J+1
кц
A[K] := A[I]; A[I] := X;
I := I+1
кц
кон

На языке Паскаль оформим этот алгоритм в виде процедуры. Параметрами ее будут массив и его длина.

const m = 10;type mass = array [l..m] of real;procedure selec(n:integer; var a:mass);var i,j,k : integer; x : real;beginfor i := 1 to n-1 dobegin k := i; x := a[i]; for j := i+l to n do if a[j] < x then begin x := a[j]; k := j end; a[k] := a[i]; a[i] := xendend;

Простой обмен

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

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

Номер элемента
Значение элемента

Будем просматривать ее от конца к началу (в принципе это не обязательно, можно организовать и обычный просмотр от начала к концу). Сравним 4-й и 5-й элементы. Они расположены не в порядке возрастания, поменяем их местами. Теперь значением 4-го элемента будет 3, а 5-го - 12. Сравним далее 3-й и 4-й элементы. Их оставим на месте. Сравнение 2-го и 3-го элементов показывает, что их нужно переставить. Теперь значение 2-го элемента - 1. И, наконец, сравним 1-й и 2-й элементы. Их тоже нужно поменять местами. Таким образом, получим:

Номер элемента
Значение элемента

Мы видим, что в результате наших действий минимальный элемент переместился на первое место в таблице. Очевидно, в дальнейшие просмотры таблицы его уже не нужно включать. Очевидно также, что каждый следующий просмотр будет приводить к постановке очередного минимального элемента в левый конец рассматриваемой части таблицы. В результате N-1 просмотра мы получим упорядоченную таблицу.

Если вообразить себе, что элементы таблицы - это пузырьки в резервуаре с водой, каждый весом, равным своему значению (что и изображено на Рис. 2), то каждый проход с обменами по таблице приводит к "всплыванию пузырька" на соответствующий его весу уровень. Благодаря такой аналогии сортировка простым обменом получила название сортировки методом "пузырька". В примере на Рис. 2 первые два элемента последовательности уже упорядочены и "всплывает" третий элемент. Знак <= (а не <) показывает условие прекращения сравнений, именноэтим достигается устойчивость сортировки "пузырьком".

Составим алгоритм решения данной задачи. Ясно, что основой алгоритма будет цикл, выполняющийся N-1 раз. Выбор границ (1 и N-1или 2 и N) повлияет затем на задание индексов сравниваемых элементов, и только. Остановимся на второй паре границ.

I := 2
пока I <= N
нц сравнить попарно элементы А_N, А_N-1, ..., А_I,А_I-1 1
I := I+1
кц

Разберем более детально пункт 1. Для попарного сравнения элементов нужен оператор цикла с границей, зависящей от I, так как при каждом новом проходе по таблице длина ее будет уменьшаться.

J := N
покаJ<=I
нцсравнить a_j и a_j-iи при необходимости поменять их местами 1.1
J := J-1
кц

Пункт 1.1. уже легко записать в виде условного оператора:

1.1 если A[J-1]>A[J]
то X := A[J-l]; A[J-1] := A[J];A[J] := X
все

Объединим теперь все шаги детализации в законченный алгоритм.

алг ОБМЕН(цел N, вещтаб A[1:N])
арг N, А
рез А
начцел I, J, вещ Х
I := 2
пока I<=N
нц J := N
пока J>=I
нцесли A[J-1]>A[J]
то X := A[J-1]
A[J-1] := A[J]
A[J] := X
все
J := J-1
кц
I := I+1
кц
кон

В паскале

const m = 10;type mass = array [l..m] of real;procedure bubble(var a:mass; n:integer);var i,j : integer; x : real;begin for i := 2 to n do for j := n downto 1 do if a[j - 1] > a[j] then begin x := a[j - 1]; a[j - 1] := a[j]; a[j] := x endend;

Простые вставки

Пусть в заданной последовательности а₁, А₂, ..., А_N первые I-1 элементов уже отсортированы. Найдем в этой части последовательности место для I-го элемента. Для этого будем сравнивать его по порядку со всеми элементами, стоящими левее, до тех пор пока не окажется, что некоторый А_K<= а_I. Затем сдвинем часть последовательности А_K+1, А_K+2, ..., А_I-1 на один элемент вправо и освободимтаким образом место А_K+1для элемента А_I , куда его и поставим. Эта последовательность действий отображена на Рис. 2 при упорядочивании последовательности треугольников разной высоты. Считая, что первые три элементауже упорядочены, ищем место для четвертого по вышеизложенному правилу. Знак<=(а не <) показывает, когда нужно прекратить сравнения, т. е. движение влево по последовательности. При этом достигается устойчивость сортировки вставками.

После того как мы проделаем подобные действия для всех элементов от 2-го до N-го, мы получим отсортированную последовательность.Отметим очень важную деталь в наших действиях. Когда мы проводим сравнение I-го элемента со всеми, стоящими левее него, может оказаться, что не найдется такого Ак, что А_K<= а_I; это произойдет, если А_I меньше всех левых элементов. На Рис. 2 эта ситуация отмечена дорожным знаком "Прочие опасности". В этом случае нужно закончить просмотр (по достижении первого элемента последовательности) и осуществить сдвиг A₁, ..., A_I-1 вправо, а элемент A_I поставить на первое место.

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

I := 2;
пока I <= N
нц найти место Ак для А_I, в упорядоченной части последовательности (1)
сдвинуть элементы А_к+1, А_к+2,:, A_i-1 вправо (2)
поставить элемент А_I на нужное место (3)
I := I+1
кц

В результате действия 1 мы должны получить номер К, индекс элемента, рядом с которым справа нужно поставить А_I.

Чтобы найти место для А_I, нужно сравнивать его последовательно со всеми левыми соседями до элемента А_K<= а_I и, если такового не окажется, остановиться на первом элементе. Действия эти - циклические, причем удобнее оформить цикл по текущему номеру элемента. Получим:

1 инициализация цикла (1.1)
пока J>0
нц сравнить элементы а_I и a_J (1.2)
кц

Обдумывая пункт 1.1 - инициализацию цикла, мы должны предусмотреть три момента. Во-первых, значение элемента а_I; нужно запомнить, так как иначе при сдвиге оно может потеряться. Во-вторых, нужно зафиксировать номер I-1 - с этого элемента начнется сравнение. В-третьих, нужно позаботиться о том, чтобы в ситуации, когда а_I, меньше A₁, A₂..., A_I-1, он смог встать на первое место. Следовательно, получаем:

1.1 X := A[I]; J := I-1; K := 1

Далее, по результатам сравнения а_I, и a_J мы должны сделать вывод о том, продолжать сравнение или нужный элемент уже найден и пора закончить цикл. Закончить цикл можно присваиванием переменной J нулевого значения. Имеем:

1.2 если A[I] >= A[J]
то K := J+1; J := 0
иначе J := J-1
все

Перейдем к детализации пункта 2. Для сдвига последовательности вправо нужно просматривать ее из конца в начало и последовательно сдвигать элементы.

2. J := I
пока J>K
нц A[J] := A[J-1]
J := J-1
кц

Пункт 3 - это один оператор присваивания:

3. A[K] := X

И наконец, законченный алгоритм сортировки простыми вставками.
алг ВСТАВКА (цел N, вещтаб A[1:N])
арг A, N
рез A
начцелI, J, K, вещ X
I := 2
пока I <= N
нц X := A[I]; J := I-1; K := 1
пока J>0
нцесли A[I] >= A[J]
то K := J+1; J := 0
иначе J := J-1
все
кц
J := I
пока J>K
нц A[J] := A[J-1]
J := J-1
кц
A[K] := X;
I := I+1
кц
кон

На паскале

Program SortByVstavka;var A: array of Integer;i, j, key: Integer;begin//Заполняем массив Afor i := 0 to Length(A) - 1 dobegin key := A[i]; j := i - 1; while (j >= 0) and (A[j] > key) do begin A[j + 1] := A[j]; j := j - 1; A[j + 1] := key; end;end;End. Найти номер минимального элемента последовательности (все элементы разные).const m = 10;type mass = array [1..m] of real;procedure nommin (x:mass; n:integer; var nom:integer);var i : integer; min : real;begin min := x[i]; nom := 1;for i := 2 to n do if min > x[i] then begin min := x[i]; nom := i endend;