📂알고리즘

스탈린 정렬

알고리즘 ¹

길이가 $n$ 인 배열이 주어져있다고 하자. 배열을 처음부터 뒤로 읽어가면서 뒤쪽이 앞쪽보다 크면 제거하는 것을 반복하면 ‘순서대로는’ 정렬된 배열을 얻는다. 그 시간복잡도는 $O(n)$ 이고, 수도코드는 다음과 같다.

FUNCTION stalinSort(A : list OF sortable items)
    n := length(A)
    bigger := 0
    B SET empty list

    FOR i := 0 TO n NOT inclusive DO
        IF A[i] >= bigger THEN
          bigger := A[i]
          B.push(A[i])
        END IF
    END FOR

    RETURN B
END FUNCTION

설명

스탈린 정렬은 소련의 독재자 이오시프 스탈린^{Ио́сиф Ста́лин}의 이름을 딴 알고리즘으로써, 사실 정렬 알고리즘이라기보다는 조크에 가깝다. 일단 정렬을 하는 방식이라는 게 스탈린이 그러했듯 마음에 들지 않는 원소를 굴라크^gulag로 보내는 점, 그러니까 숙청을 하기 때문에 원래 배열의 원소가 그대로 유지되지 않는다.

그러나 코딩을 하다보면 의외로 이런 알고리즘이라도 필요하거나, 이런 알고리즘으로 충분한 때가 없다고 장담할 수는 없다. 다행스럽게도 네이밍 센스가 기가 막히고 구현도 아주 단순하기 때문에 굳이 기억하려고 노력하지 않아도 된다.