Часто в учебных задачах, с которыми обращаются на наш форум, требуется провести упорядочение массивов, т.е. расположить элементы исходного массива в порядке возрастания или убывания. Существует множество методов (алгоритмов) решения такой задачи: лет 20-30 назад их усиленно изобретали, стараясь найти самый "оптимальный", быстрый и т.п. Сегодня, с учетом скоростей работы современных компьютеров, подобная деятельность IMHO теряет смысл, и мне представляется разумным обучать студентов владению хотя бы одним методом, лучше всего "пузырька", как самым наглядным и простым, но нет - преподы продолжают мучить детей указулями типа "использовать метод вставки". Ну что же, разберемся с основными.
Метод "пузырька"
Замечаю, что этот простейший и изящнейший метод у многих начинающих программистов вызывает трудности в понимании и даже вопросы типа "а зачем двойной цикл - массив-то одномерный?!" и т.п. Некоторые, впрочем, предпочитают бездумно откуда-нибудь перекатать фрагмент программы, при этом, как правило, путаются в двух переменных цикла, что, разумеется, "не есть хорошо". Между тем, если разобраться, то каждый легко сможет написать это самое упорядочение просто "из головы".
Сделаем разбор примера. Язык - Паскаль (что, впрочем, большого значения не имеет).
Пусть требуется упорядочить по возрастанию следующий массив A:
4 3 5 2 1
Число элементов (5) обозначим n.
Программный код:
Код:
for i:=1 to n-1 do
for j:=1 to n-i do
if A[j]>A[j+1] then
begin
D:=A[j];
A[j]:=A[j+1];
A[j+1]:=D;
end;
Полагаю, что смысл тела цикла ясен: если предыдущий элемент больше последующего, то они меняются местами. При этом обратите внимание: переменная внешнего цикла i как индекс массива не используется, она - лишь счетчик. А вот чтобы совсем было ясно, проследим последовательность выполнения программы:
Итак, напомню, исходное расположение:
4 3 5 2 1
Первое прохождение внутреннего цикла (i=1, j меняется от одного до 5-1=4):
3 4 5 2 1 (обменялись позициями 1 и 2 элементы)
3 4 5 2 1 (второй и третий стоят правильно)
3 4 2 5 1 (обменялись позициями 3 и 4 элементы)
3 4 2 1 5 (обменялись позициями 4 и 5 элементы)
Легко понять, что где бы ни находился максимальный элемент, после окончания первого внутреннего цикла он окажется последним, то есть там, где ему и место. Больше эта позиция трогаться не будет, ибо следующий внутренний цикл пойдет от 1 до 5-2=3:
3 4 2 1 5 (первый и второй стоят правильно)
3 2 4 1 5 (обменялись позициями 2 и 3 элементы)
3 2 1 4 5 (обменялись позициями 3 и 4 элементы)
Вот и второй по величине элемент (4) встал на место. Следующий цикл по j - от 1 до 5-3=2:
2 3 1 4 5 (обменялись позициями 1 и 2 элементы)
2 1 3 4 5 (обменялись позициями 2 и 3 элементы)
И, наконец, последнее прохождение по j - от 1 до 1:
1 2 3 4 5 (обменялись позициями 1 и 2 элементы)
Всё! Как видите, массив упорядочен, задача решена.
Почему это всё называется "метод пузырька"? А представьте себе наш массив в виде узкого вертикального сосуда с жидкостью, где младшие индексы - это "дно", а старшие - "верх". Тогда перемещение элемента вдоль массива подобно всплыванию пузырька воздуха в сосуде. Просто наглядная аналогия.
Естественно, если надо расположить элементы не в порядке возрастания, а в порядке убывания, то следует всего лишь поменять знак неравенства в условном операторе.
Метод вставки
Он значительно уступает "пузырьку" в простоте и наглядности и, кроме того, требует применения одного искусственного приема - добавления лишнего вспомогательного элемента (можно и без этого, но тогда программа становится громоздкой). Суть: пусть первый из n элементов уже "упорядочен", т.е. на первом месте стоит наименьший элемент. Тогда далее начиная со второго путем, как и в "пузырьке", цепочечной попарной перестановки, "гоним" справа налево элементы - сначала второй, потом третий и так до n-го. Но как выполнить условие, чтобы на первом месте стоял наименьший элемент? А вот для этого "спереди" к массиву и прицепляется лишний "нулевой" по счету элемент, заведомо меньший всех остальных. Код:
Код:
A[0]:=0; {Это если массив неотрицательный}
For i:=2 to N do
begin
j:=i;
while A[j]<A[j-1] do
begin
c:=A[j];
A[j]:=A[j-1];
A[j-1]:=c;
Dec(j);
end;
end;
Метод сортировки выбором
Тут всё совсем просто - ищем наименьший элемент, меняем местами с первым, потом ищем наименьший из оставшихся, меняем его местами со вторым и т.д. до предпоследнего, который, если надо, меняем местами с последним. Код:
Код:
For i:=1 to N-1 do
begin
d:=i;
For j:=i+1 to N do
If A[j]<A[d] then d:=j;
c:=A[i];
A[i]:=A[d];
A[d]:=c;
end;
Метод Шелла
Вот тут - внимание! МЕТОД ШЕЛЛА НЕ РЕШАЕТ ЗАДАЧУ ОКОНЧАТЕЛЬНО, он лишь осуществляет предварительную "грубую" сортировку, а окончательно это дело доводится методом вставок или пузырька. Суть: вначале обмениваются местами по возрастанию элементы, отстоящие на n/2 позиций (т.е. если n=6, то 1 с 4, 2 с 5 и 3 с 6), затем "расстояние" делится на 2 (с округлением, естественно) и процедура повторяется, и так продолжается до тех пор, пока "шаг" не станет равным 1. Код:
Код:
d:=N;
Repeat
d:=d div 2;
for i:=1 to N-d do
if A[i]>A[i+d] then
begin
c:=A[i];
A[i]:=A[i+d];
A[i+d]:=c;
end;
Until d=1;
Метод быстрой сортировки (алгоритм Хоара)
Считается одним из самых быстрых и эффективных. В то же время, весьма ненагляден и сложен для понимания. Несколько напоминает алгоритм Шелла, но, в отличие от последнего, доводит сортировку до конца. Далее я буду в основном заимствовать материал из
Википедии, как в плане описания, так и в листинге программы.
Шаги алгоритма таковы:
- Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен.
- Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы со значением меньшим или равным опорному элементу, оказались слева от него, а все элементы, превышающие по значению опорный — справа от него. Обычный алгоритм операции:
- Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.
- Вычисляется индекс опорного элемента m.
- Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше либо равен опорному.
- Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
- Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
- Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно, изменяется именно индекс опорного элемента и алгоритм продолжает свое выполнение.
- Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
- Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.
Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута обязательно и обработка гарантированно завершится.
Реализация алгоритма может быть выполнена как с использованием рекурсии, так и без таковой. В последнем случае программа существенно удлиняется.
Приведу листинг программы упорядочения целочисленного массива по возрастанию с использованием рекурсивной процедуры:
Код:
Uses CRT;
Const
N=20;
Type
Vector=Array[1..N] of Byte;
Const
M:Vector=(18,17,36,37,15,26,11,9,18,49,13,10,28,36,10,2,25,41,40,21);
Var
A:Vector;
k:Byte;
Procedure Sort(var Ar:Vector; low,high:byte);
var
i,j,m,D:byte;
begin
i:=low;
j:=high;
m:=Ar[(i+j) div 2];
repeat
while Ar[i]<m do Inc(i);
while Ar[j]>m do Dec(j);
if i<=j then
begin
D:=Ar[i];
Ar[i]:=Ar[j];
Ar[j]:=D;
Inc(i);
Dec(j);
end;
until i>j;
For k:=1 to N do
Write(Ar[k]:4);
if low<j then Sort(Ar, low, j);
if i<high then Sort(Ar, i, high);
end;
Begin
ClrScr;
A:=M;
Writeln('HOARE SORT');
Writeln;
Writeln('Initial array:');
For k:=1 to N do
Write(A[k]:4);
Writeln;
Sort(A, 1, N);
ReadKey
End.
Метод "ХХХХ"
Наткнулся тут давеча еще на один метод. Простой и глупый. Поскольку я не знаю, как он именуется, и именуется ли как-нибудь вообще, назовем его "метод ХХХХ".
Суть: вводим булеву переменную-флажок
b и начинаем многократное прохождение массива от начала до конца, меняя местами соседние "неупорядоченные" элементы, и так делаем до тех пор, пока таких "неупорядоченных" пар не останется, т.е. заданное перед очередным прохождением значение флажка останется неизменным (если же встретится хоть одна "неупорядоченная" пара, то флажок переворачивается). Код:
Код:
Repeat
b:=true;
for i:=1 to N-1 do
if A[i]>A[i+1] then
begin
D:=A[i];
A[i]:=A[i+1];
A[i+1]:=D;
b:=false;
end;
Until b;
__________
Ниже приведены скриншоты упорядочения одного и того же массива всеми рассмотренными методами. Еще раз обращаю внимание на "незавершенность" метода Шелла.