7.3. Сортировка элементов массива

Сортировкой, или упорядочиванием называется расположение этих объектов по возрастанию или убыванию согласно определённому линейному отношению порядка, такому как « ≤ » для чисел.

Сортировка бывает внутренней и внешней. При внутренней сортировке все сортируемые данные помещаются в оперативную память компьютера, где можно получить доступ к данным в любом порядке (то есть используется модель памяти с произвольным доступом). Внешняя сортировка применяется тогда, когда объём упорядочиваемых данных слишком большой, чтобы все данные можно было поместить в оперативную память. Здесь узким местом является механизм перемещения больших блоков данных от устройств внешнего хранения данных к оперативной памяти компьютера и обратно. Так как физически непрерывные данные надо для удобного перемещения организовывать в блочную структуру, то применяют разнообразные методы внешней сортировки.

В данной главе рассмотрим алгоритмы внутренней сортировки: метод «пузырька», метод вставками, сортировка посредством выбора и алгоритм «быстрой» сортировки. Будем предполагать, что сортируемые объекты являются целыми и действительными числами, символьными массивами, содержащими одно или несколько полей. Одно из полей, называемое ключом, имеет такой тип данных, что на нем определено отношение линейного порядка "<".

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

7.3.1. Сортировка методом «пузырька»

Самым простым методом сортировки является так называемый метод "пузырька". Предположим, что записи, подлежащие сортировке, хранятся в массиве, расположенном вертикально. Записи с малыми значениями ключевого поля более "легкие" и "всплывают" вверх наподобие пузырька. При первом проходе вдоль массива, начиная проход снизу, берется первая запись массива, и ее ключ поочередно сравнивается с ключами последующих записей. Если встречается запись с более "тяжелым" ключом, то эти записи меняются местами. При встрече с записью с более "легким" ключом эта запись становится "эталоном" для сравнения, и все последующие записи сравниваются с этим новым, более "легким" ключом. В результате запись с наименьшим значением ключа окажется в самом верху массива. Во время второго прохода вдоль массива находится запись со вторым по величине ключом, которая помещается под записью, найденной при первом проходе массива, т.е. на вторую сверху позицию, и т.д. Отметим, что во время второго и последующих проходов вдоль массива нет необходимости просматривать записи, найденные за предыдущие проходы, так как они имеют ключи, меньшие, чем у оставшихся записей. Другими словами, во время i-гo прохода не проверяются записи, стоящие на позициях выше i. В листинге 1 приведен описываемый алгоритм, в котором через А обозначен массив из n записей (тип данных rеcordtype). Здесь и далее предполагаем, что одно из полей записей называется key (ключ) и содержит значения ключей.

Листинг 1. Алгоритм „пузырька"

temp: recordtype;

for i := n-1 downto 1 do

for j:= 2 to i + 1 do

if A[j].key < A[j - 1].key then

begin

temp := A[j];

A[j] := A[j-1];

A[j-1] := temp;

end;

Пример 7.1. В табл.5 приведены годы знаменитых извержений вулканов.

Таблица 5. Значения годов знаменитых извержений вулканов

i	начальное положение	1-й проход	2-й проход	3-й проход	4-й проход	5-й проход
1	1902	1669	1699	1699	1699	79
2	1669	1883	1883	1883	79	1699
3	1883	1902	1902	79	1883	1883
4	1963	1963	79	1902	1902	1902
5	1980	79	1963	1963	1963	1963
6	79	1980	1980	1980	1980	1980
i	i = 6	i = 5	i = 4	i = 3	i = 2	i = 1

Применим алгоритм "пузырька" для упорядочивания списка годов извержений вулканов в возрастающем порядке их значения, считая, что отношением линейного порядка в данном случае является отношение порядка ”<” над полем ключей. В табл. 2 показаны пять проходов алгоритма (в данном случае n = 6). Линии указывают позицию, выше которой записи уже упорядочены. После пятого прохода все записи, кроме последней, стоят на нужных местах, но последняя запись не случайно оказалась последней — она также уже стоит на нужном месте. Поэтому сортировка заканчивается.

Задача 7.10. Дан целочисленный массив размерностью 10 элементов. Упорядочить элементы данного массива по возрастанию методом «пузырька».

Вариант №1. Осуществим сортировку элементов массива по возрастанию, где пары стоящих элементов просматриваются снизу вверх.

Листинг программы

program task1;

uses crt;

const n = 10;

type vector = array [1..n] of integer;

var

a : Vector;

b, t, j : integer;

temp : integer;

begin

clrscr;

{формирование элементов массива случайным образом}

randomize;

for i :=1 to n do

begin

a[i] := random(11)-5;

writeln ('a[', i, ']=', a[i]:3);

end;

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

b := n;

while (b>0) do

begin

t := 0;

for j := 1 to b-1 do

begin

if (a[j] >a [j+1]) and (a[j] <> a[j+1]) then

begin

temp := a[j];

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

a[j+1] := temp;

t := j;

end; {оператора if}

end; {оператора for}

b := t;

end; {оператора while}

{вывод упорядоченного массива на экран}

writeln ('Отсортированный массив по возрастанию');

for i := 1 to n do

writeln ('a[', i, ']=', a[i]:3);

readln;

end.

Вариант №2. Осуществим сортировку элементов массива по возрастанию, где пары стоящих элементов просматриваются сверху вниз.

Листинг программы

program task1;

uses crt;

const n = 10;

type vector = array [1..n] of integer;

var

a : Vector;

i, j : integer;

temp : integer;

begin

clrscr;

{формирование элементов массива случайным образом}

randomize;

for i :=1 to n do

begin

a[i] := random(11)-5;

writeln ('a[', i, ']=', a[i]:3);

end;

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

for i := n-1 downto 1 do

begin

for j := 2 to i+1 do

begin

if a[j] < a[j-1] then

begin

temp := a[j];

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

a[j-1] := temp;

end;

end;

end;

{вывод упорядоченного массива на экран}

writeln ('Отсортированный массив по возрастанию');

for i := 1 to n do

writeln ('a[', i, ']=', a[i]:3);

readln;

end.