[Quick Sort] python 퀵정렬

# pivot보다 작은그룹, 큰그룹 분리됨!
def partiton(arr,start,end):

    pivot = arr[(start+end)//2]

    while start <= end:
        while arr[start] < pivot : start += 1 #pivot보다 작은 값은 건너뛰고 큰 값일 경우 멈춘다. (이따 swap할거야)
        while arr[end] > pivot : end -= 1 #pivot보다 큰 값은 건너뛰고 작은 값일 경우 멈춘다. (이따 swap할거야)

        if start <= end :
            arr[start],arr[end] = arr[end],arr[start]
            start += 1
            end -= 1

    return start #pivot보다 큰 그룹의 첫 번째 idx

def quickSort(arr,start,end):

    part2 = partiton(arr,start,end) #pivot보다 큰 그룹의 첫 번째 idx 반환

    if start < part2-1 : # 작은 그룹에 있는 값 개수가 1개가 될 때까지 퀵소트
        quickSort(arr,start,part2-1)
    if part2 < end : # 큰 그룹에 있는 값 개수가 1개가 될 때까지 퀵소트
        quickSort(arr,part2,end)


if __name__ == '__main__':
    arr = [5,3,1,9,3]
    quickSort(arr,0,len(arr)-1)
    print(arr)

 

시간복잡도 O(N^2)

• 빅오표기법은 최악의 경우로 표기한다. 위 코드는 pivot이 가장 크거나 가장 작은 수가 계속 선택될 때가 최악의 경우이다.
• 예를 들어, [1,2,3,4,5,6,7,8] 배열이 있는데 맨 왼쪽값을 pivot으로 한다고 해보자. 맨 처음 pivot이 1이다. 그럼 1 / 2,3,4,5,6,7,8 로 분류된다. 그 다음은 pivot이 2다. 2 / 3,4,5,6,7,8 로 분류된다. 이런 식이면 N번 기준으로 (pivot) N개의 원소를 탐색한다. 그러니 시간복잡도가 N^2이다. 

 

평균적으로는 O(NlogN) : N번씩 쪼개면서 O(N) -> 탐색할 데이터는 반씩 줄어든다 O(logN)

 

공간복잡도 O(1)

• 추가 공간이 필요 없다.

 

아주 깔끔한 설명 영상을 참고했다.