Зліва направо по черзі порівнюються два сусідні елементи, і якщо їх взаємне розташування не відповідає заданій умові впорядкованості, то вони міняються місцями. Далі беруться два наступних сусідні елементи і так далі до кінця масиву.
Після одного такого проходу на останній n-ій позиції масиву буде стояти максимальний (або мінімальний) елемент ( "сплив" перший "бульбашка"). Оскільки максимальний (або мінімальний) елемент вже стоїть на своїй останній позиції, то другий прохід обмінів виконується до (n-1) -го елемента. І так далі. Всього потрібно (n-1) прохід.
Завдання. У зошиті накресліть схему роботи розглянутого алгоритму довільно обраного масиву.
Розгляньте процедуру, що реалізовує вище розглянутий алгоритм:
Procedure Obmen (Var a. Array1);
Var
i, j, f, g: integer;
Begin
for i: = n downto 2 do
for j: = 1 to i-1 do
if a [j]> a [j + 1]
then
begin
f: = a [j];
a [j]: = a [j + 1];
a [j + 1]: = f;
end;
End;
Завдання. Складіть програму сортування одновимірного масиву розглянутим методом.
Розглянемо використання рекурсії для побудови алгоритму сортування значень масиву.
Алгоритм реалізується в такий спосіб: в деякому відрізку масиву вибирається центральне (серединне) значення; всі елементи з лівої частини відрізка, що перевершують центральне значення, переміщаються в праву частину, і навпаки. На наступному кроці (для якого використовуються рекурсивні виклики цієї ж процедури) алгоритм повторюється для обох частин відрізка.
Розгляньте процедуру, упорядочивающую по зростанню значення з масиву Massiv в діапазоні індексів Left..Right.
Procedure QuickSort (Left, Right. Integer; Massiv. Array1);
Var
i, j, x, y. integer;
Begin
i: = Left;
j: = Right;
x: = Massiv [(Left + Right) div 2];<>
repeat
while Massiv [i]
while Massiv [j]> x do
Dec (j);
if i<=j
then
begin
y: = Massiv [i];
Massiv [i]: = Massiv [j];
Massiv [j]: = y;
Inc (i);
Dec (j);
end;
until i> j;
if Left
QuickSort (Left, j);
if i
QuickSort (i, Right);
End;