Урок 2. Простые (квадратичные) методы сортировки чисел.
Метод прямого выбора
Метод прямого выбора, самый простой. Суть : находим наименьший элемент массива и обмениваем его с первым элементом массива. После этого, первый элемент больше не рассматриваем. Среди оставшихся элементов находим наименьший элемент и обмениваем его со вторым элементом массива. Среди оставшихся элементов находим наименьший и переставляем его на третье место и так далее.
Например, наш массив состоит из n чисел.
Количество M = 3*(n-1), а C = (n*n-n)/2. Метод не зависит от исходной отсортированности массива, т.е. значения М и С не меняются, даже если сортируется уже отсортированный массив. Сортировка методом прямого выбора неустойчива.
Приводится код на Паскале. Количество M и C считается, чтобы Вам было все понятно.
procedure sort; {sortirovka massiva metodom pryamogo vibora}
var tmp,i: integer;
begin
writeln;
for i:=1 to n-1 do
begin
min:=i; {min element primem ravnim i}
for j:=i+1 to n do {naxodim min. element iz dvux sosednix}
begin
{C}c:=c+1;
if a[j]<a[min] then min:=j; end;
tmp :=a[i]; {obmenivaem znacheniyami sosednie elementi}
a[i] :=a[min];
a[min]:=tmp;
{M}m:=m+3;
end;
writeln;
end;
Вывод : метод самый простой. Кол-во пересылок не меняется сортировке любого массива, т.е. он «тупо» сортирует все и даже где не нужно делает сравнения и пересылки. При сортировке любого (упорядоченного/неупорядоченного) массива из 100 чисел получим M=297, C=4950.
Пузырьковая сортировка
Просматриваем элементы от конца массива к началу, сравниваем между собой соседние элементы. Если правый элемент aj будет меньше чем левый aj-1, j=n, n-1, … ,2, то поменяем их местами. После этого, при первом проходе наименьший элемент переместится на первое место и можно не учитывать его при сортировке оставшейся части массива. При втором проходе наименьший элемент из оставшихся перейдет на второе место. После (n-1) проходов массив отсортируется.
В алгоритме : i – номер прохода по массиву, j – индекс правого элемента в текущей паре.
procedure sort;
begin
for i:=1 to n-1 do
for j:=n downto i+1 do
begin
{C}c:=c+1;
if (a[j]<a[j-1]) then {esli sosednie elementi odin menshe drugogo}
begin {to obmenivaem ix mestami}
tmp:=a[j];
a[j]:=a[j-1];
a[j-1]:=tmp;
{M} m:=m+3; {podshet kol-va peresilok}
end;
end;
end;
Количество C = (n*n-n)/2 (равно кол-ву сравнений в методе прямого выбора), количество пересылок будет меньше : если сортируем уже упорядоченный по возрастанию массив, то M = 0; если сортируем упорядоченный по убыванию, то M=3*(n*n-n)/2.
Вывод : метод зависит от начальной упорядоченности массива, а это уже плюс, по сравнению с методом Прямого выбора. Для случайного массива, получим M = 7977 и C = 4950, для упорядоченного M=0 и C = 4950. При сортировке упорядоченного массива уже прогресс – кол-во пересылок намного меньше.
Шейкерная сортировка
Теперь немного проанализируем. Возьмем метод Пузырьковой сортировки.
1) Если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована, получается мы ее можем исключить из рассмотрения.
2) Также, при движении от конца массива к началу минимальный элемент переходит на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.
Т.е. можно немного модифицировать метод пузырьковой сортировки. А именно, границы рабочей части массива (часть массива, к которой происходит сортировка и M и C) устанавливаются в месте последнего обмена на каждом проходе. Массив просматривается поочередно справа налево и слева направо.
В алгоритме :
L – левая граница рабочей части массива.
R – правая граница рабочей части массива.
n – количество элементов в массиве
L: = 1, R: = n, k: = n,
procedure sort;
begin
l:=1; r:=n; k:=n;
while l<r do
begin
for j:=r downto l+1 do
begin
{C}c:=c+1;
if a[j]<a[j-1] then
begin
tmp:=a[j]; a[j]:=a[j-1]; a[j-1]:=tmp; {M}m:=m+3;
k:=j;
end;
end;
l:=k;
for j:=l to r-1 do
begin
{C}c:=c+1;
if (a[j]>a[j+1]) then
begin
tmp:=a[j]; a[j]:=a[j+1]; a[j+1]:=tmp; {M}m:=m+3;
k:=j;
end;
end;
r:=k;
end;
end;
Количество пересылок если сортируем уже упорядоченный по возрастанию массив, то M = 0; если сортируем упорядоченный по убыванию, то M=3*(n*n-n)/2. Количество сравнений : если массив отсортирован перед сортировкой в возрастающем порядке, то C = n-1; если в убывающем, C = (n*n-n)/2.
При сортировке упорядоченного по возрастанию массива (100 элементов) получим M = 0 и C=99 , для случайног M = 6579 и C = 3142.
Вывод : метод ещё более совершенен по сравнению с двумя первыми.
В алгоритмах, нужно дописать, только ввод массива, вывод его на экран и вывод M и C.