퀵 정렬

정렬알고리즘 중 하나인 '퀵 정렬'을 파이썬으로 구현해 보았다
퀵 정렬은 평균 시간복잡도가 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를 추가해줌으로써
구현이 되었다