[알고리듬] Array / 퀵소트 / python

🤔퀵소트란 ?

• 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬하는 비교 정렬에 속한다.
• 분할과 정복 알고리즘으로, 평균적으로 가장 빠른 수행 속도를 자랑하는 정렬방법이다.
  • 머지소트와 달리 퀵소트는 리스트를 비균등하게 분할한다.
• 분할과 정복 방법을 이용한다.
  • 문제를 해결하기 쉬운 작은 문제들로 나누고 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 방법이다.

 

😲퀵소트 알고리즘 진행 순서

• 리스트 안에 있는 한 요소를 선택한다. (랜덤으로 선택하는 방법, 가운데 인덱스를 선택하는 방법, 가장 오른쪽 인덱스를 선택하는 방법 등이 있다.) 이렇게 고른 원소를 pivot 이라고 한다.
• pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮겨지고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮겨진다.
• pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 나누고 위 과정을 반복한다.
• 리스트의 크기가 0이나 1이 될 떄까지 반복한다.

 

 

🔥파이썬 코드

N = int(input())
N_list = list(map(int, input().split()))
left = 0
right = N-1

def quick_sort(N_list, left, right):
    if left < right:
        idx = (left + right) // 2
        # 피봇은 리스트의 가운데 친구로 잡는다. 이것이 일반적으로 가장 빠르다.
        pivot = N_list[idx]
        # 피봇으로 선정한 친구와 리스트의 가장 오른쪽친구랑 자리를 바꿔준다.
        N_list[idx], N_list[right] = N_list[right], N_list[idx]

        # L, R 모두 리스트의 가장 첫 번째 인덱스로 우선 설정해준다.
        L = left
        R = left

        # R이 리스트를 넘어가기 전까지 while문
        while R <= right:
            # 만약 R인덱스의 요소가 pivot보다 작다면
            if N_list[R] < pivot:
                # L인덱스 요소와 R인덱스 요소를 바꿔주고
                N_list[L], N_list[R] = N_list[R], N_list[L]
                # R인덱스가 pivot보다 작을 때만 L 인덱스는 +1 해준다.
                L += 1
            # R인덱스는 항상 + 1 해준다.
            R += 1

        # while문 나오고 L인덱스의 위치가 파티셔닝을 할 기준이 될 인덱스다.
        p_idx = L

        # 피봇도 L인덱스의 요소와 바꿔주면서 자기 자리로 위치하게 설정해주고
        N_list[L], N_list[R-1] = N_list[R-1], N_list[L]

        # p_idx( 과거 L )을 기준으로 왼쪽 리스트와 오른쪽 리스트를 재귀호출한다.
        quick_sort(N_list, left, p_idx-1)
        quick_sort(N_list, p_idx+1, right)

quick_sort(N_list, left, right)

 

그림으로 표현하면 아래와 같은 느낌s

 

 

 

🌊퀵소트의 시간복잡도

결론부터 말하면 최악의 경우 O(N^2), 평균적으로 O(nlog₂n)을 가진다. 다른 정렬 알고리즘과 비교해서 가장 빠르다고 할 수 있다. 

 

최악의 경우를 살펴보면 예시로 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이라는 정렬이 있다고 치자. 이 때 pivot을 항상 정렬의 가장 오른쪽 인덱스 요소로 삼는다고 가정했을 때 

 

정렬중인 list 1 2 3 4 5 6 7 8 9 10 파티션 기준 인덱스 = 9
정렬중인 list 1 2 3 4 5 6 7 8 9 10 파티션 기준 인덱스 = 8
정렬중인 list 1 2 3 4 5 6 7 8 9 10 파티션 기준 인덱스 = 7
정렬중인 list 1 2 3 4 5 6 7 8 9 10 파티션 기준 인덱스 = 6
정렬중인 list 1 2 3 4 5 6 7 8 9 10 파티션 기준 인덱스 = 5
정렬중인 list 1 2 3 4 5 6 7 8 9 10 파티션 기준 인덱스 = 4
정렬중인 list 1 2 3 4 5 6 7 8 9 10 파티션 기준 인덱스 = 3
정렬중인 list 1 2 3 4 5 6 7 8 9 10 파티션 기준 인덱스 = 2
정렬중인 list 1 2 3 4 5 6 7 8 9 10 파티션 기준 인덱스 = 1

 

위와 같이 피봇이 array길이만큼 이동을 하고나서야 함수호출이 끝난다.

이 경우 리스트의 각 요소를 pivot과 비교하는 절차 O(n)과 pivot을 이동시키는 절차 O(n)을 곱해서 O(N^2)의 시간복잡도를 가지게 된다.

 

반대로 최선 or 일반적인 경우 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이라는 정렬이 있다고 치자. 이 때 pivot을 항상 정렬의 가장 중앙의 인덱스 요소로 삼는다고 가정했을 때 

 

정렬중인 list 1 2 3 4 6 7 8 9 5 10 파티션 기준 인덱스 = 9
정렬중인 list 1 2 3 4 6 7 8 9 5 10 파티션 기준 인덱스 = 4
정렬중인 list 1 3 2 4 6 7 8 9 5 10 파티션 기준 인덱스 = 3
정렬중인 list 1 3 2 4 6 7 8 9 5 10 파티션 기준 인덱스 = 1
정렬중인 list 1 3 2 4 6 8 5 9 7 10 파티션 기준 인덱스 = 5
정렬중인 list 1 3 2 4 6 8 5 9 7 10 파티션 기준 인덱스 = 7

 

요런 과정을 거치고 함수호출이 끝나게 된다.

이미 정렬된 리스트 내에서, 짝수냐 홀수냐에 따라 조금 다르겠지만 pivot을 적합한 친구로 계속 선택되기 때문에 전체 list를 반으로 잘라가며 요소가 1이하가 될 때 호출을 끝내는 횟수와 비슷하게 동작한다. 

이 경우 리스트의 각 요소를 pivot과 비교하는 절차 O(n)은 같지만 pivot을 이동시키는 절차가 O(log₂n)이 되므로 O(nlog₂n)의 시간복잡도를 갖게 된다.