정렬 알고리즘은 최적, 평균, 최악 조건에서의 시간복잡도는 물론, 메모리 사용이나 안정성 등의 범주를 기준으로 골라서 써야 한다. 비교를 기반으로 하는 정렬 알고리즘의 최악 조건의 속도는 절대 O(nlog(n))보다 빠를 수 없다.

이 포스트에서 다룰 정렬 알고리즘 목록

선택 정렬

가장 단순한 알고리즘 중 하나. In-place 알고리즘이기에 복사 연산이 매우 느린 환경에 적합하다.

매 단계마다 배열을 1번씩 스캔하며, 정렬이 되지 않은 원소 중 최솟값(최댓값)을 선택하여 맨 앞 원소와 swap한다

해당 단계가 끝나면 정렬이 되지 않은 원소의 개수를 1개 줄이고, 줄어든 배열에 대해 같은 연산을 반복한다.

In-Place. Unstable.

한 배열을 정렬이 된 배열과 안된 배열로 나누어, 단계마다 정렬이 된 배열은 크기를 늘리고 그렇지 않은 배열은 크기를 줄여가며 정렬.

정렬이 되지 않은 배열 중 가장 앞 원소를, 정렬이 된 배열의 원소와 하나씩 순차적으로 비교하여 적절한 위치에 삽입한다.

In-Place. Stable.

실린더에서 공깃방울이 떠오르듯 매 단계마다 배열을 선형탐색하여 인접한 원소와의 비교 및 swap연산을 진행.

In-place. Stable.

최대힙 혹은 최소힙을 이용하여 정렬하는 방법. 별도의 힙을 사용할 수도 있고, 주어진 배열을 Heap으로 만드는 것(In-place)도 가능하다.

힙에 원소를 삽입/삭제하는 연산은 O(logn)(힙(완전이진트리)의 높이)이고 이 연산을 원소의 개수만큼 반복하므로(2번; Heap 만들기 + Heap에서 원소 하나씩 빼기) 전체 시간복잡도는 O(nlogn)

In-place. Unstable.

피벗(Pivot)값을 기준으로 왼쪽에는 작은값, 오른쪽에는 큰값을 두고

나눠진 배열에 대해서도 퀵정렬 각각 퀵정렬을 수행(더이상 나눌 수 없을 때까지)

Pivot이 매 순간마다 최적으로 선정된다면 주어진 배열은 매번 정확히 반으로 나누어진다. 최악의 경우는 Pivot이 매번 최솟값(혹은 최댓값)으로 선정되는 것과 같다.

In-place. Unstable.

분할정복형 알고리즘의 하나. 배열을 반으로 나누고 나눠진 각 배열에 대해 다시 합병 정렬을 수행. 이후 정렬이 된 배열들을 합쳐가면서 정렬이 된 하나의 큰 배열을 얻는 방법이다.

다른 정렬 알고리즘들과 다르게 최선의 경우에도 O(n) 수준의 공간복잡도.

나눠진 배열을 정렬함에 있어서 최적화를 위해 특정 크기를 기준으로 합병정렬이 아닌 다른 정렬 알고리즘(삽입정렬 등)을 혼합하여 사용할 수도 있다(이 경우 Stable하지 않을 수 있음).

not In-place. Stable.

앞선 알고리즘들과 달리 비교 없이 수행하는 정렬 알고리즘. 기수들을 기준으로 정렬하므로, 기수들은 사전순으로 정렬할 수 있어야 한다.

버킷정렬의 일종.

not In-place. Stable

n을 정렬할 숫자의 개수, d를 최대 자리수, k를 버킷의 수(숫자의 경우 0~9이므로 10)라고 했을 때

최선 최악 평균 모두 O(d(n + k))