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

  • Автор темы Milashka
  • Дата начала
Статус
Закрыто для дальнейших ответов.
M

Milashka

Гость
#1
Господа, ответьте пожалуйста на вопрос.
Какой метод сортировки быстрее:
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

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

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

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

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

Milashka

Гость
#4
Кодт @ www.rsdn.ru

Да, вы правы, она не стоит внимания. :)
 
Статус
Закрыто для дальнейших ответов.