왜 정렬 알고리즘을 알아야 할까?
정렬은 컴퓨터 과학에서 가장 기본적이면서도 중요한 연산입니다. 데이터베이스 쿼리, 검색 엔진, 추천 시스템 등 거의 모든 소프트웨어에서 정렬이 사용됩니다. 코딩 테스트에서도 정렬은 필수 주제이며, 정렬 알고리즘을 이해하면 분할 정복, 힙, 안정성 같은 핵심 개념도 자연스럽게 익힐 수 있습니다.
이 글에서는 가장 많이 사용되는 7가지 정렬 알고리즘을 시간복잡도, 안정성, 공간복잡도 관점에서 비교하고, 각각의 동작 원리를 설명합니다.
한눈에 비교
| 알고리즘 | 최선 | 평균 | 최악 | 공간 | 안정성 |
|---|---|---|---|---|---|
| 버블 정렬 | 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(log 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) | 안정 |
1. 버블 정렬 (Bubble Sort)
인접한 두 원소를 비교하여 순서가 잘못되어 있으면 교환하는 방식입니다. 마치 거품이 떠오르듯 큰 값이 배열의 끝으로 이동합니다.
동작 원리:
- •배열의 처음부터 끝까지 인접한 원소를 비교
- •잘못된 순서면 교환
- •한 번 순회할 때마다 가장 큰 원소가 제자리를 찾음
- •교환이 없을 때까지 반복
시간복잡도: 최선 O(n), 평균/최악 O(n²)
구현이 단순하여 교육 목적으로 많이 사용되지만, 실무에서는 성능 때문에 거의 사용되지 않습니다.
2. 삽입 정렬 (Insertion Sort)
카드 게임에서 손에 든 카드를 정렬하는 방식과 같습니다. 새로운 원소를 이미 정렬된 부분의 적절한 위치에 삽입합니다.
동작 원리:
- •두 번째 원소부터 시작
- •현재 원소를 이미 정렬된 부분과 비교
- •적절한 위치를 찾아 삽입
- •모든 원소에 대해 반복
시간복잡도: 최선 O(n), 평균/최악 O(n²)
거의 정렬된 데이터에서는 매우 효율적이며, 소규모 데이터셋에서 실제로 빠릅니다. Java의 Arrays.sort()는 작은 배열에 삽입 정렬을 사용합니다.
3. 선택 정렬 (Selection Sort)
배열에서 최솟값을 찾아 맨 앞과 교환하는 과정을 반복합니다.
동작 원리:
- •정렬되지 않은 부분에서 최솟값을 찾음
- •정렬되지 않은 부분의 첫 번째 원소와 교환
- •정렬된 부분의 크기를 1 늘림
- •모든 원소가 정렬될 때까지 반복
시간복잡도: 항상 O(n²)
교환 횟수가 O(n)으로 적다는 장점이 있지만, 비교 횟수가 항상 O(n²)이라 데이터 상태에 관계없이 느립니다.
4. 병합 정렬 (Merge Sort)
분할 정복(Divide and Conquer) 전략의 대표적인 예입니다. 배열을 반으로 나누고, 각각을 정렬한 뒤, 합치는 과정을 재귀적으로 수행합니다.
동작 원리:
- •배열을 절반으로 나눔 (Divide)
- •각 부분 배열을 재귀적으로 정렬 (Conquer)
- •정렬된 두 부분 배열을 하나로 합침 (Merge)
시간복잡도: 항상 O(n log n)
안정적이고 예측 가능한 성능을 보장합니다. 추가 메모리 O(n)이 필요하다는 단점이 있지만, 연결 리스트 정렬에서는 O(1) 추가 공간으로 구현 가능합니다.
5. 퀵 정렬 (Quick Sort)
피벗을 기준으로 작은 값과 큰 값을 분리하는 분할 정복 알고리즘입니다. 실무에서 가장 많이 사용되는 정렬 알고리즘 중 하나입니다.
동작 원리:
- •피벗 원소 선택
- •피벗보다 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 분할
- •각 부분을 재귀적으로 정렬
시간복잡도: 최선/평균 O(n log n), 최악 O(n²)
평균적으로 가장 빠른 범용 정렬 알고리즘입니다. 캐시 효율이 좋고, 제자리 정렬이 가능합니다. 피벗 선택 전략에 따라 최악의 경우를 피할 수 있습니다.
6. 힙 정렬 (Heap Sort)
최대 힙(또는 최소 힙) 자료구조를 이용한 정렬입니다. 힙에서 최댓값을 추출하는 과정을 반복합니다.
동작 원리:
- •배열을 최대 힙으로 변환 (Build Heap)
- •힙의 루트(최댓값)를 배열 끝으로 이동
- •힙 크기를 줄이고 힙 속성 복원 (Heapify)
- •힙이 빌 때까지 반복
시간복잡도: 항상 O(n log n)
추가 메모리 없이 O(n log n)을 보장합니다. 우선순위 큐와 밀접한 관련이 있어, 힙 정렬을 이해하면 우선순위 큐 문제도 쉽게 풀 수 있습니다.
7. 카운팅 정렬 (Counting Sort)
비교 기반이 아닌 정렬 알고리즘입니다. 각 값의 출현 횟수를 세어 정렬합니다.
동작 원리:
- •각 값의 출현 횟수를 카운트 배열에 저장
- •카운트 배열의 누적합 계산
- •원래 배열을 역순으로 순회하며 올바른 위치에 배치
시간복잡도: O(n + k), k는 값의 범위
값의 범위(k)가 원소 수(n)에 비해 크지 않을 때 매우 효율적입니다. O(n log n)의 한계를 넘어서는 선형 시간 정렬이 가능합니다.
어떤 상황에 어떤 정렬?
거의 정렬된 데이터 → 삽입 정렬
- •최선의 경우 O(n)으로 매우 빠릅니다.
안정성이 필요한 경우 → 병합 정렬
- •동일한 값의 상대적 순서가 보장됩니다.
평균적으로 가장 빠른 정렬 → 퀵 정렬
- •캐시 효율이 좋고 실무에서 가장 많이 사용됩니다.
메모리 제한이 있을 때 → 힙 정렬
- •추가 메모리 O(1)로 O(n log n)을 보장합니다.
값의 범위가 제한적일 때 → 카운팅 정렬
- •선형 시간 O(n+k)으로 정렬 가능합니다.
AlgoNote에서 직접 확인하세요
글로만 읽는 것보다 직접 눈으로 보면 이해가 훨씬 빠릅니다. AlgoNote에서는 각 정렬 알고리즘이 한 단계씩 어떻게 동작하는지 시각적으로 확인할 수 있습니다. 속도를 조절하고, 데이터를 바꿔가며 실험해보세요.