Форум АНТИЧАТ - Нужно отсортировать числа ? Понимаем методы сортировок чисел

Форум АНТИЧАТ (https://forum.antichat.xyz/index.php)

- С/С++, C#, Delphi, .NET, Asm (https://forum.antichat.xyz/forumdisplay.php?f=24)

Нужно отсортировать числа ? Понимаем методы сортировок чисел

Урок 1. Необходимая теория.

Пусть дана последовательность чисел 4,2,1,5,3. Необходимо переставить элементы последовательности так, чтобы они были расставлены в возрастающем или убывающем порядке (например, 1,2,3,4,5).

Существует более 10 методов (алгоритмов) сортировки последовательностей чисел. В чем их отличие? В основном в быстроте сортировки. Например, быстрые методы отсортируют последовательность из 5000 чисел за 2 секунды, а самые простые за 15 секунд.

Помимо скорости выполнения сортировки, есть более «глубокие» способы оценить метод сортировки – это кол-во сравнений и пересылок элементов. Во время сортировки элементов, происходят их пересылки - 2 меняем с 4, 5 меняем с 1 – так чтобы они были отсортированы в возрастающем порядке. Во время пересылок, алгоритм сортировки определяет какой элемент из двух меньше, какой больше (1<2 или 2>1) и меняет их в возрастающем порядке – это называется сравнения.

В самое ближайшее время Вам нужно будет понимать, что за обозначение О(n). Это единица измерения, определяющая кол-во пересылок M или сравнений C. Понимать её стоит так,
M = O(n) – для того, чтобы алгоритм сортировки отсортировал числа в последовательности, потребуется, не больше n пересылок.
C=O(n) тоже самое, только для сравнений.
Ниже, будем обозначать кол-во чисел (элементов) в последовательности или массиве как n.

Переработал текст, новички должны понять )

Урок 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.

0_о в учебниках везде такое есть зачем тут еше писать...

а нахрена? где сортировки за n log n? Где за линейное время? Писать, так целиком. Да и всё равно нах не нужно...

Цитата:

Например, быстрые методы отсортируют последовательность из 5000 чисел за 2 секунды, а самые простые за 15 секунд.

Я не знаю алгоритмов, которым на это понадобится даже 2 секунды.

PS А у Кнута на сортировки целая книжка ушла!

Это, конечно, здорово, но для новичков, по-моему, много полезнее будет труд Дональда Эрвина.

Есть ошибки.

Я уже как-то предлагал (месяца 2 назад) написать статью на подобную тему, но товарищ desTiny меня от этого отговорил (за что я ему благодарен, честно). В принципе, неплохо, но есть один серьезный (для меня) недостаток - вообще не оформлен исходный код, читать такое практическе нереально.
Думаю, что подобную штуку надо закончить ссылкой на нормальную литературу по теме (тот же Кнут), ибо тянет она лишь на "средство для пробуждения желания у новоиспеченных адептов программирования ознакомится с темой подробнее".

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

скоро похоже он будет полезен только девочкам первокурсницам с кафедры прикладной информатики....

Цитата:

Сообщение от Gar|k

Так всегда бывает со всеми форумами :) Но я все такие бы так не сказал пока насчет Ачата, тут "поделись с собратом кодом" еще встречается довольно часто.

хорошо о сортировках расписано в книге Кнут........