====== 정렬 알고리즘 ======

정렬 문제, 즉 $$n$$개의 원소가 들어 있는 [[배열]]을 잘 섞어서 순서대로 배치하는 문제를 푸는 [[알고리즘]]. [[전산학]]에서 매우 중요한 문제로 취급받기 때문에 전산학 전공했는데 이걸 모른다고 하는 사람이 있으면 그 사람이 사기꾼일 가능성을 의심해 봐야 한다.

좀 더 엄밀히 말하면, 어떤 도메인 $$A$$([[정수]]라거나 그런 것)로 이루어진 배열 $$a_1, a_2, \cdots, a_n \in A$$가 존재하고 [[완전순서]] $$\le\, \subseteq A \times A$$가 존재한다 하자. 이제 이 배열의 정렬 $$\pi$$는 이 배열의 순열, 즉 [[대칭군]] $$\mathrm{S}_n$$의 원소로 다음 조건을 만족한다:
<.center>$$a_{\pi(1)} \le a_{\pi(2)} \le ... \le a_{\pi(n)}$$</>
만약 어느 두 원소도 동일하지 않을 경우(즉, $$i \ne j \implies (a_i \le a_j \wedge a_j \le a_i)$$이면) 이 정렬은 항상 존재하며 유일하다. 이는 쉽게 논증할 수 있는데, 정렬이 존재하지 않는다면 완전 순서의 추이율이 위반되고 정렬이 유일하지 않으면 두 정렬에서 공통되지 않은 두 원소가 동일한 원소라는 걸 증명할 수 있게 된다.

그 자체로도 많이 쓰이고, 다른 알고리즘의 부분으로도 자주 쓰이다 보니 정렬 문제는 매우 잘 분석된 문제 중 하나이다. 도메인 $$A$$와 완전 순서 $$\le$$에 어떤 제약을 가하느냐에 따라 다양한 결과가 나와 있지만, 도메인과 완전 순서에 어떤 제약도 없는 기본적인 버전의 경우 최적 알고리즘이 최악의 입력에 대해 **$$\mathrm{O}(n \log n)$$**의 [[시간복잡도]]를 가진다는 것이 알려져 있다.((이 결과는 가능한 모든 대칭군의 숫자, 즉 $$\vert \mathrm{S}_n \vert = n!$$이기 때문에 $$\le$$를 $$\log_2 n!$$회, 즉 ([[스털링근사]]에 따라) $$n \log n$$회 이상 호출하지 않으면 가능한 순열을 빼먹을 수있다는 데서 유도할 수 있다.)) 실제로 이 시간복잡도를 가지거나, 최소한 평균적인 입력에 대해 최적의 시간복잡도를 보이는 알고리즘은 꽤 많이 알려져 있으며 뒤에서 서술한다.

===== 분류 =====

정렬 알고리즘을 나누는 흔한 분류는 다음과 같은 것이 있다. <del>알고리즘 수가 한 둘이 아니어야 말이지...</del>

==== 최악의 입력에 대한 비교 수의 시간복잡도 ====

가장 널리 쓰이는 <del>그리고 매우 잘 오용되는</del> 분류. 실용적인 알고리즘의 경우 크게 다음 세 가지 경우 중 하나로 나뉜다.

  * $$\mathrm{O}(n^2)$$ 알고리즘은 최적은 아니지만 보통 구현이 간단하고, 작은 입력의 경우 여러 이유로 다른 알고리즘보다 더 빠른 경우가 있어서 종종 쓰인다.
  * $$\mathrm{O}(n \log n)$$ 알고리즘은 일반적인 경우에 대해 최적의 시간복잡도라서 가장 많이 쓰인다.
  * $$\mathrm{O}(kn)$$ 알고리즘은 도메인 특성에 따라 결정되는 상수 $$k$$에 비례하는 경우로, [[기수정렬]](입력이 [[자연수]]라고 가정함) 같은 것이 대표적이다. 도메인에 대해서 더 많은 가정을 할 수 있으므로 보통 일반적인 알고리즘보다 빨라진다.

그 밖에도 [[셸정렬]]($$\mathrm{O}(n \log^2 n)$$ 변종이 알려져 있음)이나 [[스투지정렬]]($$\mathrm{O}(n^{\frac{\log 3}{\log 2}})$$) 같이 어중간한 복잡도를 가진 알고리즘이 어쩌다 있는데, 많이 쓰이지는 않는다.

엄밀히 말하면, 앞의 두 경우에 대응되는 복잡도와 맨 마지막 경우에 대응되는 복잡도는 서로 다른 복잡도이다. 전자는 "완전 순서 $$\le$$를 호출하는 횟수"를 계산하는 것이고(그래서 이를 "비교정렬"이라 부른다) 후자는 일반적인 연산 횟수를 계산하는 것이다. 그러나 연산 횟수가 비교 횟수에 비례하는 경우가 태반이므로 대부분의 경우 크게 구분해서 쓰지는 않는다.

==== 평균적인 입력에 대한 비교 수의 시간복잡도 ====

최악의 입력이 매우 드물게 나타나는 경우에 사용하는 분류. 여기서 말하는 "평균적인 입력"이란 원소 두 개를 무작위로 골랐을 때 그 순서가 반대일 확률이 대략 50%인 경우를 말한다.

