Python Quicksort 알고리즘 가이드
Python의 퀵 정렬 알고리즘을 살펴보세요. 이 대화형 코딩 예제에서 피벗 선택, 분할 및 재귀에 대해 알아보세요.
개요
Quicksort는 매우 빠르고 널리 사용되는 정렬 알고리즘입니다. 병합 정렬과 마찬가지로 분할 정복 방식을 사용합니다. 그러나 퀵 정렬은 요소를 '제자리'로 정렬하여 메모리 효율성을 높입니다.
알고리즘은 목록에서 '피벗' 요소를 선택하여 작동합니다. 그런 다음 다른 요소를 두 개의 하위 배열(피벗보다 작은 배열과 피벗보다 큰 배열)로 분할합니다. 이 프로세스는 하위 배열에 재귀적으로 적용됩니다.
Quicksort의 최악의 복잡성은 O(n²)이지만 평균 런타임은 O(n log n)이며 일반적으로 캐시 누락이 적고 임시 배열 생성에 따른 오버헤드가 없기 때문에 실제로 병합 정렬보다 성능이 뛰어납니다.
코드 및 실행 출력
높은 가독성을 위해 목록 이해를 사용하는 간결한 재귀 빠른 정렬 스크립트입니다.
quicksort.py
에디터에서 사용해 보세요def quicksort(arr):
if len(arr) <= 1:
return arr
else:
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 quicksort(left) + middle + quicksort(right)
# Test list
data = [12, 4, 5, 6, 7, 3, 1, 15]
print("Original List:", data)
sorted_data = quicksort(data)
print("Sorted List: ", sorted_data)터미널 출력
Original List: [12, 4, 5, 6, 7, 3, 1, 15]
Sorted List: [1, 3, 4, 5, 6, 7, 12, 15]단계별 구현
- 메모리 공간을 최소한으로 유지해야 하는 시스템 정렬 루틴
- 표준 언어 라이브러리 프레임워크의 범용 정렬
- 분할 역학 및 재귀적 분할 정복에 대한 학문적 교육
자주 묻는 질문
Quicksort에서 O(n²)의 최악의 복잡성을 어떻게 피할 수 있습니까?
최악의 경우는 선택한 피벗이 반복적으로 가장 작은 요소 또는 가장 큰 요소일 때 발생합니다. 이를 완화하기 위해 개발자는 무작위 피벗 또는 "3개의 중앙값" 값을 선택하는 것과 같은 전략을 사용합니다.
퀵소트는 안정적인가요?
아니요, 표준 Quicksort는 불안정합니다. 분할하는 동안 요소는 긴 범위에 걸쳐 교환되므로 중복 요소의 상대적 순서가 변경될 수 있습니다.