느린 정렬

느린 정렬 또는 슬로소트(slowsort)는 정렬 알고리즘의 하나이다. 유머에서 기인한 정렬이며 유용성이 없다. 증식 항복(multiply and surrender)의 원리에 기반한, 사용이 꺼려지는 알고리즘이다. (분할 정복 알고리즘의 반의어를 취한 패러디) 1986년에 안드레이 브로더(Andrei Broder)와 조지 스톨피(Jorge Stolfi)가 출판한 논문 "최악 알고리즘과 단순성 분석"(Pessimal Algorithms and Simplexity Analysis)에서 소개되었다.^[1] (이 논문의 제목은 최적 알고리즘(Optimal Algorithm)과 복잡도 분석(Complexity Analysis)을 패러디했다.)

알고리즘

느린 정렬은 재귀 알고리즘이다.

• 제자리 정렬을 한다.
• 안정 정렬이다. (동일한 값의 키의 순서를 바꾸지 않는다)

의사 코드의 구현체는 다음과 같다.

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)

하스켈의 최적화되지 않은 구현체(순수 함수)는 다음과 같다:

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

복잡도

느린 정렬의 실행 시간 ${\displaystyle T(n)}$은 ${\displaystyle T(n)=T(\left\lfloor n/2\right\rfloor )+T(\left\lceil n/2\right\rceil )+T(n-1)+1}$로, (OEIS의 수열 A178855)와 같다.

최상의 조건을 갖추었다고 해도 거품 정렬보다도 속도가 더 느리다.

각주

1. Andrei Broder; Jorge Stolfi (1984). “Pessimal Algorithms and Simplexity Analysis” (PDF). 《ACM SIGACT News》 16 (3): 49–53. CiteSeerX 10.1.1.116.9158. doi:10.1145/990534.990536. S2CID 6566140.