이 분류가 절실하게 필요한 대표적인 알고리즘이 [[퀵정렬]]로, 웬만한 노력을 기울이지 않으면 최악의 경우 시간복잡도가 $$\mathrm{O}(n^2)$$인 입력을 무조건 만들어 내는 게 가능하다.(([[http://research.swtch.com/qsort|Killing Quicksort]]. 여러 회피 방법이 있지만 이 회피 방법들을 적용하느니 문제가 없는 다른 알고리즘을 쓰는 게 더 나은 수준이다. 자세한 것은 해당 문서 참조.)) 이런 종류의 알고리즘은 [[알고리즘복잡도공격]](algorithmic complexity attack)에 취약할 수 있으므로 각별한 주의가 필요하다.

==== 대부분 정렬된 입력에 대한 비교 수의 시간복잡도 ====

"평균적인" 입력과는 별개로, 실제로 들어오는 입력은 이미 거의 정렬되어 있거나 부분적으로라도 순서가 보존되어 있는 경우가 많다. 때문에 실용적으로는 이런 종류의 입력에 대해서 더 빠르게 동작하는 것이 유리하다.

이 기준으로 유리한 알고리즘은 의외로(...) [[삽입정렬]]과 [[병합정렬]]로, 전자는 시간복잡도가 뒤집한 원소쌍(inversion)의 수에 비례하기 때문에 가능하고, 후자는 애초에 이미 정렬된 배열 두 개를 반복적으로 합치는 식으로 동작하므로 가능하다. 병합정렬은 최악의 경우에도 최적의 시간복잡도를 보여 주기 때문에 개선의 여지가 매우 많은데, 이를 적극적으로 활용한 알고리즘이 바로 [[팀정렬]]이다.

==== 복사 수의 시간복잡도 ====

전통적인 정렬 알고리즘은 비교 숫자를 최적화하는데 집중한다. 하지만 비교가 충분히 싸다면 비교 숫자보다 복사 숫자, 즉 메모리 상에서 원소가 옮겨다니는 시간이 더 중요할 수 있다. 이 때문에 비교 수와는 별개로 복사 수를 세는 경우도 있다.

대부분의 기준에서 매우 최적에 속하는 [[병합정렬]]이 드물게 최적이 아닌 분류로, 병합정렬은 제자리 정렬을 하면 성능이 나빠지기 때문에 원소를 복사하는 숫자로 따지면 불리할 수 밖에 없다. 반면 [[퀵정렬]]에서 pivot을 구하는데 쓰는 보편적인 알고리즘은 복사 수를 줄이는 데 최적화되어 있다. 그래서 [[JDK]]의 경우 ''Comparable'' 인터페이스가 구현되어 있는, 즉 비교가 느릴 가능성이 큰 경우에만 병합정렬의 일종인 [[팀정렬]]을 사용하고, 숫자 같이 비교가 값싼 경우에는 퀵정렬의 변종을 사용한다.

==== 공간복잡도 ====

원소 자체를 저장하는 메모리 말고 추가적으로 필요한 임시 메모리에 대한 복잡도. 따라서 공간복잡도가 $$\mathrm{O}(1)$$이라는 얘기는 원소가 저장된 배열 안에서 두 원소를 교환하는 걸 반복해 가면서 정렬을 수행하는, 즉 "제자리"(in-place) 정렬이라는 뜻이 된다. 메모리가 넘쳐나는 요즘 들어서는 그렇게 부각되진 않는 특징이기도 하다.

==== 순서 안정성 ====

여기서 말하는 안정성이란, 원소 $$a_i$$와 $$a_j$$가 있고 $$i < j$$일 때, $$a_i \le a_j$$이고 $$a_j \le a_i$$였다면 정렬 후에도 둘이 뒤집혀서는 안 된다($$\pi(i) < \pi(j)$$)는 뜻이다. 즉 같은 원소 사이의 상대적인 순서를 보존한다는 뜻. 특히 만약 모든 원소가 ($$\le$$에 대해) 같은 원소로 처리될 경우 입력과 출력은 완전히 동일해야 한다.

안정적이지 않은 정렬의 대표적인 예로 [[퀵정렬]]이 있고, 안정적인 정렬로는 [[병합정렬]](의 일부 버전)이 있다. 전통적으로 순서 안전성을 포기하면 빨라진다는 생각이 있어서 둘을 구분해 놓았던 것이지만, 어찌 된 것이 최근 들어서는 안정적인 정렬이 실용적인 입력에서 빨라지는 기현상이 나타나고 있어서 현재는 그렇게 의미가 없는 분류가 되어 가고 있다.

안정적이지 않은 정렬을 안정적인 정렬로 만드는 것 자체는 (좀 부하가 걸릴 뿐) 자명하다. [[decorate-sort-undecorate]] 참고.

===== 목록 =====

  * $$\mathrm{O}(n^2)$$ 시간복잡도: [[삽입정렬]] -- [[거품정렬]] -- [[선택정렬]]
  * $$\mathrm{O}(n \log n)$$ 시간복잡도: [[퀵정렬]] ([[삼항퀵정렬]]) -- [[병합정렬]] ([[팀정렬]]) -- [[힙정렬]]
  * $$\mathrm{O}(kn)$$ 시간복잡도: [[기수정렬]]

{{tag>알고리즘 목록}}