정렬 알고리즘(Sorting Algorithms): 효율적인 데이터 정렬 방법
🔹 정렬 알고리즘이란?
1. 정렬 알고리즘(Sorting Algorithm)의 정의
정렬(Sorting)이란 주어진 데이터를 특정 순서(오름차순 또는 내림차순)로 정렬하는 작업입니다. 정렬 알고리즘은 데이터 검색, 탐색, 정렬된 출력 등이 필요한 다양한 시스템에서 필수적으로 사용됩니다.
✅ 정렬 알고리즘의 주요 특징:
- 시간 복잡도(Time Complexity): 알고리즘의 실행 속도를 결정하는 요소
- 공간 복잡도(Space Complexity): 추가적인 메모리 사용 여부
- 안정성(Stable Sort): 동일한 값의 상대적인 순서를 유지하는지 여부
- 비교 기반(Comparison-Based) vs. 비비교 기반(Non-Comparison-Based) 알고리즘
📌 정렬 알고리즘은 데이터의 크기와 정렬 상태에 따라 최적의 방법을 선택해야 합니다.
🔹 주요 정렬 알고리즘
1. 버블 정렬(Bubble Sort) - O(n²)
✅ 인접한 두 요소를 비교하여 교환하는 방식으로 정렬하는 알고리즘
✔️ 버블 정렬 예제 (Python):
def bubble_sort(arr):
n = len(arr)
for i in range(n-1):
for j in range(n-1-i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
arr = [64, 25, 12, 22, 11]
print(bubble_sort(arr))📌 버블 정렬은 구현이 쉽지만, 성능이 낮아 대규모 데이터 정렬에는 적합하지 않습니다.
2. 선택 정렬(Selection Sort) - O(n²)
✅ 가장 작은 요소를 찾아 첫 번째 요소와 교환하는 방식으로 정렬하는 알고리즘
✔️ 선택 정렬 예제 (Python):
def selection_sort(arr):
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
arr = [64, 25, 12, 22, 11]
print(selection_sort(arr))📌 선택 정렬은 비교 횟수가 많아 성능이 좋지 않지만, 추가 메모리 사용이 없습니다.
3. 삽입 정렬(Insertion Sort) - O(n²)
✅ 데이터를 하나씩 정렬된 부분에 삽입하는 방식으로 정렬하는 알고리즘
✔️ 삽입 정렬 예제 (Python):
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
arr = [64, 25, 12, 22, 11]
print(insertion_sort(arr))📌 삽입 정렬은 작은 데이터셋이나 거의 정렬된 데이터에서 효율적입니다.
4. 병합 정렬(Merge Sort) - O(n log n)
✅ 분할 정복(Divide & Conquer) 방식으로 배열을 분할하고 병합하여 정렬하는 알고리즘
✔️ 병합 정렬 예제 (Python):
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
merge_sort(left)
merge_sort(right)
i = j = k = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
while i < len(left):
arr[k] = left[i]
i += 1
k += 1
while j < len(right):
arr[k] = right[j]
j += 1
k += 1
return arr
arr = [64, 25, 12, 22, 11]
print(merge_sort(arr))📌 병합 정렬은 안정 정렬이며, 대량의 데이터를 정렬할 때 효율적입니다.
5. 퀵 정렬(Quick Sort) - O(n log n) (평균), O(n²) (최악)
✅ 피벗(Pivot)을 기준으로 작은 값과 큰 값을 분할하여 정렬하는 알고리즘
✔️ 퀵 정렬 예제 (Python):
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
arr = [64, 25, 12, 22, 11]
print(quick_sort(arr))📌 퀵 정렬은 평균적으로 매우 빠르지만, 최악의 경우 성능이 O(n²)까지 저하될 수 있습니다.
🔹 정렬 알고리즘 비교
| 정렬 알고리즘 | 최악 시간 복잡도 | 평균 시간 복잡도 | 공간 복잡도 | 안정 정렬 |
|---|---|---|---|---|
| 버블 정렬 | O(n²) | O(n²) | O(1) | O |
| 선택 정렬 | O(n²) | O(n²) | O(1) | X |
| 삽입 정렬 | O(n²) | O(n²) | O(1) | O |
| 병합 정렬 | O(n log n) | O(n log n) | O(n) | O |
| 퀵 정렬 | O(n²) | O(n log n) | O(log n) | X |
📌 정렬 알고리즘은 데이터 크기와 정렬 상태에 따라 적절한 방식을 선택하는 것이 중요합니다.
🚀 지금 바로 다양한 정렬 알고리즘을 연습해 보세요!