53. Алгоритмы сортировки массива
Задача сортировки ставится следующим способом. Пусть имеется массив целых или вещественных чисел a1,...,an. Требуется переставить элементы этого массива так, чтобы после перестановки они были упорядочены по неубыванию: а1 ≤ a2 ≤ ... ≤an или невозрастанию: а1 ≥ a2 ≥ ... ≥an. Существует множество алгоритмов сортировки, каждый из которых имеет свои характеристики по скорости. Сортировка обменами (пузырьком)Этот алгоритм считается самым простым и самым медленным. Шаг сортировки состоит в проходе снизу вверх по массиву. При этоmпросматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то они меняются местами.
После первого прохода по массиву "вверху" (в начале массива) оказывается самый "легкий" (минимальный) элемент – отсюда аналогия с пузырьком, который всплывает. Следующий проход делается до второго сверху элемента, таким образом, второй по величине элемент поднимается на правильную позицию и так далее.
Проходы делаются по все уменьшающейся нижней части массива до тех
пор, пока в ней не останется только один элемент. На этом сортировка
заканчивается, так как последовательность упорядочена по возрастанию.
Procedure SortBubble( var a:massiv); // сортировка обменами (пузырьком) var i,j,temp:integer; Begin
for i:=1 to N do begin // i - номер прохода for j:= N downto i+1 do // внутренний цикл прохода
if ( a[j-1] > a[j] ) then begin //если "левый" больше "правого" temp:=a[j-1]; a[j-1]:=a[j]; a[j]:=temp; //меняем местами элементы
end; end
end;
Сортировка выбором
Сортировка выбором выполняется несколько быстрее, чем сортировка методом пузырька. Алгоритм заключается в следующем: нужно найти элемент массива, имеющий наименьшее значение, переставить его с первым элементом, затем проделать тоже самое, начав со второго элемента и т.д. Таким образом, создается отсортированная последовательность путем присоединения к ней одного элемента за другим в правильном порядке. На i-м шаге выбирается наименьший из элементов a[i] ... a[n] и меняем его местами с a[i].
Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.
//сортировка выбором
procedure SortSelect(var a:massiv);
var
i, j, Imin, Min: integer;
begin
for i:=1 to N do
begin // i - номер текущего шага
Imin:=i; Min:=a[i]; for j:=i+1 to N do // цикл выбора наименьшего элемента
if( a[j]<Min)then begin
173
Imin:=j; Min:=a[j];// Imin - индекс наименьшего элемента end;
a[Imin] := a[i]; a[i] := Min; // меняем местами наименьший с a[i] end
end;
Сортировка простыми вставками
Просматривается массив и каждый новый элемент a[i] вставляется на подходящее место в уже упорядоченную совокупность a[1],...,a[i-1]. Это место определяется последовательным сравнением a[i] с упорядоченными элементами a[1],...,a[i-1]. Таким образом в начале массива "вырастает" отсортированная последовательность.
Однако в сортировке пузырьком или выбором можно было четко заявить, что на i-м шаге элементы a[1]...a[i-1]стоят на правильных местах и никуда более не переместятся. Здесь же подобное утверждение будет более слабым: последовательность a[1]...a[i-1] упорядочена. При этом по ходу алгоритма в нее будут вставляться (см. название метода) все новые элементы.
Рассмотрим действия алгоритма на i-м шаге. Как говорилось выше, последовательность к этому моменту разделена на две части: готовую a[1]...a[i-1] и неупорядоченную a[i]...a[n].
На следующем, i-м каждом шаге алгоритма берем a[i] и вставляем на нужное место в готовую часть массива. Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте(вставка завершена), либо они меняются местами и процесс повторяется.
Таким образом, в процессе вставки мы "просеиваем" элемент X к началу массива, останавливаясь в случае, когда
1. Hайден элемент, меньший X. 2. Достигнуто начало последовательности.
// сортировка простыми вставками
Procedure SortInsert(var a:massiv);
var i, j, temp:integer;
begin
for i:=2 to N do
begin // цикл проходов, i - номер прохода
temp := a[i];
174
j:=i-1; // поиск места элемента в готовой последовательности while (j>0) AND (a[j] > temp) do begin
a[j+1] := a[j]; // сдвигаем элемент направо, пока не дошли
dec(j); end;
// место найдено, вставить элемент
a[j+1] := temp;
end; end;
No шага
Сортировка простыми вставками является наиболее быстрой из рассмотренных. На практике очень часто используются оптимизированные (улучшенные) алгоритмы сортировки на основе алгоритма простых вставок, например, алгоритм простых вставок со «сторожевым» элементом или алгоритм Шелла.