정렬 알고리즘
1. 정렬 알고리즘이란?
정렬 알고리즘은 여러 개의 데이터를 특정한 기준에 따라 순서대로 배치하는 알고리즘이다.
예를 들어 다음과 같은 데이터가 있다고 하자.
[5, 2, 8, 1, 3]오름차순으로 정렬하면 다음과 같이 된다.
[1, 2, 3, 5, 8]정렬은 단순히 숫자를 순서대로 배치하는 것뿐만 아니라, 탐색, 데이터 처리, 우선순위 관리 등 다양한 알고리즘의 기초가 된다.
이번에는 정렬 알고리즘을 난이도 순으로 학습했다.
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Heap Sort
각 알고리즘을 이해할 때는 단순히 시간 복잡도만 외우는 것이 아니라 다음 항목을 함께 확인해야 한다.
- 동작 방식
- 시간 복잡도
- 공간 복잡도
- Stable 여부
- 언제 사용하는지
2. Stable Sort란?
정렬 알고리즘을 공부하면서 Stable(안정 정렬)이라는 개념을 알게 되었다.
Stable Sort는 값이 같은 데이터들의 원래 순서를 유지하는 정렬을 의미한다.
예를 들어 다음과 같은 데이터가 있다고 하자.
이름 점수
A 80
B 70
C 80점수를 기준으로 정렬했을 때 Stable Sort라면 다음과 같이 된다.
B 70
A 80
C 80A와 C는 점수가 모두 80점이므로 값은 같지만, 정렬하기 전에도 A → C 순서였기 때문에 정렬 후에도 A → C 순서가 유지된다.
반면 Unstable Sort에서는 다음처럼 순서가 바뀔 수도 있다.
B 70
C 80
A 80따라서 Stable 여부는 단순히 정렬 알고리즘의 성능만을 비교하는 것이 아니라, 같은 값을 가진 데이터의 기존 순서를 유지해야 하는 상황에서 중요한 요소라고 이해했다.
3. Bubble Sort
개념
Bubble Sort는 서로 인접한 두 값을 비교하고 순서가 잘못되어 있다면 서로 교환하는 방식으로 동작한다.
예를 들어:
[5, 3, 8, 1]먼저 5와 3을 비교한다.
5 > 3따라서 두 값을 교환한다.
[3, 5, 8, 1]다음으로 5와 8을 비교한다.
5 < 8순서가 올바르기 때문에 그대로 둔다.
다음으로 8과 1을 비교한다.
8 > 1따라서 교환한다.
[3, 5, 1, 8]이렇게 한 번 끝까지 탐색하면 가장 큰 값이 배열의 가장 오른쪽으로 이동한다.
다시 앞에서부터 같은 과정을 반복하면 최종적으로 정렬된다.
[5, 3, 8, 1]
↓
[3, 5, 1, 8]
↓
[3, 1, 5, 8]
↓
[1, 3, 5, 8]핵심
Bubble Sort는 한 번의 탐색이 끝날 때마다 가장 큰 값이 뒤쪽으로 밀려나는 것이 핵심이다.
이 과정에서 큰 값이 뒤쪽으로 이동하는 모습이 마치 거품이 위로 올라가는 것과 비슷하기 때문에 Bubble Sort라는 이름이 붙었다.
시간 복잡도
경우시간 복잡도
| 최선 | O(N)¹ |
| 평균 | O(N²) |
| 최악 | O(N²) |
¹ 이미 정렬되어 있는지 확인하는 조기 종료 최적화를 적용한 경우
공간 복잡도
O(1)배열 자체에서 값을 교환하면서 정렬할 수 있기 때문에 별도의 큰 배열이 필요하지 않다.
Stable 여부
Stable일반적인 Bubble Sort 구현은 같은 값의 순서를 유지할 수 있다.
사용 상황
대규모 데이터를 정렬하기에는 비효율적이다.
주로 다음과 같은 상황에서 의미가 있다.
- 정렬 알고리즘의 기본 원리를 학습할 때
- 데이터가 매우 적을 때
- 알고리즘 교육 목적으로 사용할 때
핵심 정리
Bubble Sort는 인접한 값끼리 비교하고 교환하면서 큰 값을 뒤로 보내는 정렬이다.
4. Selection Sort
개념
Selection Sort는 Bubble Sort처럼 인접한 값을 계속 교환하는 방식이 아니라, 현재 정렬되지 않은 영역에서 최솟값을 찾아서 앞으로 가져오는 방식이다.
예를 들어:
[5, 3, 8, 1, 4]전체 데이터에서 가장 작은 값을 찾는다.
최솟값 = 1찾은 1을 첫 번째 위치의 5와 교환한다.
[1, 3, 8, 5, 4]이제 첫 번째 위치는 정렬이 끝난 것으로 본다.
다음에는 두 번째 위치부터 탐색한다.
[1, 3, 8, 5, 4]
↑남아 있는 데이터에서 최솟값을 찾는다.
3이미 두 번째 위치에 있으므로 그대로 둔다.
그다음에는:
[1, 3, 8, 5, 4]
↑남은 데이터에서 최솟값인 4를 찾는다.
[1, 3, 4, 5, 8]이 과정을 반복해서 전체 배열을 정렬한다.
핵심 구조
Selection Sort는 배열을 다음과 같이 생각하면 이해하기 쉽다.
정렬된 영역 | 정렬되지 않은 영역예:
[1, 3] | [8, 5, 4]정렬되지 않은 영역에서 최솟값을 찾고 정렬된 영역의 바로 다음 위치에 배치한다.
[1, 3, 4] | [5, 8]이 과정을 반복하면서 정렬된 영역을 하나씩 늘려간다.
시간 복잡도
경우시간 복잡도
| 최선 | O(N²) |
| 평균 | O(N²) |
| 최악 | O(N²) |
이미 데이터가 정렬되어 있어도 남아 있는 데이터에서 최솟값을 찾기 위한 탐색을 계속 수행하기 때문에 일반적인 구현에서는 최선의 경우에도 O(N²)이다.
공간 복잡도
O(1)추가 배열을 만들지 않고 원본 배열에서 교환할 수 있다.
Stable 여부
Unstable일반적인 Selection Sort 구현에서는 같은 값을 가진 데이터의 순서가 바뀔 수 있다.
사용 상황
대규모 데이터를 정렬하기에는 적합하지 않다.
다만 Selection Sort는 정렬 과정에서 교환 횟수를 비교적 적게 가져갈 수 있다는 특징이 있다.
핵심 정리
Selection Sort는 정렬되지 않은 영역에서 최솟값을 찾아 현재 위치로 가져오는 정렬이다.
5. Insertion Sort
개념
Insertion Sort는 이미 정렬된 영역을 유지하면서 새로운 값을 적절한 위치에 삽입하는 방식이다.
실제 카드 게임에서 카드를 손에 들고 정렬하는 과정을 생각하면 이해하기 쉽다.
예:
[5, 3, 8, 1, 4]첫 번째 값인 5는 이미 정렬된 것으로 생각한다.
[5]다음 값 3을 가져온다.
[5] 33은 5보다 작기 때문에 5를 오른쪽으로 이동시키고 3을 앞에 넣는다.
[3, 5]다음 값 8을 가져온다.
[3, 5] 88은 가장 크기 때문에 그대로 뒤에 놓는다.
[3, 5, 8]다음 값 1을 가져온다.
[3, 5, 8] 11보다 큰 값들을 오른쪽으로 이동시킨다.
[3, 5, 8]
↑결과:
[1, 3, 5, 8]이후 4도 적절한 위치에 삽입한다.
[1, 3, 4, 5, 8]핵심 구조
Insertion Sort 역시 배열을 다음과 같이 나누어 생각하면 이해하기 쉽다.
정렬된 영역 | 정렬되지 않은 영역정렬되지 않은 영역에서 하나의 값을 가져온 뒤, 정렬된 영역에서 자신이 들어갈 위치를 찾아 삽입한다.
시간 복잡도
경우시간 복잡도
| 최선 | O(N) |
| 평균 | O(N²) |
| 최악 | O(N²) |
특히 데이터가 이미 정렬되어 있거나 거의 정렬되어 있다면 매우 효율적으로 동작할 수 있다.
공간 복잡도
O(1)추가 배열 없이 원본 배열에서 값을 이동시키면서 정렬할 수 있다.
Stable 여부
Stable같은 값의 기존 순서를 유지할 수 있다.
사용 상황
Insertion Sort는 다음과 같은 상황에서 유용하다.
- 데이터의 개수가 적을 때
- 데이터가 거의 정렬되어 있을 때
- 정렬된 데이터에 새로운 데이터를 조금씩 추가할 때
- 고급 정렬 알고리즘에서 작은 구간을 처리할 때
핵심 정리
Insertion Sort는 정렬된 영역을 유지하면서 새로운 값을 알맞은 위치에 끼워 넣는 정렬이다.
6. Merge Sort
여기부터는 기본 정렬보다 한 단계 높은 정렬 알고리즘이다.
Merge Sort는 분할 정복(Divide and Conquer)을 사용하는 대표적인 정렬 알고리즘이다.
핵심은 다음과 같다.
계속 반으로 나눈다.
↓
더 이상 나눌 수 없을 때까지 나눈다.
↓
작은 배열부터 정렬하면서 합친다.동작 과정
예를 들어:
[8, 3, 5, 4, 7, 6, 1, 2]먼저 반으로 나눈다.
[8, 3, 5, 4] [7, 6, 1, 2]다시 나눈다.
[8, 3] [5, 4] [7, 6] [1, 2]다시 나눈다.
[8] [3] [5] [4] [7] [6] [1] [2]이제 더 이상 나눌 수 없으므로 다시 합친다.
[8] + [3]
→ [3, 8][5] + [4]
→ [4, 5]그리고:
[3, 8] + [4, 5]
→ [3, 4, 5, 8]반대쪽도:
[7] + [6]
→ [6, 7]
[1] + [2]
→ [1, 2]
[6, 7] + [1, 2]
→ [1, 2, 6, 7]마지막으로:
[3, 4, 5, 8]
+
[1, 2, 6, 7]두 배열을 비교하면서 작은 값을 순서대로 가져오면:
[1, 2, 3, 4, 5, 6, 7, 8]이 된다.
왜 O(N log N)인가?
Merge Sort는 데이터를 계속 절반으로 나눈다.
데이터가 N개라면 절반으로 나누는 과정은 대략:
log N번 진행된다.
그리고 각각의 단계에서 전체 데이터를 한 번씩 비교하면서 병합한다.
따라서:
N × log N이 되어 시간 복잡도는:
O(N log N)이 된다.
시간 복잡도
경우시간 복잡도
| 최선 | O(N log N) |
| 평균 | O(N log N) |
| 최악 | O(N log N) |
Merge Sort의 중요한 특징은 최악의 경우에도 O(N log N)을 보장한다는 것이다.
공간 복잡도
O(N)두 배열을 합치는 과정에서 추가적인 공간이 필요하기 때문이다.
Stable 여부
Stable일반적인 Merge Sort 구현은 Stable하게 만들 수 있다.
사용 상황
- 안정적인 O(N log N) 성능이 필요할 때
- Stable Sort가 필요할 때
- 데이터의 크기가 클 때
- 외부 정렬(External Sort)이 필요한 경우
핵심 정리
Merge Sort는 데이터를 계속 반으로 나눈 다음 정렬하면서 다시 합치는 분할 정복 알고리즘이다.
7. Quick Sort
Quick Sort 역시 분할 정복(Divide and Conquer)을 사용하는 알고리즘이다.
하지만 Merge Sort와는 분할하는 방식이 다르다.
Quick Sort의 핵심 개념은 Pivot(피벗)이다.
동작 과정
예를 들어:
[6, 3, 8, 5, 2, 7, 4, 1]여기서 5를 Pivot으로 선택했다고 하자.
Pivot = 5Pivot보다 작은 값과 큰 값을 나눈다.
[3, 2, 4] 5 [6, 8, 7]그다음 왼쪽 영역과 오른쪽 영역에 다시 Quick Sort를 적용한다.
왼쪽:
[3, 2, 4]Pivot을 3으로 선택하면:
[2] 3 [4]오른쪽:
[6, 8, 7]Pivot을 7로 선택하면:
[6] 7 [8]최종적으로:
[2, 3, 4, 5, 6, 7, 8]이 된다.
Merge Sort와의 차이
둘 다 분할 정복을 사용하지만 핵심이 다르다.
Merge Sort
데이터를 분할
↓
작은 단위까지 나눔
↓
병합하는 과정에서 정렬Quick Sort
Pivot 선택
↓
Pivot보다 작은 값 / 큰 값으로 분할
↓
각 영역을 다시 정렬따라서 다음과 같이 기억할 수 있다.
Merge Sort는 합치는 과정에서 정렬하고, Quick Sort는 Pivot을 기준으로 나누는 과정에서 정렬의 구조를 만든다.
8. Quick Sort의 시간 복잡도
Quick Sort는 Merge Sort와 달리 최악의 경우 시간 복잡도가 달라진다.
경우시간 복잡도
| 최선 | O(N log N) |
| 평균 | O(N log N) |
| 최악 | O(N²) |
평균적으로 Pivot이 적절하게 선택되어 데이터가 균형 있게 나뉘면:
N
↓
N/2 + N/2
↓
N/4 + N/4 + N/4 + N/4
↓
...와 같은 형태가 된다.
따라서 평균적으로 O(N log N)이 된다.
하지만 Pivot이 계속 최솟값이나 최댓값으로 선택되면 문제가 발생한다.
예를 들어 이미 정렬된 데이터:
[1, 2, 3, 4, 5, 6, 7]에서 계속 가장 작은 값을 Pivot으로 선택하면:
[1] | [2, 3, 4, 5, 6, 7]
[2] | [3, 4, 5, 6, 7]
[3] | [4, 5, 6, 7]처럼 한쪽으로만 분할된다.
이렇게 되면 균형 잡힌 분할이 이루어지지 않아서 최악의 경우 O(N²)가 된다.
공간 복잡도
평균적인 재귀 호출 스택 기준으로:
O(log N)정도가 된다.
다만 분할이 계속 한쪽으로 치우치는 최악의 경우에는 재귀 깊이가 N까지 증가하여 O(N)이 될 수 있다.
Stable 여부
Unstable일반적인 Quick Sort 구현은 같은 값의 순서를 보장하지 않는다.
사용 상황
- 평균적인 성능이 빠른 정렬이 필요할 때
- 배열 기반 데이터를 정렬할 때
- 추가 메모리 사용을 줄이고 싶을 때
핵심 정리
Quick Sort는 Pivot을 기준으로 데이터를 나누고, 각각의 영역을 다시 정렬하는 분할 정복 알고리즘이다.
평균적으로 O(N log N)이지만 Pivot 선택이 좋지 않으면 최악의 경우 O(N²)가 될 수 있다.
9. Heap Sort
Heap Sort는 Heap 자료구조를 이용하는 정렬 알고리즘이다.
Heap은 완전 이진 트리 형태를 기반으로 하는 자료구조이며, Max Heap에서는 다음 조건을 만족한다.
부모 노드 ≥ 자식 노드예를 들어:
9
/ \
7 8
/ \ / \
3 5 6 2여기에서는 가장 큰 값인 9가 Root에 위치한다.
즉, Max Heap을 사용하면 가장 큰 값을 빠르게 확인할 수 있다.
Heap Sort의 기본 과정
- 배열을 Max Heap으로 만든다.
- Root에 있는 최댓값을 꺼낸다.
- 꺼낸 값을 배열의 뒤쪽에 배치한다.
- 남은 데이터로 Heap을 다시 구성한다.
- 이 과정을 반복한다.
예를 들어:
[4, 10, 3, 5, 1]을 Max Heap으로 만들면:
10
/ \
5 3
/ \
4 1이 된다.
가장 큰 값인 10을 뒤쪽으로 이동시킨다.
[4, 5, 3, 1, 10]남은 영역을 다시 Heap으로 정리한다.
[5, 4, 3, 1, 10]다시 최댓값인 5를 뒤로 이동시킨다.
[4, 1, 3, 5, 10]이 과정을 반복하면:
[1, 3, 4, 5, 10]이 된다.
시간 복잡도
경우시간 복잡도
| 최선 | O(N log N) |
| 평균 | O(N log N) |
| 최악 | O(N log N) |
Heap Sort의 중요한 장점은 최악의 경우에도 O(N log N)을 보장한다는 것이다.
공간 복잡도
일반적인 배열 기반 In-place 구현에서는:
O(1)이다.
추가적인 배열을 만들지 않고 원본 배열 내부에서 Heap을 구성할 수 있기 때문이다.
Stable 여부
Unstable일반적인 Heap Sort에서는 같은 값을 가진 데이터의 순서를 보장하지 않는다.
사용 상황
- 최악의 경우에도 O(N log N) 성능이 필요한 경우
- 추가 메모리 사용을 최소화해야 하는 경우
- Heap 자료구조의 특성을 활용해야 하는 경우
핵심 정리
Heap Sort는 Heap을 구성한 뒤 최댓값 또는 최솟값을 반복적으로 꺼내 정렬하는 알고리즘이다.
10. 6가지 정렬 알고리즘 비교
알고리즘핵심 동작 최선 평균 최악 추가 공간 Stable
| Bubble Sort | 인접 값 비교 및 교환 | O(N)¹ | O(N²) | O(N²) | O(1) | O |
| Selection Sort | 최솟값을 찾아 배치 | O(N²) | O(N²) | O(N²) | O(1) | X |
| Insertion Sort | 정렬 영역에 삽입 | O(N) | O(N²) | O(N²) | O(1) | O |
| Merge Sort | 분할 후 병합 | O(N log N) | O(N log N) | O(N log N) | O(N) | O |
| Quick Sort | Pivot 기준 분할 | O(N log N) | O(N log N) | O(N²) | O(log N)² | X |
| Heap Sort | Heap을 이용한 추출 | O(N log N) | O(N log N) | O(N log N) | O(1) | X |
¹ 조기 종료 최적화를 적용한 경우
² 평균적인 재귀 호출 스택 기준이며, 최악의 경우 O(N)이 될 수 있다.
11. O(N²)와 O(N log N)의 차이
이번 정렬 알고리즘을 공부하면서 데이터의 크기가 커질수록 시간 복잡도가 얼마나 중요한지 알 수 있었다.
예를 들어 N = 1,000,000이라고 하면:
O(N²)
= 1,000,000²
= 1,000,000,000,000반면:
O(N log N)
≈ 1,000,000 × 20
≈ 20,000,000정도가 된다.
Big-O가 실제 실행 시간을 정확하게 나타내는 것은 아니지만, 데이터의 크기가 증가할 때 알고리즘의 성능이 어떤 형태로 증가하는지 비교하는 데 매우 중요하다.
따라서 기본 정렬과 고급 정렬 사이에는 다음과 같은 차이가 있다.
Bubble / Selection / Insertion
↓
O(N²)반면:
Merge / Quick / Heap
↓
O(N log N) 중심이다.
12. 기본 정렬 3개의 차이
세 가지 기본 정렬은 모두 비교를 기반으로 하지만 동작 방식이 서로 다르다.
Bubble Sort
인접한 값 비교
↓
필요하면 교환
↓
큰 값을 뒤로 이동핵심은 비교와 교환이다.
Selection Sort
정렬되지 않은 영역 탐색
↓
최솟값 탐색
↓
현재 위치와 교환핵심은 선택이다.
Insertion Sort
정렬된 영역 유지
↓
새로운 값 선택
↓
적절한 위치에 삽입핵심은 삽입이다.
13. 고급 정렬 3개의 차이
Merge Sort
분할
↓
분할
↓
분할
↓
작은 단위
↓
병합하면서 정렬핵심은 분할과 병합이다.
Quick Sort
Pivot 선택
↓
작은 값 / 큰 값으로 분할
↓
각 영역에 다시 Quick Sort핵심은 Pivot이다.
Heap Sort
Heap 구성
↓
최댓값 또는 최솟값 추출
↓
Heap 재구성
↓
반복핵심은 Heap이다.
14. 어떤 정렬을 사용해야 하는가?
정렬 알고리즘은 단순히 시간 복잡도만 보고 선택하는 것은 아니다.
데이터의 특징과 필요한 조건을 함께 고려해야 한다.
데이터가 거의 정렬되어 있는 경우
Insertion Sort가 유리할 수 있다.
예:
[1, 2, 3, 5, 4, 6, 7]처럼 이미 대부분 정렬되어 있고 일부 데이터만 위치가 잘못되어 있다면 Insertion Sort는 적은 작업으로 정렬할 수 있다.
Stable Sort가 필요한 경우
Merge Sort를 고려할 수 있다.
같은 값을 가진 데이터들의 기존 순서를 유지해야 하는 상황에서 Stable Sort가 중요하다.
평균적인 빠른 정렬이 필요한 경우
Quick Sort 계열이 많이 사용된다.
특히 배열 기반 데이터에서 효율적인 구현이 가능하다.
최악의 경우에도 O(N log N)이 필요한 경우
Merge Sort 또는 Heap Sort를 고려할 수 있다.
두 알고리즘 모두 최악의 경우에도:
O(N log N)을 보장한다.
추가 메모리를 최소화해야 하는 경우
일반적인 In-place Heap Sort는 추가 공간을:
O(1)까지 줄일 수 있다는 장점이 있다.
15. 정렬 알고리즘을 한 문장으로 정리하기
각 알고리즘의 원리를 다음과 같이 기억할 수 있다.
Bubble Sort
→ 옆에 있는 값끼리 비교해서 큰 값을 뒤로 보낸다.
Selection Sort
→ 남은 값 중 최솟값을 찾아 앞으로 가져온다.
Insertion Sort
→ 정렬된 영역에 새로운 값을 알맞은 위치에 끼워 넣는다.
Merge Sort
→ 데이터를 계속 나눈 뒤 정렬하면서 다시 합친다.
Quick Sort
→ Pivot을 기준으로 작은 값과 큰 값을 나누고 다시 정렬한다.
Heap Sort
→ Heap에서 최댓값 또는 최솟값을 꺼내면서 정렬한다.16. 이번 학습에서 중요하게 기억할 내용
이번 단계에서는 단순히 알고리즘의 이름과 시간 복잡도를 암기하는 것보다 각 알고리즘이 어떤 방식으로 데이터를 움직이는지 이해하는 것이 중요했다.
특히 다음 내용을 기억해야 한다.
Bubble Sort
인접한 값들을 비교하고 교환하면서 큰 값을 뒤로 이동시킨다.
O(N²)Selection Sort
정렬되지 않은 영역에서 최솟값을 찾아 현재 위치에 배치한다.
O(N²)Insertion Sort
정렬된 영역에 새로운 값을 적절한 위치로 삽입한다.
최선 O(N)
평균/최악 O(N²)Merge Sort
데이터를 계속 반으로 나누고 병합하면서 정렬한다.
최선/평균/최악 O(N log N)Stable Sort가 가능하지만 추가 공간 O(N)이 필요하다.
Quick Sort
Pivot을 기준으로 데이터를 분할하고 각 영역을 다시 정렬한다.
평균 O(N log N)
최악 O(N²)Pivot을 어떻게 선택하느냐가 성능에 큰 영향을 준다.
Heap Sort
Heap의 구조를 이용하여 최댓값 또는 최솟값을 반복적으로 꺼내 정렬한다.
최선/평균/최악 O(N log N)일반적인 In-place 구현에서는 추가 공간 O(1)을 사용할 수 있다.
17. 최종 정리
이번 단계에서 가장 중요한 흐름은 다음과 같다.
기본 정렬
│
├─ Bubble Sort
│ └─ 인접한 값 비교/교환
│
├─ Selection Sort
│ └─ 최솟값 선택
│
└─ Insertion Sort
└─ 정렬된 영역에 삽입
↓
고급 정렬
│
├─ Merge Sort
│ └─ 분할 → 병합
│
├─ Quick Sort
│ └─ Pivot → 분할
│
└─ Heap Sort
└─ Heap → 최댓값/최솟값 추출그리고 시간 복잡도를 기준으로 보면:
Bubble / Selection / Insertion
↓
O(N²)에서
Merge / Quick / Heap
↓
O(N log N) 중심으로 발전한다.
특히 고급 정렬에서는 다음 세 가지를 확실하게 구분해야 한다.
Merge Sort
→ "나누고 합친다"
Quick Sort
→ "Pivot으로 나눈다"
Heap Sort
→ "Heap에서 꺼낸다"이번 정렬 알고리즘 학습을 통해 같은 문제인 "데이터를 정렬한다"를 해결하더라도 알고리즘의 구조에 따라 시간 복잡도와 메모리 사용량, 안정성, 실제 활용 상황이 크게 달라진다는 점을 이해했다.