Метод "пузырька" предполагает следующую физическую модель пре­образования массива данных.

Из N чисел массива всплывает (как в бокале с шампанским) "пузы­рек"- число, оказывающееся больше в случае сортировки по возрастанию, чем (N - 1) чисел. Затем всплывает "пузырек" - число, оказывающееся больше чем (N - 2) оставшихся, но меньше, чем первый всплывший "пу­зырек" и т.д.

Рассмотрим массив из 6 элементов, содержащих следующие значения:

1 3 4 2 6 5.

Пройдем по массиву, сравнивая первый элемент со вторым, вто­рой с третьим, и так далее до пятого. Будем проверять упорядо­ченность и, если она нарушена, т.е. если значение некоторого элемента больше значения следующего элемента, то поменяем эти значения местами. Например, дойдя до третьего элемента, значение которого равно 4, мы обнаружим, что оно больше значения чет­вертого элемента, равного 2. Выполнив обмен, получим новую пос­ледовательность значений:

1 3 2 4 6 5.

После этого перейдем к четвертому элементу. Теперь его зна­чение равно 4. Значение следующего элемента равно 6, оно больше 4, поэтому обмена значениями не происходит. Перейдя к пятому, обнаруживаем, что его значение больше значения шестого, и про­изводим обмен. Итак, выполнив один проход по массиву, получим последовательность значений:

1 3 2 4 5 6.

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

1 2 3 4 5 6

После этого прохода предпоследнее по величине значение 5 стало на свое место. Выполняя новые проходы, каждый раз сокра­щая количество просматриваемых элементов на 1, мы в конечном счете отсортируем все значения. Этот алгоритм можно реализовать с помощью двух циклов for - внешнего и внутреннего. Число по­вторений внешнего цикла будет на 1 меньше числа элементов мас­сива (так как последовательность из одного значения проверять нет смысла). Число повторений внутреннего цикла будет последова­тельно сокращаться от N-1 до 1:

program sort;

{Программа сортировки одномерного массива в порядке возрастания

методом обмена пар ("пузырьковая" сортировка)}

const

n = 12;

var

а : array[1..n] of integer;

x, i, j : integer;

begin

{ввод массива}

for i:=1 to n do

begin

write( ‘Введите ‘, i,’-e значение’);

readln(a[i]);

end;

{сортировка}

for i:=1 to n-1 do

for j:=1 to n-i do

if a[j]>a[j+1] then

begin

{перестановка элементов массива}

x:=a[j];

a[j]:=a[j+1];

a[j+1]:=x;

end;

{вывод отсортированных значений массива}

for i:=1 to n do

write(a[i]:5);

readln; end.

Этот алгоритм нередко называют "пузырьковой" сорти­ровкой, так как значения элементов как бы "всплывают" на свои места.

Алгоритм, сформулированный выше, — это, строго говоря, лишь один из алгоритмов сортировки обменом. Есть и другие алгоритмы, которые естественно отнести к алгоритмам сортировки обменом. Приведем пример такого алгоритма. Последовательными просмотрами чисел x₁, ..., x_n найти наименьшее i такое, что x_i > x_i+1. Поменять x_i и x_i+1 местами и возобновить просмотр с начала массива. Когда не удается найти i, массив будет упорядочен.

Другой вариант алгоритма сортировки обменом. Предположим, что k - 1 элементов массива отсортированы. Последовательным просмотром чисел x_k, ..., x_n найти такое число, что x_k > x_i, и поменять местами x_k и x_i. В результате такого просмотра чисел x_k, ..., x_n на k-м месте окажется нужное число.

Сортировка выбором

Сортировку выбором называют еще сорти­ровкой поиском последовательных минимумов.

Рассмотрим один из алгоритмов сортировки выбором.

