Медленная неправильная переменная
- 1 year ago
- 0
- 0
Медленная сортировка ( англ. Slowsort ) — непрактичный и юмористический алгоритм сортировки . Он основан на принципе размножай и сдавайся ( англ. multiply and surrender ), пародии на разделяй и властвуй . Его опубликовали Андрей Бродер и Йорге Столфи в 1986 году в своей статье Pessimal Algorithms and Simplexity Analysis ( Пессимальные алгоритмы и анализ простоты , пародия на оптимальные алгоритмы и анализ сложности ).
Медленная сортировка — рекурсивный алгоритм .
Он может быть описан следующим образом:
На псевдокоде он реализуется следующим образом:
подпрограмма 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)
Время выполнения медленной сортировки равно . Медленная сортировка не в полиномиальном времени . Даже в лучшем случае она хуже сортировки пузырьком .