Antichat снова доступен.
Форум Antichat (Античат) возвращается и снова открыт для пользователей.
Здесь обсуждаются безопасность, программирование, технологии и многое другое.
Сообщество снова собирается вместе.
Новый адрес: forum.antichat.xyz
 |
Нужно отсортировать числа ? Понимаем методы сортировок чисел |
14.09.2008, 01:55
|
|
Участник форума
Регистрация: 30.08.2008
Сообщений: 128
Провел на форуме:
668329
Репутация:
106
|
|
Нужно отсортировать числа ? Понимаем методы сортировок чисел
Урок 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.
Переработал текст, новички должны понять ) |
|
|
14.09.2008, 01:59
|
|
Участник форума
Регистрация: 30.08.2008
Сообщений: 128
Провел на форуме:
668329
Репутация:
106
|
|
Урок 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.
|
|
|
|
14.09.2008, 02:04
|
|
Познающий
Регистрация: 20.07.2007
Сообщений: 99
Провел на форуме:
1562993
Репутация:
25
|
|
0_о в учебниках везде такое есть зачем тут еше писать...
|
|
|
|
14.09.2008, 22:22
|
|
Reservists Of Antichat - Level 6
Регистрация: 04.02.2007
Сообщений: 1,152
Провел на форуме:
3008839
Репутация:
1502
|
|
а нахрена? где сортировки за n log n? Где за линейное время? Писать, так целиком. Да и всё равно нах не нужно...
Например, быстрые методы отсортируют последовательность из 5000 чисел за 2 секунды, а самые простые за 15 секунд.
Я не знаю алгоритмов, которым на это понадобится даже 2 секунды.
PS А у Кнута на сортировки целая книжка ушла!
__________________
Bedankt euch dafür bei euch selbst.
H_2(S^3/((z1, z2)~(exp(2pi*i/p)z1, exp(2pi*q*i/p)z2)))=Z/pZ
Последний раз редактировалось desTiny; 14.09.2008 в 22:25..
|
|
|
|
14.09.2008, 23:42
|
|
Постоянный
Регистрация: 30.08.2007
Сообщений: 773
Провел на форуме:
3069349
Репутация:
808
|
|
|
|
|
|
06.01.2010, 05:32
|
|
Новичок
Регистрация: 04.11.2009
Сообщений: 11
Провел на форуме:
4191
Репутация:
0
|
|
Есть ошибки.
|
|
|
|
06.01.2010, 20:49
|
|
Участник форума
Регистрация: 03.07.2009
Сообщений: 151
Провел на форуме:
638378
Репутация:
41
|
|
Я уже как-то предлагал (месяца 2 назад) написать статью на подобную тему, но товарищ desTiny меня от этого отговорил (за что я ему благодарен, честно). В принципе, неплохо, но есть один серьезный (для меня) недостаток - вообще не оформлен исходный код, читать такое практическе нереально.
Думаю, что подобную штуку надо закончить ссылкой на нормальную литературу по теме (тот же Кнут), ибо тянет она лишь на "средство для пробуждения желания у новоиспеченных адептов программирования ознакомится с темой подробнее".
|
|
|
|
07.01.2010, 01:17
|
|
Постоянный
Регистрация: 20.03.2009
Сообщений: 564
Провел на форуме:
991929
Репутация:
395
|
|
форум (или раздел, честно в остальные даже страшно заходить такой тупизм) превращается не в хакерский форум и уже давно не в поделись с собратом кодом и даже не в помоги ламеру, а в научи нуба программированию )
скоро похоже он будет полезен только девочкам первокурсницам с кафедры прикладной информатики....
|
|
|
|
07.01.2010, 20:40
|
|
Участник форума
Регистрация: 03.07.2009
Сообщений: 151
Провел на форуме:
638378
Репутация:
41
|
|
Сообщение от Gar|k
форум (или раздел, честно в остальные даже страшно заходить такой тупизм) превращается не в хакерский форум и уже давно не в поделись с собратом кодом и даже не в помоги ламеру, а в научи нуба программированию )
скоро похоже он будет полезен только девочкам первокурсницам с кафедры прикладной информатики....
Так всегда бывает со всеми форумами  Но я все такие бы так не сказал пока насчет Ачата, тут "поделись с собратом кодом" еще встречается довольно часто.
|
|
|
|
07.01.2010, 22:10
|
|
Новичок
Регистрация: 02.01.2010
Сообщений: 26
Провел на форуме:
33560
Репутация:
15
|
|
хорошо о сортировках расписано в книге Кнут........
|
|
|
|
|
|
|
Здесь присутствуют: 1 (пользователей: 0 , гостей: 1)
|
|
|
|
Линейный вид