Очевидно, что первое место в массиве должен занять наименьший элемент, второе — наименьший из всех остальных эле­ментов и т. д. Пусть x₁,…, x_i-1 уже получили нужные значения. Тогда определение индекса k наименьшего элемента из х_i, x_i+1, ... , x_п и перестановка x_i с х_k приведут к тому, что х₁, ..., x_i будут иметь нужные значения. Таким образом, схема программы решения поставленной задачи может быть следующей:

program vibor;

описания;

begin

ввести массив х;

for i:=1 to n do

begin

найти индекс k наименьшего элемента среди х_i, x_i+1 ,.., x_n;

переставить x_i с х_k ;

writeln(x_i)

end

end.

Как только элемент занял свое место, он сразу же выводится.

Приступим к детализации схемы. Ввод массива не доставляет затруднений:

for i:=1 to n do read(x[i])

и можно перейти к поиску индекса k наименьшего элемента среди x[i], ..., х[п]:

k:= i;

for j:= i+1 to n do

if x[j] < x[k] then k:= j

Для перестановки x[i] с x[k] привлекаем дополнительную переменную v: v:=x[i]; x[i]:= x[k]; x[k]:=v.

Теперь можно написать программу (считаем элементы массива действительными числами):

program vibor;

const n=20;

type vect=array[1. .n] of real;

var x : vect; v : real;

i, j, k : integer;

begin

for i:=1 to n do read(x[i]);

for i:=1 to n do

begin

k:= i;

for j:= i+1 to n do

if x[j] < x[k] then k:= j;

v:=x[i]; x[i]:= x[k]; x[k]:=v

writeln(x[i])

end

end.

При решении практических задач упорядочивание x₁, ..., x_n, как правило, сопровождается некоторыми дополнительными дей­ствиями. Например, если x₁, y₁, x₂, y₂,..., x_п, y_п—это значения аргумента х и некоторой функции y=f(x), то перестановка x₁,..., х_n должна сопровождаться перестановкой y₁, ..., y_п. Эле­менты y₁, ..., y_n переставляются так же, как x₁, ...,x_п вне зави­симости от значений самих y₁ ,.., y_п. Рассмотрим эту задачу, переставленные значения x₁, y₁, ..., x_п, y_п будут выведены в два столбца:

x₁ y₁

x₂ y₂

. . . . . . .

x_п y_п

Программа:

program tabl;

const n =20;

type vect=array[1. .n] of real;

var x, y : vect;

v : real;

i, j, k : integer;

begin

for i:=1 to n do read(x[i], y[i]);

for i:=1 to n do

begin

k:= i;

for j:=i+1 to n do

if x[j] < x[k] then k:= j;

v:=x[i]; x[i]:= x[k]; x[k]:=v;

v:=y[i]; y[i]:=y[k]; y[k]:=v;

writeln(x [i], y[i])

end

end.

Ниже приведен пример программы, в которой определяется максимальный из оставшихся элементов. Программа, реализующая этот алгоритм для сортировки по убыванию, выглядит следующим образом:

program sort1;

{Программа сортирует значения одномерного массива в порядке убывания методом выбора максимума)

const

n = 20;

var

а : array[ 1..n] of integer;

i, j, max, i_max : integer;

begin

{ввод значений элементов массива}

for i:=1 to n do

read(a[i]);

{сортировка}

for i:=1 to n-1 do

begin

max:=a[i]; {поиск максимального значения элемента}

i_max:=i; {среди значений элементов от}

for j:=i+1 to n do {i-гo до n-гo}

if a[j] > max then

begin

max:=a[j];

i_max:=j;

end;

a[i_max]:=a[i]; {обмен i-ro и максимального элементов}

a[i]:=max;

end;

{вывод отсортированного массива}

for i:=1 to n do

write(a[i]:7);

end.

Сортировка вставкой

Для упорядочивания массива попарно различных чисел x₁, ..., x_п может быть использован алгоритм сортировки простыми вставками. Опишем этот алгоритм применительно к упорядочива­нию по возрастанию.

