Вопрос по сортировке

[Milashka]

Господа, ответьте пожалуйста на вопрос.
Какой метод сортировки быстрее:
1)

for i=1 to n-1
for j=i+1 to n
if a(i)<a(j) then
s=a(i)
a(i)=a(j)
a(j)=s
end if
next j
next i


2)

for i=1 to n-1
max= a(i)
k=i
for j=i+1 to n
if max<a(j) then
max= a(j)
k = j
end if
next j
a(k)=a(i)
a(i) = max
next i

И почему?

 

[admin]

Milashka
Немного подкорректировав и написав на Delphi эти алгоритмы практически одинаковы. Первый обогнал на 3ms при сортировке 1 млн элементов. Тестировал на Athlon 1600XP+.

 

[Guest]

В обоих случаях имеем дело с вариациями пузырьковой сортировки.
Асимптотика и там, и там - O(N*N).
Если говорить точнее, то выполняется N*(N-1)/2 сравнений и не более N*(N-1)/2 обменов.

При желании, конечно, можно тщательно изучить, насколько эти алгоритмы совпадают/различаются (с точностью до порядка выполнения операций) - в предположении, что и сравнение, и обмен имеют побочные эффекты (например, запись в журнал).

Однако сама по себе пузырьковая сортировка не стоит того внимания.

 

[Milashka]

Кодт @ www.rsdn.ru

Да, вы правы, она не стоит внимания.