Медленная сортировка (англ. Slowsort) — непрактичный и юмористический алгоритм сортировки. Он основан на принципе размножай и сдавайся (англ. multiply and surrender), пародии на разделяй и властвуй. Его опубликовали Андрей Бродер и Йорге Столфи в 1986 году в своей статье Pessimal Algorithms and Simplexity Analysis (Пессимальные алгоритмы и анализ простоты, пародия на оптимальные алгоритмы и анализ сложности).
Алгоритм Медленная сортировка — рекурсивный алгоритм.
Он может быть описан следующим образом: 1.1. Рекурсивно отсортировать первую половину. 1.2. Рекурсивно отсортировать вторую половину. 1.3. Найти максимум всего массива, сравнивая результаты 1.1 и 1.2, и поместить его в конец массива. 2. Рекурсивно отсортировать весь массив, кроме максимума.
На псевдокоде он реализуется следующим образом: подпрограмма slowsort(A, i, j) // сортирует массив A[i], ..., A[j] если (i >= j) то вернуться m := floor((i+j)/2) slowsort(A, i, m) // (1.1) slowsort(A, m+1, j) // (1.2) если (A[j] < A[m]) то поменять A[j] и A[m] // (1.3) slowsort(A, i, j-1) // (2)
Возможная реализация на Haskell: slowsort :: Ord a => [a] -> [a] slowsort xs | length xs <= 1 = xs | otherwise = slowsort xsnew ++ [max llast rlast] -- (2) where l = slowsort $ take m xs -- (1.1) r = slowsort $ drop m xs -- (1.2) llast = last l rlast = last r xsnew = init l ++ min llast rlast : init r m = fst (divMod (length xs) 2)
Сложность Время выполнения медленной сортировки равно . Медленная сортировка не в полиномиальном времени. Даже в лучшем случае она хуже сортировки пузырьком.
Примечания
Категория:Алгоритмы_сортировки Категория:Компьютерный_юмор