Искусственная жизнь. Борьба кланов.,Science & Technology,искусственная жизнь,artificial life,evolution,эволюция,моделирование эволюции,Новый вариант "искусственной жизни" для моделирования Эволюции.
Придуманный мир с придуманными правилами, в котором живут клетки, имеющие геном и способные порождат
Не говоря уже о том, что часто важно ещё такое (упущенное здесь) свойство как стабильность: относительный порядок одинаковых ключей не меняется. Немудренные Q и все Heap сортировки нестабильны, а пузырек стабилен.
А было желание понять?
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)
Полезно для сортировки структур
* с точки зрения критерия сортировки.
И нет, на практике QSort вытягивает не за счет тервера (чтобы это не означало), хотя безусловно оптимизации делающие практически невероятной работу за квадрат важны, а за счет того, что он cache friendly (свойство первостепенной важности, когда мы говорим о практических реализациях алгоритмов, а не водим мелом по доске). Его (QSort) время работы в лучшем случае есть O(n log n), в общем O(n^2), он требует дополнительной памяти (в стеке), что почти по всем статьям хуже (и не лучше по остальным) с точки зрения теории чем у heapsort. Тогда как на практике heapsort почти всегда хуже.
Перефразируя, я хотел сказать, что есть сортировка теоретически безоговорочно лучше QSort (и даже не одна), но на практике лучше работает очень мало что. Потому что мы программируем не машины Тьюринга, современный процессор простаивает больше половины времени ожидая данных. Если же мы займемся сухой теорией, можно настроить таких веселых непрактичных алгоритмов. Знаешь ли ты например: что массив int'ов radix sort сортирует за линейное время в худшем случае? Это правда, только отчего-то никто так не делает.
А вообще вот хорошая статья, с хорошей таблицей: http://habrahabr.ru/company/infopulse/blog/133303/
Вообще рекурсия прекрасная вещь пока ты можешь оценить её глубину и она тебя устраивает (для классического qsort глубина в худшем случае n - 1 =) и это конечно никого не может устроить). Если мы не говорим про случаи когда мы пишем для ring0, для микроконтроллеров или ещё чего-то где ресурсы сильно ограничены, стэка у тебя больше чем достаточно.
Но нужна крайне медленная версия, чтобы вдуматься...
"является очень неэффективным алгоритмом сортировки. Её используют только в образовательных целях"
Инсерт-сорт представлен некорректно, поиск места куда вставить должен идти не с начала, а с последнего вставленного элемента, так оптимальнее. В этом случае количество операций варьируется от N в лучшем случае до N*N/2 в худшем.
http://www.sorting-algorithms.com/
Over Quota
This application is temporarily over its serving quota. Please try again later.