Под сортировкой массива понимают процесс перестановки элементов массива определенным образом. Для числовых массивов это означает упорядочивание массивов либо по возрастанию, либо по убыванию. Существуют различные метода сортировки массивов. Рассмотрим наиболее распространенные: метод линейного перебора и метод «пузырька».
Суть метода линейного перебора заключается в следующем:
1. В исходном массиве выбирается элемент с наименьшим (если сортировка по возрастанию), либо с наибольшим значением (если сортировка по убыванию).
2. Этот элемент меняется местами с первым элементом массива. Он занимает свою окончательную позицию и в дальнейшем исключается из рассмотрения. Теперь исходный массив укорачивается слева на 1 элемент.
3. Шаги 1-2 повторяются до тех пор, пока длина укороченного массива больше одного элемента.
Очередной просмотр массива в соответствии с указанным методом называется проходом.
На рис. 17 приведен тестовый пример сортировки числового массива по убыванию.
Исходный массив N = 5
-2
-4
Первый проход
J = 1
-2
-4
Второй проход
J = 2
-2
-4
Третий проход
J = 3
-4
-2
Четвертый проход
J = 4
-2
-4
Результирующий массив
Рис. 17
На рис. 17 темным цветом отмечена ячейка, с которой начинается поиск максимального элемента в каждом проходе. В каждом проходе приводится массив после обмена элементов. Как видно из тестового примера, для упорядочивания массива необходимо N-1 проходов просмотра массива, причем поиск максимального значения в укороченном массиве начинается с того элемента, номер которого совпадает с номером прохода. В приведенном тестовом примере:
Первый проход
Перебирают массив с первого элемента. Максимальное значение массива равно A[3] = 15, поэтому производят обмен A[1] = -2 и A[3] = 15.
Второй проход
Перебирают массив со второго элемента. Максимальное значение массива равно A[2] = 8, поэтому не производят обмен.
Третий проход
Перебирают массив с третьего элемента. Максимальное значение массива равно A[6] = 6, поэтому производят обмен A[3] = -2 и A[6] = 6.
Четвертый проход
Перебирают массив с четвертого элемента. Максимальное значение массива равно A[6] = -2, поэтому производят обмен A[4] = -4 и A[6] = -2.
На рис. 18 приведена блок-схема алгоритма упорядочивания по убыванию методом линейного перебора. Внешний цикл по параметру J предназначен для счетчика проходов, а внутренний по I – для просмотра элементов массива внутри каждого прохода. Перестановка пар элементов аналогична процедуре, представленной на рис. 15. Фрагмент программы приводится ниже.
…
for j:=1 to N-1 do
begin
MAX := A[j];
Imax := j;
for i := j+1 to N do
if A[i] > MAX then
begin
MAX:= A[i];
Imax:=i;
end;
A[Imax]:= A[j];
A[j]:= MAX;
end;
…
Рис.18
Если массив необходимо упорядочить по возрастанию, то необходимо в каждом проходе находить MIN.
Упорядочить массив методом «пузырька»возможно также за N-1 проходов, только в каждом проходе массив просматривается полностью. Переставляют соседние элементы по следующему правилу:
1. Если массив упорядочивают по убыванию, то в паре соседних элементов на первое место ставится больший по значению элемент.
2. Если массив упорядочивают по возрастанию, то в паре соседних элементов на первое место ставится меньший по значению элемент.
На рис. 19 приведен тестовый пример упорядочивания массива методом «пузырька» по возрастанию.
Исходный массив N = 4
Первый проход J = 1
I = 1
I = 2
I = 3
Второй проход J = 2
I = 1
I = 2
I = 3
Нет обмена
Третий проход J = 3
I = 1
I = 2
Нет обмена
I = 3
Нет обмена
Результирующий массив
Рис. 19
В каждом проходе приводится массив после процедуры обмена элементов.
На рис. 20 приведена блок-схема алгоритма упорядочивания по возрастанию методом «пузырька». Внешний цикл по параметру J предназначен для счетчика проходов, а внутренний по I – для просмотра элементов массива внутри каждого прохода (конечное значение параметра цикла I = N-1 – это максимальное количество пар обмена). Перестановка пар элементов аналогична процедуре, представленной на рис. 15. Фрагмент программы приводится ниже.
J = 3
Четвертый проход
Первый проход J = 1
Второй проход J = 2
I = 1
…