- Pivot(큰 값 작은 값을 교환할 때의 기준)을 사용 - Pivot이 이동된 경우 Pivot을 기준으로 좌 우를 별개로 나눠 교환 반복 - 가장 많이 사용되는 정렬 알고리즘, 대부분의 정렬 라이브러리의 근간
시간 복잡도 : O(NlogN) 최악의 경우 O(N^2) - 이미 정렬된 경우, 인덱스 n(n-1, n-2 ..._)부터 Pivot까지 공간 복잡도:O(N)
#파이썬이 지리는 형태
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array):
#리스트가 하나 이하의 원소가 남았을 때, 종료
if len(array) <= 1:
return array
pivot = array[0]
tail = array[1:0]
left_side = [x for x in tail if x <= pivot] #분할 중 왼쪽
right_side = [x for x in tail if x > pivot] #분할 중 오른쪽
return quick_sort(left_side) + [pivot] + quick_sort(right_side)
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end):
if start >= end: # 원소가 1개인 경우 종료
return
pivot = start
left = start + 1
right = end
while(left <= right):
# 피벗보다 큰 데이터를 찾을 때까지
while(left <= end and array[left] <= array[pivot]):
left += 1
# 피벗보다 작은 데이터를 찾을 때까지
while(right > start and array[right] >= array[pivot]):
right -= 1
if(left > right): # 엇갈렸다면
array[right], array[pivot] = array[pivot], array[right]
else: # 엇갈리지 않았다면
array[left], array[right] = array[right], array[left]
# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
quick_sort(array, start, right - 1)
quick_sort(array, right + 1, end)
quick_sort(array, 0, len(array) - 1)
