퀵 정렬 (Quick Sort)
목차
정렬 알고리즘의 꽃. 기준점(pivot)을 정하여 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right)으로 모으고, 각각을 재귀적으로 반복하는 정렬 알고리즘.
구현
def quick_sort(data):
if len(data) <= 1:
return data
left, right, pivot = list(), list(), list()
pivot.append(data[0])
for index in range(1, len(data)):
if pivot[0] < data[index]:
right.append(data[index])
else:
left.append(data[index])
return quick_sort(left) + pivot + quick_sort(right)시간 복잡도
| 경우 | 복잡도 |
|---|---|
| 평균 | O(n log n) |
| 최악 (pivot이 최대/최소일 때) | O(n²) |