정렬은 데이터를 정해진 순서에 맞게 배열하는 과정으로, 많은 알고리즘이 존재합니다. 그중에서 버블 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬은 기본부터 고급까지 다양한 문제에서 사용됩니다. 이번 포스트에서는 이 네 가지 정렬 알고리즘의 작동 원리와 차이점을 비교해보겠습니다.
1. 버블 정렬 (Bubble Sort)
1) 알고리즘 설명
• 인접한 두 요소를 비교하여, 순서가 잘못된 경우 서로 교환합니다.
• 가장 큰 값이 매번 오른쪽 끝으로 “거품처럼 올라가는” 방식입니다.
2) 특징
• 시간 복잡도:
• 최선: O(n) (이미 정렬된 경우).
• 평균 및 최악: O(n2).
• 공간 복잡도: O(1) (제자리 정렬, 추가 메모리 필요 없음).
• 장점: 구현이 간단함.
• 단점: 데이터 크기가 클 경우 비효율적.
3) Python 코드
def bubble_sort(arr):
n = len(arr)
for i in range(n):
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
# 실행 예시
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
2. 삽입 정렬 (Insertion Sort)
1) 알고리즘 설명
• 배열의 각 요소를 정렬된 부분 배열에 삽입하여 정렬을 확장합니다.
• 카드를 한 장씩 정렬하는 방식과 유사합니다.
2) 특징
• 시간 복잡도:
• 최선: O(n) (이미 정렬된 경우).
• 평균 및 최악: O(n2).
• 공간 복잡도: O(1) (제자리 정렬).
• 장점: 작은 배열이나 거의 정렬된 데이터에서 효율적.
• 단점: 데이터 크기가 클 경우 비효율적.
3) 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
# 실행 예시
print(insertion_sort([64, 34, 25, 12, 22, 11, 90]))
3. 퀵 정렬 (Quick Sort)
1) 알고리즘 설명
• 분할 정복 알고리즘의 일종으로, 배열을 피벗(pivot)을 기준으로 나누고, 각 부분 배열을 재귀적으로 정렬합니다.
2) 특징
• 시간 복잡도:
• 최선 및 평균: O(n log n).
• 최악: O(n2) (이미 정렬된 경우 등).
• 공간 복잡도: O(log n) (재귀 호출 스택).
• 장점: 평균적으로 매우 빠르며, 대부분의 경우 적합.
• 단점: 최악의 경우 성능 저하.
3) 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)
# 실행 예시
print(quick_sort([64, 34, 25, 12, 22, 11, 90]))
4. 병합 정렬 (Merge Sort)
1) 알고리즘 설명
• 분할 정복 알고리즘의 일종으로, 배열을 반으로 나누어 각각 정렬한 후 병합합니다.
2) 특징
• 시간 복잡도:
• 최선, 평균, 최악: O(n log n).
• 공간 복잡도: O(n) (추가 메모리 필요).
• 장점: 안정적이며, 큰 데이터나 외부 정렬에 적합.
• 단점: 추가 메모리를 사용하므로 메모리 제약이 있는 경우 비효율적.
3) Python 코드
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# 실행 예시
print(merge_sort([64, 34, 25, 12, 22, 11, 90]))
'컴퓨터과학' 카테고리의 다른 글
[그래프 탐색: DFS와 BFS] 자료구조 탐색의 핵심 이해하기 (0) | 2025.01.07 |
---|---|
[이진 탐색과 선형 탐색] 효율적인 데이터 탐색의 기본 (0) | 2025.01.07 |
[시간 복잡도를 이해하는 법] 효율적인 알고리즘을 위한 첫걸음 (0) | 2025.01.07 |
[딕셔너리와 맵의 차이점] 자료구조의 구현방식 살펴보기 (0) | 2025.01.07 |
[우선순위 큐와 힙] 효율적인 데이터 처리의 핵심! (0) | 2025.01.07 |