기초 정렬 알고리즘: 버블 정렬, 선택 정렬, 삽입 정렬
· 7분 읽기
기초 정렬 알고리즘: 버블 정렬, 선택 정렬, 삽입 정렬
정렬은 컴퓨터 과학에서 가장 기본적이고 중요한 알고리즘 중 하나입니다. 데이터를 순서대로 나열하는 작업은 데이터베이스, 검색, 최적화 등 다양한 분야에서 필수적입니다. 이번 글에서는 가장 기초적인 세 가지 정렬 알고리즘을 자세히 알아보겠습니다.
1. 정렬 알고리즘의 기초 개념
정렬의 정의
주어진 데이터 집합을 특정 기준에 따라 순서대로 나열하는 과정입니다.
정렬 알고리즘 평가 기준
- 시간 복잡도: 얼마나 빠르게 정렬하는가?
- 공간 복잡도: 얼마나 적은 메모리를 사용하는가?
- 안정성: 같은 값의 상대적 순서를 유지하는가?
- 제자리 정렬: 추가 메모리를 사용하는가?
비교 기반 정렬의 하한
모든 비교 기반 정렬 알고리즘은 최악의 경우 **Ω(n log n)**의 시간 복잡도를 가집니다.
2. 버블 정렬 (Bubble Sort)
알고리즘 원리
인접한 두 요소를 비교하여 순서가 잘못되었으면 교환하는 방식입니다. 마치 물방울이 위로 올라가듯 큰 값들이 뒤쪽으로 이동합니다.
동작 과정
초기 배열: [5, 3, 8, 4, 2]
1회전: [3, 5, 8, 4, 2] → [3, 5, 8, 4, 2] → [3, 5, 4, 8, 2] → [3, 5, 4, 2, 8]
2회전: [3, 5, 4, 2, 8] → [3, 4, 5, 2, 8] → [3, 4, 2, 5, 8] → [3, 4, 2, 5, 8]
3회전: [3, 4, 2, 5, 8] → [3, 2, 4, 5, 8] → [3, 2, 4, 5, 8] → [3, 2, 4, 5, 8]
4회전: [2, 3, 4, 5, 8] → [2, 3, 4, 5, 8] → [2, 3, 4, 5, 8] → [2, 3, 4, 5, 8]Python 구현
def bubble_sort(arr):
"""
버블 정렬 구현
Args:
arr (list): 정렬할 배열
Returns:
list: 정렬된 배열
"""
n = len(arr)
# 모든 요소에 대해 반복
for i in range(n):
# 마지막 i개 요소는 이미 정렬되어 있음
for j in range(0, n - i - 1):
# 인접한 요소 비교 및 교환
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# 테스트
test_array = [64, 34, 25, 12, 22, 11, 90]
print("정렬 전:", test_array)
bubble_sort(test_array)
print("정렬 후:", test_array)C++ 구현
#include <iostream>
#include <vector>
void bubbleSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 요소 교환
std::swap(arr[j], arr[j + 1]);
}
}
}
}
int main() {
std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
std::cout << "정렬 전: ";
for (int num : arr) std::cout << num << " ";
std::cout << std::endl;
bubbleSort(arr);
std::cout << "정렬 후: ";
for (int num : arr) std::cout << num << " ";
std::cout << std::endl;
return 0;
}시간 복잡도 분석
- 최선: O(n) - 이미 정렬된 경우
- 최악: O(n²) - 역순으로 정렬된 경우
- 평균: O(n²)
공간 복잡도
- O(1) - 제자리 정렬
특징
- 안정성: 안정적 (같은 값의 순서 유지)
- 장점: 구현이 간단함, 추가 메모리 불필요
- 단점: 비효율적 (대용량 데이터에 부적합)
3. 선택 정렬 (Selection Sort)
알고리즘 원리
배열에서 최솟값을 찾아 맨 앞 요소와 교환하는 방식입니다. 마치 카드 게임에서 가장 작은 카드를 골라 제일 앞으로 옮기는 것과 같습니다.
동작 과정
초기 배열: [64, 25, 12, 22, 11]
1단계: 최솟값 11을 찾아 첫 번째 요소 64와 교환
[11, 25, 12, 22, 64]
2단계: 두 번째 이후 요소들 중 최솟값 12를 찾아 교환
[11, 12, 25, 22, 64]
3단계: 세 번째 이후 요소들 중 최솟값 22를 찾아 교환
[11, 12, 22, 25, 64]
4단계: 네 번째 이후 요소들 중 최솟값 25를 찾아 교환
[11, 12, 22, 25, 64]Python 구현
def selection_sort(arr):
"""
선택 정렬 구현
Args:
arr (list): 정렬할 배열
Returns:
list: 정렬된 배열
"""
n = len(arr)
for i in range(n):
# 현재 위치부터 끝까지 최솟값의 인덱스 찾기
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# 최솟값을 현재 위치로 이동
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# 테스트
test_array = [64, 25, 12, 22, 11]
print("정렬 전:", test_array)
selection_sort(test_array)
print("정렬 후:", test_array)시간 복잡도 분석
- 최선: O(n²)
- 최악: O(n²)
- 평균: O(n²)
공간 복잡도
- O(1) - 제자리 정렬
특징
- 안정성: 불안정적 (같은 값의 순서가 바뀔 수 있음)
- 장점: 교환 횟수가 적음 (최대 n-1번)
- 단점: 비교 횟수가 많음
4. 삽입 정렬 (Insertion Sort)
알고리즘 원리
카드 게임에서 손에 든 카드를 올바른 위치에 삽입하듯, 정렬된 부분과 비교하며 적절한 위치에 삽입합니다.
동작 과정
초기 배열: [12, 11, 13, 5, 6]
1단계: [12, 11, 13, 5, 6] → 11을 적절한 위치에 삽입
[11, 12, 13, 5, 6]
2단계: [11, 12, 13, 5, 6] → 13은 이미 올바른 위치
[11, 12, 13, 5, 6]
3단계: [11, 12, 13, 5, 6] → 5를 적절한 위치에 삽입
[5, 11, 12, 13, 6]
4단계: [5, 11, 12, 13, 6] → 6을 적절한 위치에 삽입
[5, 6, 11, 12, 13]Python 구현
def insertion_sort(arr):
"""
삽입 정렬 구현
Args:
arr (list): 정렬할 배열
Returns:
list: 정렬된 배열
"""
n = len(arr)
for i in range(1, n):
key = arr[i] # 현재 삽입할 요소
j = i - 1
# key보다 큰 요소들을 오른쪽으로 이동
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
# key를 올바른 위치에 삽입
arr[j + 1] = key
return arr
# 테스트
test_array = [12, 11, 13, 5, 6]
print("정렬 전:", test_array)
insertion_sort(test_array)
print("정렬 후:", test_array)시간 복잡도 분석
- 최선: O(n) - 이미 정렬된 경우
- 최악: O(n²) - 역순으로 정렬된 경우
- 평균: O(n²)
공간 복잡도
- O(1) - 제자리 정렬
특징
- 안정성: 안정적
- 장점: 이미 정렬된 데이터에 효율적, 온라인 정렬 가능
- 단점: 대용량 데이터에 비효율적
5. 세 알고리즘 비교
| 알고리즘 | 시간 복잡도 | 안정성 | 제자리 정렬 | 특징 |
|---|---|---|---|---|
| 버블 정렬 | O(n²) | ✅ | ✅ | 구현 간단 |
| 선택 정렬 | O(n²) | ❌ | ✅ | 교환 횟수 적음 |
| 삽입 정렬 | O(n²) | ✅ | ✅ | 정렬된 데이터에 효율적 |
성능 비교 그래프
입력 크기(n) 버블 선택 삽입
100 10000 10000 2500 (부분 정렬 시)
1000 100만 100만 25만
10000 1억 1억 2500만실제 사용 사례
- 삽입 정렬: 작은 데이터셋, 거의 정렬된 데이터
- 버블 정렬: 교육용, 간단한 구현이 필요할 때
- 선택 정렬: 교환이 비용이 많이 드는 경우 (예: 대용량 데이터)
6. 최적화 기법
버블 정렬 최적화
def optimized_bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# 교환이 없었다면 이미 정렬됨
if not swapped:
break
return arr삽입 정렬 최적화 (이진 검색 활용)
def binary_insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
# 이진 검색으로 삽입 위치 찾기
left, right = 0, i - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] > key:
right = mid - 1
else:
left = mid + 1
# 요소들을 오른쪽으로 이동
for j in range(i - 1, left - 1, -1):
arr[j + 1] = arr[j]
arr[left] = key
return arr7. 연습 문제
-
세 가지 정렬 알고리즘의 시간 복잡도를 비교하고, 어떤 상황에서 각각이 유용한지 설명하세요.
-
다음 배열을 각 정렬 알고리즘으로 정렬하는 과정을 단계별로 쓰세요:
[8, 3, 1, 7, 4, 2, 9, 5, 6] -
안정성이 중요한 이유는 무엇인가요? 실무에서 어떤 경우에 안정성이 필요한지 예를 들어 설명하세요.
-
삽입 정렬이 이미 거의 정렬된 데이터에 효율적인 이유를 설명하세요.
마무리
세 가지 기초 정렬 알고리즘의 원리와 구현 방법을 배웠습니다. 이 알고리즘들은 이해하기 쉽지만 대용량 데이터에는 비효율적입니다.
핵심 요약:
- 버블 정렬: 인접 요소 교환, 안정적, 구현 간단
- 선택 정렬: 최솟값 선택 후 교환, 불안정적, 교환 횟수 적음
- 삽입 정렬: 정렬된 부분에 삽입, 안정적, 부분 정렬에 효율적
다음 글에서는 검색 알고리즘에 대해 알아보겠습니다. 데이터를 찾는 효율적인 방법들을 배워보겠습니다!
추가 학습: 실제 데이터를 사용해서 세 알고리즘의 성능을 비교해보세요. 작은 데이터에서는 차이가 미미하지만, 데이터 크기가 커질수록 차이가 확연해집니다! 📊