Массив данных разделяется на две части: отсортированную и неотсортированную. Элементы из неотсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части принимается первый элемент массива.

Таким образом, будет иметь место (n - 1) проходов (где п - размер­ность массива), каждый из которых будет включать четыре действия:

- взятие очередного элемента из неотсортированной части и сохра­нение в дополнительной переменной;

- поиск позиции в отсортированной части массива для вставки элемента, взятого предыдущим действием, который бы не нару­шил порядок;

- сдвиг элементов массива для вставки элемента массива в отсор­тированную часть;

- вставка элемента в найденную позицию.

Для реализации данного метода существует несколько алгоритмов, которые отличаются способом поиска позиции вставки.

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

{Сортировка вставкой}

Program SortInsetr ;

Uses Crt;

Const n=5;

Var a :array [1..n] of byte;

b, i , j , k, p, с : byte ;

begin

ClrScr ;

Randomize; {Инициализация генератора случайных чисел} WriteLn('Исходный массив:');

{Генерация и печать исходного массива}

for i:=1 to n do

begin

a[i]:=Random(100) ;

Write(a[i]:3)

end;

{Внешний цикл сортировки}

for i:=2 to n do

begin

b:=a[i];

{Взятие элемента массива из неотсортированной части и сохранение его в дополнительной переменной}

j:=1; {Присвоение значения индексной переменной}

{Цикл поиска позиции вставки}

while b>a[j] do

j:=j+l; {Фиксация позиции вставки}

{Цикл сдвига элементов массива для вставки}

for k:= i-1 downto j do

a[k+1]:=a[k] ;

{Вставка элемента массива в найденную позицию}

а[j]:=b;

end;

WriteLn('Отсортированный массив: ') ;

{Цикл печати отсортированного массива}

for i:=1 to n do Write(a[i]:3) ;

ReadKey

end.

Один из возможных результатов работы программы выглядит следующим образом:

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

Исходный массив:

22 45 6 24 4

Отсортированный массив:

4 6 22 24 45

Алгоритм сортировки простыми вставками можно изменить следующим образом. Место, на которое надо вста­вить x_i в уже упорядоченную совокупность x₁, ..., x_i-1, опреде­ляется алгоритмом деления пополам (см. алгоритм поиска места элемента в п. 5.2). Получается новый ал­горитм сортировки, который называется алгоритмом сортировки бинарными вставками (слова «бинарная вставка» следует понимать как «вставка делением пополам»).

По числу сравнений алгоритм сортировки бинарными вставками намного лучше, чем рассмотренные выше алгоритмы. Различными авторами предпринимались попытки доказательства оптимальности алгоритма сортировки бинарными вставками и даже печатно сооб­щалось о якобы найденном доказательстве. Позднее выяснилось, что и этот алгоритм не оптимален, так как он требует восьми сравнений для упорядочивания пяти чисел, а на самом деле доста­точно семи сравнений.

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

Алгоритм быстрой сортировки заключается в следующем. Отсортируем последовательность значений одномерного массива по возрастанию. Для этого возьмем некоторый элемент последо­вательности (назовем его контрольным). Пусть это будет, напри­мер, последний элемент. Далее разделим всю последовательность на две группы: в первую поместим те, которые предшествуют кон­трольному элементу, а во вторую - те, которые должны следовать за ним. Для этого будем сравнивать с контрольным элементы пос­ледовательности, начиная с первого, и до тех пор, пока не дойдем до элемента, значение которого больше контрольного. Запомним координату этого элемента в переменной After. Далее, двигаясь от правого конца последовательности, будем сравнивать элементы с контрольным до тех пор, пока не дойдем до элемента, меньшего контрольного или до элемента с индексом After. Запомним индекс элемента, на котором закончились сравнения, в переменной Before. Совпадение значений Before и After означает, что все элементы, сто­ящие до After, меньше контрольного, а элементы с номером After и после него - больше. Поменяв местами элементы After и контроль­ный, получим правильно разбитую на две части последователь­ность: в первой, слева от контрольного, стоят элементы, меньше его, а во второй, справа, - элементы, больше контрольного. Если переменные After и Before не совпадают, то это означает, что элемент с индексом After должен стоять после контрольного, а элемент с индексом Before - перед контрольным. Поменяем мес­тами элементы Before и After и будем повторять процедуру нахож­дения элементов Before и After до тех пор, пока они не совпадут, т.е. пока не представится возможность получить последователь­ность, правильно разбитую на две группы.

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

