느린 정렬 문서 원본 보기

{{위키데이터 속성 추적}}
'''느린 정렬''' 또는 '''슬로소트'''(slowsort)는 [[정렬 알고리즘]]의 하나이다. 유머에서 기인한 정렬이며 유용성이 없다. 증식 항복(multiply and surrender)의 원리에 기반한, 사용이 꺼려지는 알고리즘이다. ([[분할 정복 알고리즘]]의 [[반의어]]를 취한 패러디) 1986년에 안드레이 브로더(Andrei Broder)와 조지 스톨피(Jorge Stolfi)가 출판한 논문 "최악 알고리즘과 단순성 분석"(Pessimal Algorithms and Simplexity Analysis)에서 소개되었다.<ref>{{저널 인용|title=Pessimal Algorithms and Simplexity Analysis |date=1984 |author1=Andrei Broder |author2=Jorge Stolfi |journal=ACM SIGACT News |volume=16 |issue=3 |pages=49–53 |url=http://www.mipmip.org/tidbits/pasa.pdf |doi=10.1145/990534.990536 |citeseerx=10.1.1.116.9158|s2cid=6566140 }}</ref> (이 논문의 제목은 [[최적 알고리즘]](Optimal Algorithm)과 [[계산 복잡도 이론|복잡도 분석]](Complexity Analysis)을 패러디했다.)

== 알고리즘 ==
느린 정렬은 [[재귀 (컴퓨터 과학)|재귀 알고리즘]]이다.
* [[제자리 알고리즘|제자리]] 정렬을 한다.
* [[정렬 알고리즘|안정 정렬]]이다. (동일한 값의 키의 순서를 바꾸지 않는다)

의사 코드의 구현체는 다음과 같다.
<syntaxhighlight lang="pascal">
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)
</syntaxhighlight>

* 처음의 절반을 재귀 정렬한다. (1.1)
* 나머지 절반을 재귀 정렬한다. (1.2)
* 1.1과 1.2의 결과를 비교함으로써 전체 배열의 최대치를 찾고 이를 목록의 끝에 넣는다. (1.3)
* 모든 목록(맨 끝의 최대값 제외)을 각각 정렬한다. (2)

[[하스켈]]의 최적화되지 않은 구현체(순수 함수)는 다음과 같다:
<syntaxhighlight lang="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
</syntaxhighlight>

== 복잡도 ==
느린 정렬의 실행 시간 <math>T(n)</math>은 <math>T(n) = T ( \left \lfloor n/2 \right \rfloor ) + T ( \left \lceil n/2 \right \rceil ) + T(n-1) + 1</math>로, {{OEIS|A178855}}와 같다.

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


== 각주 ==
{{각주}}

{{정렬 알고리즘}}

[[분류:컴퓨터 유머]]
[[분류:정렬 알고리즘]]