Algorithm / DS · 한장정리
[기술사토픽] 정렬 알고리즘 총정리 완벽 정리 - 한장정리
버블·선택·삽입·퀵·병합·힙 정렬 시간복잡도와 특징, 안정 정렬 vs 불안정 정렬, 비교/비비교 정렬까지 기술사 빈출 주제를 완벽 정리합니다.
Ⅰ.데이터 순서화 기술, 정렬 알고리즘의 개요
개념: 정렬(Sorting)이란 데이터 집합을 특정 기준(오름차순·내림차순)으로 재배열하는 알고리즘입니다. 탐색·병합 등 다른 알고리즘의 전처리 단계로 활용됩니다.
분류: (1) 비교 기반 — 원소 간 비교로 정렬 (O(n log n) 하한) (2) 비비교 기반 — 원소 값 활용 (O(n) 가능, 단 제약 있음)
Ⅱ.주요 정렬 알고리즘 비교표
| 알고리즘 | 최선 | 평균 | 최악 | 공간 | 안정 | 특징 |
|---|---|---|---|---|---|---|
| 버블 정렬 | 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²) | O(log n) | ❌ | 피벗 기반 분할. 평균 가장 빠름 |
| 병합 정렬 | O(n log 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) | ❌ | 힙 자료구조 활용. 제자리 정렬 |
| 계수 정렬 | O(n+k) | O(n+k) | O(n+k) | O(k) | ✅ | 비비교. 정수·범위 제한 시 |
시험 포인트
안정 정렬(같은 값의 상대 순서 유지): 버블·삽입·병합·계수 정렬
최악 O(n log n) 보장: 병합 정렬, 힙 정렬
평균 가장 빠름: 퀵 정렬 (단, 최악 O(n²) — 피벗 선택이 핵심)
Ⅲ.주요 정렬 동작 원리 & 선택 기준
가. 퀵 정렬 동작 원리
|
① 피벗 선택
|
배열에서 기준값(피벗) 선택 |
| ↓ | |
|
② 분할(Partition)
|
피벗 기준으로 작은 값/큰 값 분리 |
| ↓ | |
|
③ 재귀 호출
|
왼쪽·오른쪽 부분 배열에 재귀 적용 |
나. 상황별 정렬 선택 기준
| 상황 | 추천 정렬 | 이유 |
|---|---|---|
| 일반적인 경우 | 퀵 정렬 | 평균 O(n log n), 캐시 효율 좋음 |
| 안정성 필요 | 병합 정렬 | 안정 + 최악 O(n log n) 보장 |
| 메모리 제한 | 힙 정렬 | 제자리 정렬 O(1) 공간 |
| 거의 정렬된 데이터 | 삽입 정렬 | 최선 O(n) |
| 정수·범위 제한 | 계수/기수 정렬 | O(n) 선형 시간 |
| 연결 리스트 | 병합 정렬 | 임의 접근 불필요 |
Ⅳ.결론 및 전문가 의견
결론
정렬 알고리즘은 상황에 맞는 선택이 핵심입니다.
실무에서는 대부분 언어가 팀소트(TimSort) — 삽입 정렬 + 병합 정렬 하이브리드 — 를 기본 정렬로 사용하며, 안정성과 성능을 동시에 확보합니다.
"완벽한 정렬 알고리즘은 없다. 데이터의 특성과 제약 조건에 맞는 알고리즘을 선택하는 것이 진짜 실력이다."
블로그: 기술사 학습노트 · imt-log.tistory.com
'알고리즘자료구조' 카테고리의 다른 글
| 그래프 자료구조 표현 방법과 활용 정리 (0) | 2026.03.27 |
|---|---|
| 동적 프로그래밍 DP 핵심 개념과 유형 정리 (0) | 2026.03.27 |
| 빅오 표기법 시간복잡도 공간복잡도 총정리 (0) | 2026.03.27 |
| 백트래킹 알고리즘 개념과 구현 완벽 정리 (0) | 2026.03.27 |
| 알고리즘·자료구조 완전정복 — 기술사 핵심 토픽 모음 (0) | 2026.03.18 |
