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)

Реализация в Haskell (чисто функциональный) может выглядеть следующим образом.

медленная сортировка :: (Ord а) => [а] -> [а]медленная сортировка хз  | длина хз <= 1 = хз  | иначе      = медленная сортировка хз ' ++ [Максимум last rlast]  -- (2)  куда м     = длина хз `div` 2        л     = медленная сортировка $ брать м хз  -- (1.1)        р     = медленная сортировка $ уронить м хз  -- (1.2)        last = последний л        rlast = последний р        хз '   = в этом л ++ мин last rlast : в этом р

Сложность

Время выполнения для Slowsort это .Нижнее асимптотическая оценка за в Обозначения Ландау является для любого . Поэтому Slowsort не входит в полиномиальное время. Даже лучший случай хуже чем Пузырьковая сортировка.

Рекомендации

  1. ^ «CiteSeerX - пессимальные алгоритмы и анализ симплексности». CiteSeerX  10.1.1.116.9158. Цитировать журнал требует | журнал = (помощь)