над медленнее, всякие дебилы вроде меня не успевают(
17.11.2014, 11:17
даунгрейд?
Охренеть, есть тип задач для которых пузырек оптимален)
Охреневай дальше, кроме чисто абстрактных академических задач сортировки, есть ещё реализация на конкретном физическом железе. И для малых объемов данных внезапно оказывается, что большинство хорошо написанных чисто квадратичных Шелов и Пузырьков будут работать лучше хип и квик сортов. Константа при асимптотике лучше, разница между n и log(n) для маленьких n мала, а накладных расходы, плохо предсказуемые переходы у сложного кода..... забивают гвоздь в крышку гроба.
Не говоря уже о том, что часто важно ещё такое (упущенное здесь) свойство как стабильность: относительный порядок одинаковых ключей не меняется. Немудренные Q и все Heap сортировки нестабильны, а пузырек стабилен.
Не говоря уже о том, что часто важно ещё такое (упущенное здесь) свойство как стабильность: относительный порядок одинаковых ключей не меняется. Немудренные Q и все Heap сортировки нестабильны, а пузырек стабилен.
cool story
Стабильная сортировка позволяет сохранять позиции элементов с одинаковым значением. Например:
3(A) 1(A) 1(B) 2(A) 1(C)
Последовательность из 5 чисел. За каждым закреплена буква. Так вот некоторые сортировки могут вернуть такой результат:
1(B) 1(C) 1(A) 2(A) 3(A)
Видно, что позиции единиц относительно друг друга изменились.
Стабильная сортировка гарантирует, что их позиции сохранятся:
1(A) 1(B) 1(C) 2(A) 3(A)
Полезно для сортировки структур
3(A) 1(A) 1(B) 2(A) 1(C)
Последовательность из 5 чисел. За каждым закреплена буква. Так вот некоторые сортировки могут вернуть такой результат:
1(B) 1(C) 1(A) 2(A) 3(A)
Видно, что позиции единиц относительно друг друга изменились.
Стабильная сортировка гарантирует, что их позиции сохранятся:
1(A) 1(B) 1(C) 2(A) 3(A)
Полезно для сортировки структур
я кончил и закурил
Чувак, не забывай, что у пузырька фиксированное число операций, если не ведется какая-то проверка на упорядоченность всего массива, поэтому даже если на каком то этапе массив окажется отсортирован, то пузырек все равно продолжит заканчивать свои O(n*n) действий. Так что табличка не совсем корректна. Ну а если добавить проверку на отсортированность, то уже добавляются вероятностные условия, при которых пузырек будет быстрее, а это мало чем отличается от той же быстрой сортировки, потому как она вытягивает именно за счет теорвера.
Ты не поверишь. Любая практическая реализация пузырька (зайди хоть в английскую вики) будет содержать флаг "был ли сделан хоть один своп на этой итерации". И это тривиальное изменение мгновенно добавляет алгоритму свойство: работать за O(n) в лучшем случае, что крайне важно на практике.
И нет, на практике QSort вытягивает не за счет тервера (чтобы это не означало), хотя безусловно оптимизации делающие практически невероятной работу за квадрат важны, а за счет того, что он cache friendly (свойство первостепенной важности, когда мы говорим о практических реализациях алгоритмов, а не водим мелом по доске). Его (QSort) время работы в лучшем случае есть O(n log n), в общем O(n^2), он требует дополнительной памяти (в стеке), что почти по всем статьям хуже (и не лучше по остальным) с точки зрения теории чем у heapsort. Тогда как на практике heapsort почти всегда хуже.
И нет, на практике QSort вытягивает не за счет тервера (чтобы это не означало), хотя безусловно оптимизации делающие практически невероятной работу за квадрат важны, а за счет того, что он cache friendly (свойство первостепенной важности, когда мы говорим о практических реализациях алгоритмов, а не водим мелом по доске). Его (QSort) время работы в лучшем случае есть O(n log n), в общем O(n^2), он требует дополнительной памяти (в стеке), что почти по всем статьям хуже (и не лучше по остальным) с точки зрения теории чем у heapsort. Тогда как на практике heapsort почти всегда хуже.
В том то и дело, что я именно вожу мелом по доске :D На практике можно к многим ухищрениям прибегать. Вводить флаги, параллелить процессы, подгонять аппаратную часть. Просто можно ли это учитывать в "честном" подсчете O? Вот табличка то как раз и не отражает полностью всего этого спектра. По поводу быстрой и тервера: ты сам написал что в лучшем случае O(n log n), в общем O(n^2), т.е. расчет на то, что в большинстве случаев будет "лучший" случай :D Ну а в практической части я с тобой согласен, конечно.
Что значит можно или нельзя учитывать в честном подсчете асимптотики? Если они её меняют - да, если не меняют - нет. Для сортировки пузырьком это стандартная её доработка, она меняет для неё время работы в лучшем случае, таблица её учитывает (отчетливо видно в nearly sorted).
Перефразируя, я хотел сказать, что есть сортировка теоретически безоговорочно лучше QSort (и даже не одна), но на практике лучше работает очень мало что. Потому что мы программируем не машины Тьюринга, современный процессор простаивает больше половины времени ожидая данных. Если же мы займемся сухой теорией, можно настроить таких веселых непрактичных алгоритмов. Знаешь ли ты например: что массив int'ов radix sort сортирует за линейное время в худшем случае? Это правда, только отчего-то никто так не делает.
А вообще вот хорошая статья, с хорошей таблицей: http://habrahabr.ru/company/infopulse/blog/133303/
Перефразируя, я хотел сказать, что есть сортировка теоретически безоговорочно лучше QSort (и даже не одна), но на практике лучше работает очень мало что. Потому что мы программируем не машины Тьюринга, современный процессор простаивает больше половины времени ожидая данных. Если же мы займемся сухой теорией, можно настроить таких веселых непрактичных алгоритмов. Знаешь ли ты например: что массив int'ов radix sort сортирует за линейное время в худшем случае? Это правда, только отчего-то никто так не делает.
А вообще вот хорошая статья, с хорошей таблицей: http://habrahabr.ru/company/infopulse/blog/133303/
В продакшене, никто не использует классический qsort без доработок. И ты или, делаешь нерекурсивную реализацию (стэк тебе всё равно понадобится) или твои другие оптимизации ограничат глубину.
Вообще рекурсия прекрасная вещь пока ты можешь оценить её глубину и она тебя устраивает (для классического qsort глубина в худшем случае n - 1 =) и это конечно никого не может устроить). Если мы не говорим про случаи когда мы пишем для ring0, для микроконтроллеров или ещё чего-то где ресурсы сильно ограничены, стэка у тебя больше чем достаточно.
Вообще рекурсия прекрасная вещь пока ты можешь оценить её глубину и она тебя устраивает (для классического qsort глубина в худшем случае n - 1 =) и это конечно никого не может устроить). Если мы не говорим про случаи когда мы пишем для ring0, для микроконтроллеров или ещё чего-то где ресурсы сильно ограничены, стэка у тебя больше чем достаточно.
Ну и там же есть остальные алгоритмы
это круто!
Какой-то совсем уж неэффективный алгоритм. Целых семь минут сортировал числа от 0 до 9. Кажется пляски отрицательно влияют на скорость сортировки
Схоронил!!!
Но нужна крайне медленная версия, чтобы вдуматься...
Но нужна крайне медленная версия, чтобы вдуматься...
офигеть! схоронил
как будто опять в Earthbound поиграл
че за bogo sort? такое ощущение, что он переставляет элементы в случайном порядке и проверяет, не отсортировалось ли
Во многих случаях достаточно селект-сорта, эффективность N*N/2
Инсерт-сорт представлен некорректно, поиск места куда вставить должен идти не с начала, а с последнего вставленного элемента, так оптимальнее. В этом случае количество операций варьируется от N в лучшем случае до N*N/2 в худшем.
Инсерт-сорт представлен некорректно, поиск места куда вставить должен идти не с начала, а с последнего вставленного элемента, так оптимальнее. В этом случае количество операций варьируется от N в лучшем случае до N*N/2 в худшем.
Еххх, а полезная вещица.
Похоже кто-то из щенков уже на первом курсе!
что ты натворил
Over Quota
This application is temporarily over its serving quota. Please try again later.
Over Quota
This application is temporarily over its serving quota. Please try again later.
третий
Так кто топ в номинациях.
http://sorting.at/
Чтобы написать коммент, необходимо залогиниться
