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

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

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

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

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

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

Самым простым методом сортировки является так называемый метод "пузырька". Предположим, что записи, подлежащие сортировке, хранятся в массиве, расположенном вертикально. Записи с малыми значениями ключевого поля более "легкие" и "всплывают" вверх наподобие пузырька. При первом проходе вдоль массива, начиная проход снизу, берется первая запись массива, и ее ключ поочередно сравнивается с ключами последующих записей. Если встречается запись с более "тяжелым" ключом, то эти записи меняются местами. При встрече с записью с более "легким" ключом эта запись становится "эталоном" для сравнения, и все последующие записи сравниваются с этим новым, более "легким" ключом. В результате запись с наименьшим значением ключа окажется в самом верху массива. Во время второго прохода вдоль массива находится запись со вторым по величине ключом, которая помещается под записью, найденной при первом проходе массива, т.е. на вторую сверху позицию, и т.д. Отметим, что во время второго и последующих проходов вдоль массива нет необходимости просматривать записи, найденные за предыдущие проходы, так как они имеют ключи, меньшие, чем у оставшихся записей. Другими словами, во время 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-й проход
	1902
					79
	1883			79
			79
		79
	79
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;

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

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

for i := 1 to n do

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

readln;

end.

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

Метод называется сортировкой вставками, так как на i-м этапе "вставляем" i-й элемент A[i] в нужную позицию среди элементов А[1], А[2], ..., A[i - 1], которые уже упорядочены. После этой вставки первые i элементов будут упорядочены. Сказанное можно записать в виде следующей псевдопрограммы:

for i : = 2 to n do

переместить A[i] на позицию j < i такую, что

A[i] < A[k] для j ≤ k < i и

либо A[i] ≥ A[j - 1], либо j = 1

Чтобы сделать процесс перемещения элемента A[i] более простым, полезно ввести элемент А[0], чье значение ключа будет меньше значения ключа любого элемента А[1], ..., А[n]. Постулируем существование константы - ∞ типа keytype, которая будет меньше значения ключа любой записи, встречающейся на практике. Если такую константу нельзя применить, то при вставке A[i] в позицию j - 1 надо проверить, не будет ли j = 1, если нет, тогда сравнивать элемент A[i] (который сейчас находится в позиции j) с элементом A[j - 1]. Описанный алгоритм показан в листинге 3.

Листинг 2. Сортировка вставками

А[0].key:= - ∞;

for i:= 2 to n do

Begin

j:= i;

while (A[j] < A[j - 1]) or (j>=1) do

Begin

temp := A[j];

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

A[j-1] := temp;

j:= j - 1

End

Пример 7.2. В табл. 6 показан начальный список из табл. 5 и последовательные этапы алгоритма вставкой для i = 2, 3, ..., 6. После каждого этапа алгоритма элементы, расположенные выше линии, уже упорядочены, хотя между ними на последующих этапах могут быть вставлены элементы, которые сейчас находятся ниже линии.

Таблица 6. Этапы сортировки вставками

i	начальное положение	1-й проход	2-й проход	3-й проход	4-й проход	5-й проход
			1669
	1669	1902




i	i = 1	i = 2	i = 3	i = 4	i = 5	i = 6