반응형
컴퓨터공학과 알고리즘 시험이나 개발자 면접에서 "데이터 정렬의 기본 동작 원리와 효율성 평가"를 물어볼 때 절대 빠지지 않는 주제가 있습니다. 바로 기본 정렬(버블, 선택, 삽입)과 고급 분할 정복 정렬(퀵, 병합)입니다.
"왜 퀵 정렬은 최악의 경우 O(N^2)이 되는데도 실무에서 가장 많이 쓸까?"
"안정 정렬(Stable Sort)과 제자리 정렬(In-Place Sort)의 의미는 무엇일까?"
5가지 정렬 알고리즘의 매커니즘부터 핵심 특성, 복잡도 분석, 그리고 시험 단골 객관식/서술형 문제 포인트까지 깔끔하게 정리해 드립니다!
1. 기본 정렬 알고리즘 (O(N^2) 계열)
1️⃣ 버블 정렬 (Bubble Sort)
- 동작 원리: 인접한 두 원소를 비교하여 크기 순서대로 맞지 않으면 서로 교환(Swap)하는 과정을 반복합니다. 1회전이 끝나면 가장 큰 원소가 맨 뒤로 이동합니다.
- 특징: 구현이 매우 단순하지만, 인접 원소 간 교환 작업이 빈번하게 일어나 실제 성능이 매우 떨어집니다.
- 안정성: 안정 정렬 (Stable)
2️⃣ 선택 정렬 (Selection Sort)
- 동작 원리: 전체 배열 중 최소값(또는 최대값)을 찾아 정렬되지 않은 맨 앞의 원소와 위치를 교환합니다. 회전마다 정렬된 영역이 하나씩 확장됩니다.
- 특징: 데이터 교환 횟수는 O(N)으로 적지만, 비교 횟수는 무조건 O(N^2)을 유지합니다.
- 안정성: 불안정 정렬 (Unstable) (동일한 값의 원소가 먼 위치와 교환될 때 순서가 뒤바뀔 수 있음)
3️⃣ 삽입 정렬 (Insertion Sort)
- 동작 원리: 2번째 원소부터 시작하여 앞쪽의 이미 정렬된 배열 영역 내에서 자신의 적절한 위치를 찾아 삽입합니다.
- 특징: 거의 정렬된 배열이 입력으로 들어올 경우, 비교 횟수가 크게 줄어들어 최선의 경우 $O(N)$이라는 빠른 성능을 보입니다.
- 안정성: 안정 정렬 (Stable)
2. 고급 분할 정복 정렬 알고리즘 (O(N \log N) 계열)
4️⃣ 퀵 정렬 (Quick Sort)
- 동작 원리:
- 하나의 피봇(Pivot)을 선정합니다.
- 피봇보다 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 이동시키는 파티셔닝(Partitioning)을 수행합니다.
- 피봇을 기준으로 나뉜 양쪽 부분 배열에 대해 재귀적으로 퀵 정렬을 반복합니다.
- 특징:
- 평균적으로 가장 빠른 속도를 자랑합니다 (지역성/Locality 효과와 낮은 상수항 덕분).
- 최악의 경우(이미 정렬된 배열에서 피봇을 맨 앞/뒤로 잡을 때)에는 분할이 불균형하게 이루어져 O(N^2)으로 성능이 떨어집니다.
- 안정성: 불안정 정렬 (Unstable)
5️⃣ 병합 정렬 (Merge Sort)
- 동작 원리:
- 배열을 반으로 나눕니다 (Divide).
- 나뉜 부분 배열의 크기가 1이 될 때까지 계속 재귀적으로 나눕니다.
- 나뉜 부분 배열들을 크기 순서대로 합치면서 정렬을 수행합니다 (Combine).
- 특징:
- 입력 데이터 상태와 무관하게 최악의 경우에도 항상 O(N \log N)을 보장합니다.
- 합치는 과정에서 임시 배열이 추가로 필요하므로 O(N)의 추가 공간 복잡도가 발생합니다.
- 안정성: 안정 정렬 (Stable)
3. 정렬 알고리즘 복잡도 종합 비교표 (★시험 1순위)
| 알고리즘 | 최선 시간 복잡도 | 평균 시간 복잡도 | 최악 시간 복잡도 | 공간 복잡도 | 안정성 (Stable) |
| 버블 정렬 | O(N) (최적화 시) | O(N^2) | O(N^2) | O(1) | O (안정) |
| 선택 정렬 | O(N^2) | O(N^2) | O(N^2) | O(1) | X (불안정) |
| 삽입 정렬 | O(N) | O(N^2) | O(N^2) | O(1) | O (안정) |
| 퀵 정렬 | O(N \log N) | O(N \log N) | O(N^2) | O(\log N) | X (불안정) |
| 병합 정렬 | O(N \log N) | O(N \log N) | O(N \log N) | O(N) | O (안정) |
💡 핵심 용어 정리
- 안정 정렬 (Stable Sort): 정렬 후에도 값이 같은 원소들의 기존 상대적 순서가 유지되는 정렬 방식 (버블, 삽입, 병합 등).
- 제자리 정렬 (In-Place Sort): 입력 배열 외에 추가적인 메모리 공간을 거의 사용하지 않는 방식 (O(1) 공간 복잡도).
4. 시험 단골 출제 유형 체크
- Q. 최악의 시간 복잡도가 O(N^2)임에도 불구하고, 실제 환경에서 가장 평균적으로 속도가 빠르고 널리 쓰이는 분할 정복 기반 정렬은?
- 👉 퀵 정렬 (Quick Sort) 입니다.
- Q. 항상 $O(N \log N)$의 시간 복잡도를 보장하지만, 정렬 과정에서 O(N)의 추가적인 메모리 공간이 필요한 정렬은?
- 👉 병합 정렬 (Merge Sort) 입니다.
- Q. 입력 데이터가 이미 '거의 정렬된 상태'일 때, 가장 효율적이며 O(N)의 시간 복잡도를 갖는 기본 정렬 알고리즘은?
- 👉 삽입 정렬 (Insertion Sort) 입니다.
반응형
