정렬과 탐색 알고리즘
대표 정렬의 안정성·제자리성·복잡도와 순차·이진 탐색 조건을 비교한다.
1. 정렬의 비교 기준
- 안정 정렬: 키가 같은 원소의 기존 상대 순서를 유지한다.
- 제자리 정렬: 입력 크기에 비례하는 추가 배열을 거의 사용하지 않는다.
- 비교 정렬: 원소 비교를 기반으로 하며 일반적인 하한은 Ω(n log n)이다.
2. 단순 정렬
버블정렬
인접 원소를 비교하여 큰 값을 뒤로 보낸다. 일반 구현은 O(n²)이며, 한 회전에서 교환이 없으면 중단하는 최적화가 있을 때 이미 정렬된 입력은 O(n)이 가능하다. 안정·제자리 정렬이다.
선택정렬
정렬되지 않은 부분에서 최솟값을 찾아 앞쪽 원소와 교환한다. 최선·평균·최악 모두 O(n²)이다. 일반적인 구현은 불안정하지만 제자리이다.
삽입정렬
정렬된 앞부분의 적절한 위치에 현재 원소를 삽입한다. 거의 정렬된 데이터에서 빠르며 최선 O(n), 평균·최악 O(n²)이다. 안정·제자리이다.
3. 고급 정렬
병합정렬
배열을 절반으로 나누고 각각 정렬한 뒤 병합한다. 항상 O(n log n)이며 안정적이다. 배열 구현에서는 O(n) 추가 공간이 필요하다.
퀵정렬
피벗을 기준으로 작은 값과 큰 값을 분할한 뒤 재귀적으로 정렬한다. 평균 O(n log n), 최악 O(n²)이다. 일반적으로 제자리이지만 불안정하다.
힙정렬
최대 힙을 만든 뒤 루트 최댓값을 배열 뒤로 보내는 과정을 반복한다. 최선·평균·최악 O(n log n), 제자리, 불안정이다. 전체 복잡도는 O(n log n)이다.
기수정렬
자릿수별로 버킷에 분배한다. 비교 정렬이 아니며 키 길이 d, 원소 수 n, 기수 범위를 k라 하면 보통 O(d(n+k))로 본다. 적용 가능한 키 형태가 제한된다.
4. 정렬 비교표
| 알고리즘 | 최선 | 평균 | 최악 | 안정 | 추가 공간 |
|---|---|---|---|---|---|
| 버블 | O(n)* | O(n²) | O(n²) | 예 | O(1) |
| 선택 | O(n²) | O(n²) | O(n²) | 보통 아니오 | O(1) |
| 삽입 | O(n) | O(n²) | O(n²) | 예 | O(1) |
| 병합 | O(n log n) | O(n log n) | O(n log n) | 예 | O(n) |
| 퀵 | O(n log n) | O(n log n) | O(n²) | 아니오 | 재귀 스택 |
| 힙 | O(n log n) | O(n log n) | O(n log n) | 아니오 | O(1) |
* 조기 종료 최적화가 있는 경우이다.
5. 탐색
- 순차 탐색: 정렬 여부와 무관하게 앞에서부터 확인, O(n)
- 이진 탐색: 정렬된 배열에서 중간값과 비교하여 범위를 절반으로 줄임, O(log n)
- 해시 탐색: 평균 O(1), 정렬 범위 탐색에는 부적합
- 이진탐색트리: 평균 O(log n), 편향되면 O(n)
이진 탐색에서 mid=(low+high)//2로 두고, 목표가 작으면 high=mid-1, 크면 low=mid+1로 갱신한다. 경계 갱신을 잘못하면 무한 반복이나 누락이 발생할 수 있다.
6. 정렬 과정 추적
삽입정렬은 현재 키를 정렬된 왼쪽 구간에 삽입한다.
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
[5,2,4,6,1]에서 i=1 후 [2,5,4,6,1], i=2 후 [2,4,5,6,1], 마지막에 [1,2,4,5,6]이 된다. 비교 조건을 >=로 바꾸면 같은 키의 상대 순서를 뒤집어 안정성을 잃을 수 있다.
7. 퀵정렬 분할과 피벗
분할 방식(Lomuto, Hoare)에 따라 피벗의 최종 위치와 교환 횟수가 다르다. 분할 코드는 단계별로 그대로 추적해야 한다. 정렬된 입력에서 첫 원소만 피벗으로 택하면 극단적 분할이 반복될 수 있다. 무작위 피벗이나 median-of-three는 평균 성능을 안정화한다.
8. 선형시간 비비교 정렬
- 계수정렬: 키 범위 k가 작을 때 O(n+k), 안정 구현 가능, O(k) 공간
- 기수정렬: 각 자릿수 정렬이 안정적이어야 전체 결과가 올바름
- 버킷정렬: 값이 구간에 균등 분포한다는 가정에서 평균 성능 우수
비교 정렬의 Ω(n log n) 하한은 비교만으로 순서를 결정하는 일반 모델에 적용되며 키의 구조를 사용하는 비비교 정렬에는 그대로 적용되지 않는다.
9. 이진 탐색 경계 변형
정확히 같은 값 하나를 찾는 것 외에 다음 변형이 중요하다.
def lower_bound(a, x):
lo, hi = 0, len(a) # [lo, hi)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
- lower_bound: x 이상인 첫 위치
- upper_bound: x 초과인 첫 위치
- x의 개수:
upper_bound(x)-lower_bound(x)
닫힌 구간 [lo,hi]와 반열린 구간 [lo,hi)의 갱신 규칙을 섞지 않는다.
10. 정렬 선택 시나리오
| 조건 | 후보 |
|---|---|
| 거의 정렬된 작은 배열 | 삽입정렬 |
| 최악 O(n log n), 제자리 필요 | 힙정렬 |
| 안정성과 일관된 O(n log n) | 병합정렬 |
| 평균적으로 빠른 범용 배열 정렬 | 퀵정렬 계열 |
| 작은 정수 범위 | 계수정렬 |
| 외부 저장장치의 대용량 데이터 | 외부 병합정렬 |
11. 탐색 전처리 비용
한 번만 탐색한다면 정렬 O(n log n) 후 이진 탐색보다 순차 탐색 O(n)이 낫다. 여러 번 q회 탐색한다면 정렬 후 비용은 O(n log n + q log n), 매번 순차 탐색은 O(qn)이다. 전체 작업량으로 비교한다.
최종 확인 문제
- 삽입정렬에서 비교 조건을
a[j] >= key로 두면 안정성에 어떤 영향이 있는가? - 정렬된 배열
[1,2,2,2,5,7]에서 값 2의 lower_bound와 upper_bound 인덱스를 0-base로 구하시오. - 키 범위가 0~999이고 원소가 1,000,000개인 정수 배열에 고려할 만한 정렬은 무엇이며 이유는 무엇인가?
- 한 번의 탐색을 위해 먼저 정렬하는 것이 일반적으로 불리한 이유를 복잡도로 설명하시오.
- 기수정렬의 각 자릿수 정렬이 안정적이어야 하는 이유를 설명하시오.