1. Набираем команду codeby webinar. Набираем команду для организации и проведения вебинаров. Подробнее ...

    Скрыть объявление
  2. Требуются разработчики и тестеры для проекта codebyOS. Требования для участия в проекте: Знание принципов работы ОС на базе Linux; Знание Bash; Крайне желательное знание CPP, Python, Lua; Навыки системного администрирования. Подробнее ...

    Скрыть объявление
  3. Получи 30.000 рублей. Для получения денег необходимо принять участие в конкурсе авторов codeby. С условиями и призами можно ознакомиться на этой странице ...

    Внимание! Регистрация авторов на конкурс закрыта.

    Скрыть объявление

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

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

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

    Milashka Гость

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

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

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

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

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

    Milashka Гость

    Репутация:
    0
    Кодт @ www.rsdn.ru

    Да, вы правы, она не стоит внимания. :)
     
Загрузка...
Статус темы:
Закрыта.

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