정렬알고리즘 중 하나인 '퀵 정렬'을 파이썬으로 구현해 보았다
퀵 정렬은 평균 시간복잡도가 O(nlogn)으로 매우 빠르다
퀵 정렬 : https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC
def quickSort(arr,start,end):
pivot = arr[(start+end)//2]
prev_start = start # 다음 방에 인자로 넣어줄 시작 위치
prev_end = end # 다음 방에 인자로 넣어줄 끝나는 위치
while start <= end:
while arr[start] < pivot:
start += 1
while arr[end] > pivot:
end -= 1
if start <= end:
arr[start],arr[end] = arr[end],arr[start]
start += 1
end -= 1
if prev_start < start-1:
quickSort(arr,prev_start,start-1)
if start < prev_end:
quickSort(arr,start,prev_end)
array=[49,97,53,5,33,65,62,51]
quickSort(array,0,len(array)-1)
print(array)
보통 partition 함수를 만들어 구현해 놓은 경우를 많이 봤지만
하나의 함수로 해결하고 싶어서 prev_start 와 prev_end를 추가해줌으로써
구현이 되었다