topic★★★★★난이도 · 약 30분
정렬 알고리즘
선택·버블·삽입은 O(n²), 퀵·병합·힙은 O(n log n). PASS별 결과 추적이 실기 단골.
#정렬#실기핵심
왜 배우는가
버블 정렬 2 PASS 후 배열 상태 같은 문제가 서술형으로 나온다.
| 정렬 | 평균 | 최악 | 안정 | 설명 |
|---|---|---|---|---|
| 선택 (Selection) | O(n²) | O(n²) | X | 최솟값을 앞으로 |
| 버블 (Bubble) | O(n²) | O(n²) | O | 인접 비교·교환 |
| 삽입 (Insertion) | O(n²) | O(n²) | O | 정렬된 영역에 삽입 |
| 셸 (Shell) | O(n^1.5) | O(n²) | X | 간격 기반 삽입 |
| 퀵 (Quick) | O(n log n) | O(n²) | X | 피벗 분할 |
| 병합 (Merge) | O(n log n) | O(n log n) | O | 분할 정복 |
| 힙 (Heap) | O(n log n) | O(n log n) | X | 힙 자료구조 |
| 기수 (Radix) | O(dn) | O(dn) | O | 자릿수 기반 |
안정 정렬 (값이 같을 때 원래 순서 유지) — 버블·삽입·병합·기수. 불안정 — 선택·퀵·힙·셸.
pseudo
-- 버블 정렬 의사 코드
for i from 0 to n-1:
for j from 0 to n-i-2:
if a[j] > a[j+1]:
swap(a[j], a[j+1])
-- 삽입 정렬
for i from 1 to n-1:
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j+1] = a[j]
j -= 1
a[j+1] = keyPASS별 결과 추적 — 버블 정렬은 1 PASS마다 최댓값이 끝으로 간다. 삽입 정렬은 1 PASS마다 앞쪽이 정렬된 상태가 1칸 더 커진다. 시험에서는 특정 PASS 시점의 배열 상태를 직접 적어야 한다.
실기 드릴 3문항
edit실기 드릴 · 단답형
배열 [5, 2, 4, 1, 3]에 삽입 정렬을 적용할 때 2 PASS 수행 후 배열 상태는?
edit실기 드릴 · 단답형
최악의 경우 O(n²) 성능을 가지는 분할정복 정렬은?
check_circle실기 드릴 · OX
퀵 정렬은 안정 정렬이다.