Пример сортировки массива по возрастанию методом обмена
На рисунках 8.8 – 8.12 подробно показаны изменения массива в процессе сортировки обменом во время первого прохода по массиву.
Рисунок 8.8 – Массив перед сортировкой обменом
Рисунок
8.9
– Массив после первого обмена элементов
Рисунок
8.10 – Массив после второго обмена
элементов
Рисунок
8.11 – Массив после третьего обмена
элементов
Рисунок
8.12
– Массив после первого прохода
После первого прохода по массиву максимальный элемент стал на свое место, поэтому во втором проходе по массиву этот элемент уже анализироваться не будет, то есть число сравнений во втором проходе будет на одно меньше..
Второй проход по массиву рассмотрим менее детально. Его результаты представлены на рисунке 8.13.
Рисунок
8.13 – Второй проход по массиву
Во втором проходе понадобился только один обмен, и в результате не только A[4], но и A[3] оказались на своих местах.
После третьего прохода все элемента оказались на своих местах. В общем случае для сортировки массива понадобился бы еще один проход, но данном случае сортировка уже закончена. В этом особенность сортировки обменом – число проходов может быть меньше максимально возможного количества.
Результаты последнего прохода по массиву показаны на рисунке 8.14.
Рисунок
8.14 – Результаты третьего проход по
массиву
Процедура сортировки массива методом обмена
procedure SortBubl(var a: TArray100; count: integer);
var last, i, x: integer; ok: boolean;
begin
last := count;
repeat
ok := true;
for i:= 1 to last - 1 do
if a[i] > a[i+1] then
begin
x := a[i];
a[i] := a[i+1];
a[i+1] := x;
ok := false;
end;
last := last - 1;
until ok;
end;
7.1.10Сортировка вставкой или включением.
Суть алгоритма в следующем – элементы массива разделяют на упорядоченную часть А[1], А[2], ……, А[i-1], которая располагается в начале массива, и остальную, неупорядоченную часть А[i], ……., А[N], а затем, по одному, элементы из неупорядоченной части переносятся в упорядоченную.
Перед началом сортировки упорядоченная часть состоит всего из одного, первого элемента, а все остальные элементы располагаются во второй части массива.
Рисунок 8.15 - Алгоритм сортировки по возрастанию методом вставки
Последовательные шаги алгоритма сортировки заключаются в том, что первый элемент из неупорядоченной части сравнивается с последним элементом упорядоченной последовательности. Если оказывается, что порядок расположения сравниваемых элементов не соответствует требованиям сортировки, то элемент из неупорядоченной части извлекается и переносится в упорядоченную часть. Место для этого элемента освобождается путем сдвига упорядоченных элементов вправо на место извлеченного элемента. Сдвиги упорядоченных элементов на одну позицию вправо продолжаются до тех пор, пока не будет найдено место для элемента, извлеченного из неупорядоченной последовательности.
Как видно из рисунка 8.15, в алгоритме есть два цикла.
Во внешнем цикле последовательно изменяется номер левой границы неупорядоченной области от значения i = 2 до i = count. В теле этого цикла производится сравнение элементов, находящихся по обе стороны от границы, разделяющей упорядоченную и неупорядоченную части. Если порядок нарушен, то первый элемент неупорядоченной последовательности запоминается в переменной tmp и, тем самым, освобождается место для сдвигов упорядоченных элементов вправо.
Внутренний цикл обеспечивает последовательные сдвиги упорядоченных элементов вправо, начиная с последнего, до тех пор, пока не будет найдено место для первого элемента из неупорядоченной области.
Возможность вставки элемента определяется одним из двух условий.
mas[j-1] <= buf < mas[j] и 1 < j < i, т.е. найдено место внутри упорядоченной последовательности.
j=1 , т.е. tmp является самым малым элементом и вставляется на первое место в упорядоченной части массива.
После завершения цикла сдвигов элемент массива из переменной tmp переносится на найденное место в упорядоченной последовательности.