Python 병합 정렬 알고리즘 튜토리얼
Python에서 병합 정렬을 구현하는 방법을 알아보세요. Divide and Conquer 정렬 전략의 대화형 단계별 예입니다.
개요
병합 정렬은 분할 정복 전략을 활용하는 매우 효율적인 정렬 알고리즘입니다. 정렬되지 않은 목록을 더 작은 하위 목록으로 나누고 해당 하위 목록을 정렬한 다음 다시 병합합니다.
알고리즘은 단일 요소 하위 배열에 도달할 때까지 배열을 반복적으로 절반으로 분할합니다. 그런 다음 각 측면의 요소를 비교하고 정렬된 순서로 배치하여 정렬된 하위 배열을 병합합니다. 이는 최적의 시간 복잡도를 보장합니다.
초기 배열이 정렬되었는지, 역방향인지 또는 완전히 무작위인지에 관계없이 병합 정렬은 O(n log n) 시간 내에 실행됩니다. 그러나 병합 단계에서 하위 목록을 보관하려면 O(n)의 추가 공간이 필요합니다.
코드 및 실행 출력
Python에서 병합 정렬 알고리즘의 표준 재귀 구현입니다.
merge_sort.py
에디터에서 사용해 보세요def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = merge_sort(arr[:mid])
right_half = merge_sort(arr[mid:])
return merge(left_half, right_half)
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
# Test dataset
data = [38, 27, 43, 3, 9, 82, 10]
print("Original List:", data)
sorted_data = merge_sort(data)
print("Sorted List: ", sorted_data)터미널 출력
Original List: [38, 27, 43, 3, 9, 82, 10]
Sorted List: [3, 9, 10, 27, 38, 43, 82]단계별 구현
- 복사 없이 쉽게 병합할 수 있는 노드 구조의 연결 목록 정렬
- 시스템 RAM에 완전히 맞지 않는 파일에 대한 외부 정렬 루틴
- 일치하는 키가 원래 순서를 유지해야 하는 안정적인 정렬 애플리케이션
자주 묻는 질문
병합 정렬(Merge Sort)은 안정적인 정렬 알고리즘인가요?
예, 병합 정렬은 안정적입니다. 동일한 요소를 비교할 때 원래 상대 위치를 유지하면서 왼쪽(원래 첫 번째) 하위 배열의 요소가 먼저 배치됩니다.
Python이 순수 병합 정렬 대신 Timsort를 사용하는 이유는 무엇입니까?
Python의 내장 `sorted()`는 병합 정렬과 삽입 정렬을 결합한 하이브리드 알고리즘인 Timsort를 사용합니다. 이미 정렬된 하위 세그먼트를 식별하여 실제 데이터 패턴을 최적화하고 순수 병합 정렬보다 빠르게 렌더링합니다.