arr = [5,7,9,0,3,1,6,2,4,8]
def quick_sort(arr, start, end):
if start >= end: #원소가 1개인 경우 종료
return
# 시작점, 끝점과 별개로 이동할 때 필요하므로 사용
pivot = start
left = start + 1
right = end
# 엇갈릴 때까지 반복
while left <= right:
# (->) 왼쪽이 마지막 인덱스 전까지 & 피벗보다 큰 데이터를 찾을 때까지 반복
while left<=end and arr[left] <= arr[pivot]: # = 작으면 패스
left += 1
# (<-) 오른쪽이 맨앞 인덱스 전까지 & 피벗보다 작은 데이터를 찾을 때까지 반복
while start < right and arr[pivot] <= arr[right]: # = 크면 패스
right -= 1
# 엇갈렸어 ~> 피벗과 작은값 swap
if right < left:
arr[pivot], arr[right] = arr[right], arr[pivot] # 값을 바꾸는거 (idx 그대로!)
# 아니야 ~> 둘이 swap
else:
arr[left], arr[right] = arr[right], arr[left]
# Swap된 Right를 기준으로 Recursive하게 수행
quick_sort(arr, start, right-1) # 왼쪽 수행
quick_sort(arr, right+1, end) # 오른쪽 수행
quick_sort(arr, 0, len(arr)-1) # 정렬할것, 시작, 끝
print(arr)
''' 간단 버전 - 파이썬 '''
arr = [5,7,9,0,3,1,6,2,4,8]
def quick_sort(arr):
#원소가 1개인 경우 종료
if len(arr) <= 1:
return arr
pivot = arr[0] # 피벗은 보통 첫 번째 원소
tail = arr[1:] # 피벗을 제외한 나머지 리스트
left_side = [x for x in tail if x <= pivot] # 피벗보다 작은 것만 왼쪽에 모아(정렬되진 않음)
right_side = [x for x in tail if x > pivot] # 피벗보다 큰 것만 오른쪽에 모아(정렬되진 않음)
# 피벗의 위치만 확정이고, 작은 < 피벗 < 큰 순서의 배열로 Recursive
return quick_sort(left_side) + [pivot] + quick_sort(right_side)
print(quick_sort(arr))