 |
Сортировка элементов массива
|
|
|
|
Сортировкой, или упорядочиванием называется расположение этих объектов по возрастанию или убыванию согласно определённому линейному отношению порядка, такому как «≤» для чисел.
Сортировка бывает внутренней и внешней. При внутренней сортировке все сортируемые данные помещаются в оперативную память компьютера, где можно получить доступ к данным в любом порядке (то есть используется модель памяти с произвольным доступом). Внешняя сортировка применяется тогда, когда объём упорядочиваемых данных слишком большой, чтобы все данные можно было поместить в оперативную память. Здесь узким местом является механизм перемещения больших блоков данных от устройств внешнего хранения данных к оперативной памяти компьютера и обратно. Так как физически непрерывные данные надо для удобного перемещения организовывать в блочную структуру, то применяют разнообразные методы внешней сортировки.
В данной главе рассмотрим алгоритмы внутренней сортировки: метод «пузырька», метод вставками, сортировка посредством выбора и алгоритм «быстрой» сортировки. Будем предполагать, что сортируемые объекты являются целыми и действительными числами, символьными массивами, содержащими одно или несколько полей. Одно из полей, называемое ключом, имеет такой тип данных, что на нем определено отношение линейного порядка "<".
Задача сортировки состоит в упорядочивании последовательности записей таким образом, чтобы значения ключевого поля составляли неубывающую последовательность.
Сортировка методом «пузырька»
Самым простым методом сортировки является так называемый метод "пузырька". Предположим, что записи, подлежащие сортировке, хранятся в массиве, расположенном вертикально. Записи с малыми значениями ключевого поля более "легкие" и "всплывают" вверх наподобие пузырька. При первом проходе вдоль массива, начиная проход снизу, берется первая запись массива, и ее ключ поочередно сравнивается с ключами последующих записей. Если встречается запись с более "тяжелым" ключом, то эти записи меняются местами. При встрече с записью с более "легким" ключом эта запись становится "эталоном" для сравнения, и все последующие записи сравниваются с этим новым, более "легким" ключом. В результате запись с наименьшим значением ключа окажется в самом верху массива. Во время второго прохода вдоль массива находится запись со вторым по величине ключом, которая помещается под записью, найденной при первом проходе массива, т.е. на вторую сверху позицию, и т.д. Отметим, что во время второго и последующих проходов вдоль массива нет необходимости просматривать записи, найденные за предыдущие проходы, так как они имеют ключи, меньшие, чем у оставшихся записей. Другими словами, во время 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;
end;
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.
|
|
|