Program Sort_Q;

Type

Vector=Array [1..20] of Byte;

Var

I, N : Byte;

Vec : Vector;

Procedure Quick_Sort(var A:Vector; First, Last : Byte);

{Процедура быстрой сортировки массива.

Входные параметры:

1) A типа Vector - сортируемый одномерный массив;

2) First, Last типа Byte - индексы, указывающие

начальный и конечный элементы сортируемой последовательности}

Var

After, Before : Byte;

Control, Work : Integer;

Begin

{обрабатываем массив, если он содержит не менее 2 элементов}

If First < Last Then

Begin

Control:=A[Last];

After:=First;

Before:=Last;

{разбиение массива на 2 группы}

Repeat

{поиск индекса первого элемента, большего или равного контрольному, After}

While A[After]<Control Do

Inc(After);

{поиск индекса элемента, меньшего контрольного во второй половине массива, Before}

While (A[Before] >= Control) And (Before > After) Do

Dec(Before);

{если во второй половине массива такой элемент найден, поменять его местами с элементом After)

If After < Before Then

Begin

Work:=A[Before];

A[Before]:=A[After];

A[After]:=Work;

End;

Until After=Before;

A[Last]:=A[After];

A[After]:=Control;

{массив разбит правильным образом:

слева от контрольного элемента находятся элементы, предшествующие ему, а справа - следующие за ним}

Quick_Sort(A, First, After-1); {обработать левую подгруппу}

Quick_Sort(A, After+1, Last); {обработать правую подгруппу}

End;

End;

Begin {Main}

Write(‘Введите размерность массива (не более20)’);

Readln(N);

For I:=1 To N Do

Begin

Write(‘Введите А[‘,I:2,’]= ‘);

Readln(Vec[I]);

End;

Quick_Sort(Vec, 1, N);

Writeln(‘Отсотированный массив’);

For I:=1 To N Do

Write (Vec[I]:4);

Writeln; End.

Процедура Quick_Sort является рекурсивной, так как в ней имеется обращение самой к себе. Рекурсия упрощает реализацию алгоритма быстрой сортировки. Этот способ сортировки является более эффективным, чем рас­смотренные нами прямые способы сортировки, хотя и не так прост для понимания.

Рассмотрим, как будет осуществляться сортировка массива из 6 элементов при выполнении программы Sort_Q. В основной программе после операторов, предназначенных для ввода с клавиатуры значений элементов исходного массива, происходит вызов процедуры быстрой сортировки Quick_Sort. При этом обрабатываемой последовательностью элементов будет весь массив А, так как индекс начального элемента равен 1, индекс конечного элемента - N (N=6). При каждом обращении к процедуре Quick_Sort программа переходит на следующий уровень или возвращается на предыдущий, в зависимости от выполнения условия: индекс начального элемента (First) меньше индекса конечного элемента (Before), т.е. First < Before. Так как условие First < Before выполняется, то программа переходит на уровень 1.

Ниже приведены изменения исходного массива (3 1 5 6 2 4) на различных уровнях обработки. Эле­менты After и Before помечены соответственно символами а и b, a контрольный элемент - символом с.

Уровень 1. Последовательность 3 1 5 6 2 4

a bc

3 1 5 6 2 4

a b с