Slowsort - Slowsort
Slowsort - это алгоритм сортировки . Он носит юмористический характер и бесполезен. Это неохотный алгоритм, основанный на принципе умножения и подчинения ( пародия, созданная путем взятия противоположностей « разделяй и властвуй» ). Он был опубликован в 1986 году Андреем Бродером и Хорхе Столфи в их статье « Пессимальные алгоритмы и анализ симплексности» (пародия на оптимальные алгоритмы и анализ сложности ).
Алгоритм
Slowsort - это рекурсивный алгоритм .
- Сортировка на месте .
- Это стабильный сорт . (Это не меняет порядок ключей с одинаковыми значениями.)
Это реализация в псевдокоде:
procedure slowsort(A[], i, j) // Sort array range A[i ... j] in-place.
if i ≥ j then
return
m := floor( (i+j)/2 )
slowsort(A, i, m) // (1.1)
slowsort(A, m+1, j) // (1.2)
if A[j] < A[m] then
swap A[j] , A[m] // (1.3)
slowsort(A, i, j-1) // (2)
- Рекурсивно отсортируйте первую половину. (1.1)
- Рекурсивно отсортируйте вторую половину. (1.2)
- Найдите максимум всего массива, сравнив результаты 1.1 и 1.2, и поместите его в конец списка. (1.3)
- Рекурсивно отсортировать весь список (кроме максимума в конце). (2)
Неоптимизированная реализация в Haskell (чисто функциональная) может выглядеть следующим образом:
slowsort :: (Ord a) => [a] -> [a]
slowsort xs
| length xs <= 1 = xs
| otherwise = slowsort xs' ++ [max llast rlast] -- (2)
where m = length xs `div` 2
l = slowsort $ take m xs -- (1.1)
r = slowsort $ drop m xs -- (1.2)
llast = last l
rlast = last r
xs' = init l ++ min llast rlast : init r
Сложность
Среда выполнения для Slowsort - это .
Более низкая асимптотическим связаны для в Ландау обозначениях это для любого .
Следовательно, Slowsort не выполняется за полиномиальное время . Даже лучший случай хуже, чем пузырьковая сортировка .