- 선택정렬 · 버블정렬 · 삽입정렬 · 퀵정렬 -
정렬(Sorting)은 모든 프로그래밍 언어에서 가장 기본적이면서도 중요한 알고리즘이다.
데이터를 정렬하면 탐색 시간이 줄어들고, 이후 처리 과정이 훨씬 효율적으로 된다.
이번 글에서는 대표적인 정렬 알고리즘(선택, 버블, 삽입, 퀵 정렬)을
원리 → 시각 자료 → 코드 → 시간 복잡도 → 특징 비교 순서로 정리해본다.
먼저 정렬이 필요한 이유는 다음과 같다.
1. 자료 탐색 속도 향상
2. 중복 제거 및 데이터 정리
3. 탐색/병합 등 다른 알고리즘의 전제 조건
복잡도(BIG-O) 개념을 간단 요약해보자.
- O(1) → O(log N) → O(N) → O(N log N) → O(N^2) → O(2^N) → O(N!)
O(1)은 빠른 정렬의 기준이다.
O(N!)은 데이터가 많아질수록 기하급수적으로 느려진다.
- 선택 정렬(Selection Sort)
원리
1. 전체 배열에서 최소값을 찾는다.
2. 해당 최소값을 맨 앞과 교환
3. 한 칸 오른쪽으로 이동하며 반복
시각화 (글 형태)
[5, 3, 8, 4, 2]
→ 최소값 2 선택 → 맨 앞과 교환
→ [2, 3, 8, 4, 5]
→ 그 다음 최소값 3 선택 → 이미 자리 O
→ 반복...
코드 예제 (C 언어)
void selection_sort(int arr[], int n) {
int i, j, min_idx, temp;
for (i = 0; i < n - 1; i++) {
min_idx = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// swap
temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
시간 복잡도
| 최악 / 평균 / 최선 | O(N^2) |
| 공간 복잡도 | O(1) |
특징
1. 구현은 직관적 → 하지만 느림
2. "최소값을 선택한다"라는 컨셉이 명확
- 버블 정렬(Bubble Sort)
원리
1. 옆에 있는 값과 비교해 더 큰 값을 뒤로 보내는 방식 (거품이 위로 올라가는 것처럼 정렬됨)
시각화 (글 형태)
[5, 3, 8, 4, 2]
→5와 3 비교 →교환
→3과 8 비교 →유지
→반복....
코드 예제(C언어)
void bubble_sort(int arr[], int n) {
int i, j, temp;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// swap
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
시간 복잡도
| 최선 / 평균 / 최악 / | O(N^2) |
특징
직관적이라 교육용으로 많이 사용됨
- 삽입 정렬(Insertion Sort)
원리
1.현재 원소를 알맞은 위치에 “삽입”하여 부분 배열을 유지
시각화 (글 형태)
[5 | 3, 8, 4, 2]
→ 3 삽입 → [3, 5 | 8, 4, 2]
→ 8 삽입 → [3, 5, 8 | 4, 2]
→ 4 삽입 → [3, 4, 5, 8 | 2]
...
코드 예제(C 언어)
void insertion_sort(int arr[], int n) {
int i, j, key;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
// key보다 큰 요소는 한 칸 뒤로 이동
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
시간 복잡도
| 최선 | O(N) |
| 평균 / 최악 | O(N^2) |
특징
1. 작은 데이터에 매우 효율적
2. 카드 정렬 방식과 동일
- 퀵 정렬(Quick Sort)
원리
1. pivot(기준)을 하나 선택
2. pivot보다 작은 값은 왼쪽, 큰 값은 오른쪽
3. 동일 방식으로 재귀적으로 정렬
시각화 (글 형태)
pivot = 5
[3, 2, 1] + [5] + [8, 6, 7]
→ 왼쪽, 오른쪽을 각각 다시 퀵 정렬
예제 코드(C 언어)
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 마지막 요소를 pivot으로 선택
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quick_sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quick_sort(arr, low, pi - 1);
quick_sort(arr, pi + 1, high);
}
}
시간 복잡도
| 평균 | O(N log N) |
| 최악 | O(N^2) |
특징
1. 매우 빠르고, 실무에서도 자주 사용되는 핵심 정렬
정렬 알고리즘 비교 표
| 알고리즘 | 평균 속도 | 최악 속도 | 공간 복잡도 | 특징 |
| 선택 정렬 | O(N^2) | O(N^2) | O(1) | 구현 쉬움, 느림 |
| 버블 정렬 | O(N^2) | O(N^2) | O(1) | 가장 단순, 거의 사용 X |
| 삽입 정렬 | O(N^2) | O(N^2) | O(1) | 작은 입력에 효율, 거의 즉시 반영 |
| 퀵 정렬 | O(N log N) | O(N^2) | O(N log N) | 가장 빠른 정렬 중 하나 |
정렬 알고리즘은 단순한 것처럼 보이지만, 컴퓨터가 어떤 방식으로 데이터를 처리하는지를 이해하는 핵심 개념이다.
다음 글에서는 힙 정렬 / 병합 정렬 / 기수 정렬처럼 고급 정렬 알고리즘을 다룰 예정이다.