Slowsort - Википедия - Slowsort
Slowsort это алгоритм сортировки. Он носит юмористический характер и бесполезен. Он основан на принципе умножаться и сдаваться, насмешливая шутка разделяй и властвуй. Он был опубликован в 1986 году Андреем Бродером и Хорхе Стольфи в их статье. Пессимальные алгоритмы и анализ симплексности[1] (пародия на оптимальные алгоритмы и анализ сложности ).
Алгоритм
Slowsort - это рекурсивный алгоритм.
An на месте реализация в псевдокоде:
процедура slowsort (A, i, j) // сортирует массив A [i], ..., A [j] если я ≥ j тогда возвращаться m: = ⌊ (i + j) / 2⌋ slowsort (A, i, m) // (1.1) slowsort (A, m + 1, j) // (1.2) если A [j] тогда поменять местами A [j] и A [m] // (1.3) slowsort (A, i, j-1) // (2)
- Рекурсивно отсортировать первую половину (1.1)
- Рекурсивно отсортировать вторую половину (1.2)
- Найдите максимум всего массива, сравнив результаты 1.1 и 1.2, и поместите его в конец списка (1.3)
- Рекурсивно отсортировать весь список без максимума в 1.3 (2).
Реализация в Haskell (чисто функциональный) может выглядеть следующим образом.
медленная сортировка :: (Ord а) => [а] -> [а]медленная сортировка хз | длина хз <= 1 = хз | иначе = медленная сортировка хз ' ++ [Максимум last rlast] -- (2) куда м = длина хз `div` 2 л = медленная сортировка $ брать м хз -- (1.1) р = медленная сортировка $ уронить м хз -- (1.2) last = последний л rlast = последний р хз ' = в этом л ++ мин last rlast : в этом р
Сложность
Время выполнения для Slowsort это .Нижнее асимптотическая оценка за в Обозначения Ландау является для любого . Поэтому Slowsort не входит в полиномиальное время. Даже лучший случай хуже чем Пузырьковая сортировка.
Рекомендации
- ^ «CiteSeerX - пессимальные алгоритмы и анализ симплексности». CiteSeerX 10.1.1.116.9158. Цитировать журнал требует
| журнал =
(помощь)