기본 정렬: 삽입·선택·버블·셸
삽입·선택·버블·셸 정렬의 처리 과정과 안정성, 시간 복잡도를 비교한다.
정렬 알고리즘을 비교하는 기준
정렬(Sort)은 원소를 키의 순서에 맞게 재배치하되, 정렬 전후에 원소의 종류와 개수가 같아야 하는 연산이다. 이하의 예시는 배열을 오름차순으로 정렬하는 표준 구현을 기준으로 한다.
정렬 문제에서는 실행 결과만 보지 말고 다음 성질을 함께 구분해야 한다.
- 안정 정렬(Stable Sort): 키가 같은 원소들의 입력 순서를 정렬 후에도 보존한다.
- 제자리 정렬(In-place Sort): 입력 배열 이외에 원소 수에 비례하는 추가 저장 공간을 사용하지 않는다. 일반적으로 O(1)의 보조 공간만 사용한다.
- 적응성(Adaptiveness): 입력이 이미 정렬되어 있거나 거의 정렬되어 있을 때 작업량이 줄어드는 성질이다.
- 회전(Pass): 미정렬 구간을 한 번 처리하는 단위다. 알고리즘과 진행 방향에 따라 한 회전 뒤 확정되는 영역이 다르다.
같은 빅오 표기가 붙어 있어도 비교 위치, 이동 횟수, 안정성, 입력 상태의 영향은 서로 다르다.
네 정렬의 핵심 차이
| 알고리즘 | 한 회전의 핵심 동작 | 한 회전 뒤 보장되는 상태 |
|---|---|---|
| 삽입 정렬 | 현재 key를 앞쪽 정렬 구간의 알맞은 위치에 삽입 | 처리한 앞쪽 구간이 정렬됨. 각 원소의 전체 최종 위치까지 보장되지는 않음 |
| 선택 정렬 | 미정렬 구간의 최솟값을 찾아 첫 위치와 교환 | 앞쪽에 전체 최솟값부터 하나씩 최종 확정 |
| 버블 정렬 | 왼쪽에서 오른쪽으로 인접한 역순 쌍을 교환 | 미정렬 구간의 최댓값이 오른쪽 끝에 최종 확정 |
| 셸 정렬 | 간격 g만큼 떨어진 원소들로 부분 수열을 만들고 삽입 정렬 | 배열이 g-정렬됨. g = 1 단계가 끝나야 전체 정렬 완료 |
표준 배열 구현의 성질
| 알고리즘 | 시간 복잡도 | 안정성 | 보조 공간 | 기억할 조건 |
|---|---|---|---|---|
| 삽입 정렬 | 최선 Θ(n), 평균·최악 Θ(n²) | 안정적 | O(1) | key보다 큰 원소만 오른쪽으로 이동할 때 |
| 선택 정렬 | 최선·평균·최악 Θ(n²) | 일반적으로 불안정 | O(1) | 비교 횟수는 입력 상태와 무관, 교환은 최대 n - 1회 |
| 버블 정렬 | 조기 종료 시 최선 Θ(n), 평균·최악 Θ(n²) | 안정적 | O(1) | 같은 값은 교환하지 않고, 한 회전에서 교환이 없으면 종료 |
| 셸 정렬 | 간격 수열에 따라 달라짐 | 일반적으로 불안정 | O(1) | 간격을 줄여 마지막에 반드시 1을 사용 |
삽입 정렬의 최선 Θ(n)은 표준 삽입 과정에서 자연스럽게 나타나며, 버블 정렬의 최선 Θ(n)은 교환 여부를 검사해 조기 종료하는 구현을 전제로 한다. 버블 정렬이 교환 여부를 확인하지 않고 정해진 회전을 모두 수행하면, 이미 정렬된 입력에서도 Θ(n²) 비교를 할 수 있다.
삽입 정렬
파란 구간은 지금까지 정렬한 앞부분이다. 다음 원소를 끼워 넣으며 이 구간을 늘린다.
삽입 정렬(Insertion Sort)은 배열의 앞부분을 정렬된 구간으로 유지하면서 다음 원소를 알맞은 위치에 끼워 넣는다. 손에 든 카드를 순서에 맞게 정리하는 과정과 비슷하다.
배열 인덱스를 0부터 시작하면 다음 순서로 처리한다.
A[0]하나를 정렬된 구간으로 본다.i = 1부터A[i]를key에 저장한다.- 정렬된 앞쪽 구간에서
key보다 큰 원소를 오른쪽으로 한 칸씩 민다. - 비워진 위치에
key를 넣는다. - 마지막 원소까지 반복한다.
배열 [5, 2, 4, 1]을 추적하면 다음과 같다.
| 회전 | key | 회전 후 배열 | 보장되는 구간 |
|---|---|---|---|
| 1 | 2 | [2, 5, 4, 1] | [2, 5]가 정렬됨 |
| 2 | 4 | [2, 4, 5, 1] | [2, 4, 5]가 정렬됨 |
| 3 | 1 | [1, 2, 4, 5] | 전체 정렬 완료 |
삽입 정렬에서 “앞쪽 구간이 정렬되었다”는 말은 그 구간 내부의 순서가 맞다는 뜻이다. 예를 들어 2회전 뒤의 [2, 4, 5]는 정렬되어 있지만, 뒤에 있는 1이 앞으로 들어올 수 있으므로 세 원소의 전체 최종 위치가 확정된 것은 아니다.
복잡도와 안정성
- 이미 오름차순이면 각
key가 바로 앞 원소보다 크거나 같으므로 한 번씩만 확인해 최선 Θ(n)이 된다. - 내림차순이면 각
key가 앞 원소를 모두 지나가야 하므로 평균·최악은 Θ(n²)이다. - 최악의 경우 오른쪽으로 미는 원소 수의 합은
1 + 2 + ... + (n - 1) = n(n - 1) / 2다. key보다 큰 원소만 이동시키면 같은 키의 상대 순서를 보존하므로 안정적이다.key와 같은 원소까지 이동시키는 구현은 안정성을 잃을 수 있다.
삽입 위치를 이진 탐색으로 찾더라도 배열에서 빈자리를 만들기 위한 원소 이동은 남아 있으므로 전체 시간 복잡도가 자동으로 O(n log n)이 되는 것은 아니다.
삽입 정렬의 안정성을 유지하려면 일반적으로 현재 키보다 큰 원소만 이동한다. 같은 키까지 이동시키는 구현은 기존 동률 순서를 뒤집을 수 있으므로 알고리즘 이름만으로 모든 변형의 안정성을 단정하지 않는다.
선택 정렬
선택 정렬(Selection Sort)은 미정렬 구간에서 가장 작은 원소를 선택해 그 구간의 첫 위치와 교환한다. 한 회전이 끝날 때마다 앞쪽에 최종 위치가 하나씩 확정된다.
배열 [5, 2, 4, 1, 3]을 추적해 보자.
| 회전 | 미정렬 구간의 최솟값 | 회전 후 배열 | 최종 확정 |
|---|---|---|---|
| 1 | 1 | [1, 2, 4, 5, 3] | 인덱스 0의 1 |
| 2 | 2 | [1, 2, 4, 5, 3] | 인덱스 1의 2 |
| 3 | 3 | [1, 2, 3, 5, 4] | 인덱스 2의 3 |
| 4 | 4 | [1, 2, 3, 4, 5] | 인덱스 3의 4 |
첫 회전에는 n - 1개, 둘째 회전에는 n - 2개를 비교한다. 기본 선택 정렬의 전체 비교 횟수는 입력 상태와 관계없이 다음과 같다.
(n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2
따라서 이미 정렬된 배열도 최솟값을 찾기 위한 비교는 줄어들지 않는다. 반면 실제 교환은 회전마다 많아야 한 번이므로 최대 n - 1회다. 비교 비용은 크지만 교환 횟수가 적다는 점이 삽입·버블 정렬과 구분되는 특징이다.
일반적인 제자리 교환 방식의 선택 정렬은 안정 정렬이 아니다. 예를 들어 키만 비교하는 [(2, A), (2, B), (1, C)]에서 첫 번째 2와 1을 교환하면 [(1, C), (2, B), (2, A)]가 되어 같은 키 2의 A와 B 순서가 뒤바뀐다. 최솟값을 교환하지 않고 중간 원소를 밀어 넣는 변형은 안정적으로 만들 수 있지만, 시험에서는 보통 표준 교환 구현은 불안정으로 판단한다.
버블 정렬
버블 정렬(Bubble Sort)은 서로 이웃한 두 원소를 비교해 앞의 값이 더 크면 교환한다. 오름차순에서 왼쪽부터 오른쪽으로 한 회전을 수행하면 미정렬 구간의 최댓값이 오른쪽 끝까지 이동한다.
배열 [5, 2, 4, 1, 3]의 왼쪽→오른쪽 회전 결과는 다음과 같다.
| 회전 | 회전 후 배열 | 최종 확정 영역 |
|---|---|---|
| 1 | [2, 4, 1, 3, 5] | 맨 뒤의 5 |
| 2 | [2, 1, 3, 4, 5] | 뒤의 [4, 5] |
| 3 | [1, 2, 3, 4, 5] | 뒤의 [3, 4, 5] |
| 4 | 교환 없음 → 종료 | 전체 정렬 확인 |
한 회전이 끝나면 이미 확정된 뒤쪽 원소는 다음 회전의 비교 대상에서 제외할 수 있다. 또한 회전 중 교환이 한 번도 없었다면 남은 구간도 정렬되어 있으므로 즉시 종료할 수 있다.
- 조기 종료를 사용하면 이미 정렬된 입력의 비교는
n - 1회이므로 최선 Θ(n)이다. - 평균·최악은 Θ(n²)이며, 역순 배열에서는 인접 교환이 많이 발생한다.
- 앞의 값이 뒤의 값보다 클 때만 교환하면 같은 키끼리는 위치를 바꾸지 않으므로 안정적이다.
- 오른쪽에서 왼쪽으로 진행하는 변형에서는 작은 값이 앞쪽에 확정된다. 문제에서 회전 방향을 먼저 확인해야 한다.
셸 정렬
셸 정렬(Shell Sort)은 삽입 정렬이 멀리 떨어진 원소를 한 칸씩 옮겨야 하는 약점을 줄이기 위해, 큰 간격의 원소들을 먼저 부분적으로 정렬한 뒤 간격을 감소시키는 방법이다. 감소 간격 정렬(Diminishing Increment Sort)이라고도 한다.
간격을 g라고 할 때 인덱스가 같은 나머지를 갖는 원소들이 하나의 부분 수열이 된다.
- 부분 수열 0:
0, g, 2g, ... - 부분 수열 1:
1, 1 + g, 1 + 2g, ... - 나머지 부분 수열도 같은 방식으로 구성한다.
각 부분 수열을 삽입 정렬한 상태를 **g-정렬(g-sorted)**이라고 한다. 부분 수열을 실제 새 배열로 분리할 필요는 없고, 원래 배열에서 g칸씩 이동하며 처리할 수 있다.
배열 [5, 2, 4, 1, 3]에 간격 수열 2, 1을 적용해 보자.
간격 g = 2
- 인덱스
(0, 2, 4)의 값[5, 4, 3]→[3, 4, 5] - 인덱스
(1, 3)의 값[2, 1]→[1, 2] - 배열 결과:
[3, 1, 4, 2, 5]
이 배열은 아직 전체 오름차순이 아니지만, 두 칸 간격으로 본 각 부분 수열은 정렬되어 있다.
간격 g = 1
모든 원소가 하나의 부분 수열이 되므로 전체 배열에 삽입 정렬을 적용한다.
[3, 1, 4, 2, 5] → [1, 2, 3, 4, 5]
간격 수열과 복잡도
- 간격은 양의 정수로 줄어들며 마지막 값은 반드시
1이어야 전체 정렬이 보장된다. - 원래 셸 방식처럼
floor(n/2), floor(n/4), ..., 1을 사용할 수 있지만, 더 효율적인 여러 간격 수열이 존재한다. - 시간 복잡도는 간격 수열에 따라 달라지므로 셸 정렬 전체에 하나의 평균·최악 복잡도를 고정해서 적용하면 안 된다.
- 단순한 절반 간격 수열은 최악의 경우 O(n²)가 될 수 있다. 일부 수험서에서 제시하는 평균 O(n^1.5)는 특정 분석·간격 가정에 따른 근삿값이지 모든 셸 정렬 구현의 보편적 복잡도는 아니다.
- 멀리 떨어진 원소가 이동하면서 같은 키의 상대 순서가 바뀔 수 있으므로 일반적으로 안정성을 보장하지 않는다.