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

Тема в разделе "Другие", создана пользователем Milashka, 18 фев 2004.

Статус темы:
Закрыта.
  1. Milashka

    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

    И почему?
     
  2. admin

    admin Well-Known Member

    Регистрация:
    8 авг 2003
    Сообщения:
    2.811
    Симпатии:
    0
    Milashka
    Немного подкорректировав и написав на Delphi эти алгоритмы практически одинаковы. Первый обогнал на 3ms при сортировке 1 млн элементов. Тестировал на Athlon 1600XP+.
     
  3. Гость

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

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

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

    Milashka Гость

    Кодт @ www.rsdn.ru

    Да, вы правы, она не стоит внимания. :)
     
Загрузка...
Похожие Темы - Вопрос по сортировке
  1. ApplePen
    Ответов:
    0
    Просмотров:
    60
  2. gURaBA_N
    Ответов:
    3
    Просмотров:
    92
  3. kartaman
    Ответов:
    0
    Просмотров:
    127
  4. Peter
    Ответов:
    4
    Просмотров:
    522
  5. di0d_
    Ответов:
    1
    Просмотров:
    437
Статус темы:
Закрыта.

Поделиться этой страницей