• 🔥 Бесплатный курс от Академии Кодебай: «Анализ защищенности веб-приложений»

    🛡 Научитесь находить и использовать уязвимости веб-приложений.
    🧠 Изучите SQLi, XSS, CSRF, IDOR и другие типовые атаки на практике.
    🧪 Погрузитесь в реальные лаборатории и взломайте свой первый сайт!
    🚀 Подходит новичкам — никаких сложных предварительных знаний не требуется.

    Доступ открыт прямо сейчас Записаться бесплатно

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

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

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

И почему?
 
Milashka
Немного подкорректировав и написав на Delphi эти алгоритмы практически одинаковы. Первый обогнал на 3ms при сортировке 1 млн элементов. Тестировал на Athlon 1600XP+.
 
В обоих случаях имеем дело с вариациями пузырьковой сортировки.
Асимптотика и там, и там - O(N*N).
Если говорить точнее, то выполняется N*(N-1)/2 сравнений и не более N*(N-1)/2 обменов.

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

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

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

Взломай свой первый сервер и прокачай скилл — Начни игру на HackerLab