медленная сортировка

О другом алгоритме сортировки, также известном как «медленная сортировка», см. Bogosort .

Slowsort — это алгоритм сортировки . Оно носит юмористический характер и бесполезно. Это неохотный алгоритм , основанный на принципе « умножай и сдавайся» ( пародия , образованная путем использования противоположностей « разделяй и властвуй» ). Он был опубликован в 1984 году Андреем Бродером и Хорхе Столфи в их статье «Пессимальные алгоритмы и анализ симплексности». (пародия на оптимальные алгоритмы и анализ сложности ).

Алгоритм

Медленная сортировка — это рекурсивный алгоритм .

• Он сортируется на месте .
• Это стабильный сорт . (Оно не меняет порядок ключей с одинаковыми значениями.)

Это реализация в псевдокоде:

procedure slowsort(A[], start_idx, end_idx)        // Sort array range A[start ... end] in-place.
    if start_idx ≥ end_idx then
        return

    middle_idx := floor( (start_idx + end_idx)/2 )
    slowsort(A, start_idx, middle_idx)             // (1.1)
    slowsort(A, middle_idx + 1, end_idx)           // (1.2)
    if A[end_idx] < A[middle_idx] then
        swap (A, end_idx, middle_idx)          // (1.3)

    slowsort(A, start_idx, end_idx - 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

Сложность

Время выполнения $T(n)$ для медленной сортировки $T(n)=2T(n/2)+T(n-1)+1$.

Нижняя асимптотическая оценка для $T(n)$ в Ландау обозначениях $\Omega \left(n^{\log _{2}(n)/(2+\epsilon )}\right)$ для любого $\epsilon >0$.

Поэтому медленная сортировка не выполняется за полиномиальное время . Даже лучший случай хуже, чем сортировка пузырьком .