[정렬] 5. 퀵 정렬

퀵 정렬

: 특정 기준 원소를 중심으로, 기준 원소보다 작은 것들은 기준의 왼쪽으로, 기준 원소보다 큰 것들을 기준의 오른쪽으로 정렬 + 재귀적으로 분할 정복 기법 사용.

가장 널리 쓰이는 정렬 알고리즘이기도 하다.

 

핵심 원리를 쉽게 이해할 수 있는 Python 코드

 

def quicksort(L):
    if(len(L) == 1) or (len(L) == 0):
        return L
    
    pivot = L[0]
    left = []
    right = []
    
    for x in L[1:]:
        if (x < pivot):
            left.append(x)
        else:
            right.append(x)
    
    return quicksort(left) + [pivot] + quicksort(right)

 

 

 

위의 코드는 기준 점을 주어진 배열의 0번째 인덱스, 즉 가장 첫번째 원소를 기준으로 삼고,

해당 기준 원소보다 작은 값은 left에, 해당 기준 원소보다 큰 값은 right에 저장한 후, 재귀적으로 함수를 진행하고 있다.

 

위의 코드는 이해하기 쉽지만, 메모리 사용량을 고려하지 않은 코드이다.

left와 right 포인터 2개를 이용해 효율적으로 퀵 정렬을 수행하는 Python Code를 참고해보자.

이해가 안된다면 그 아래 한 단계 한 단계 어떻게 진행되는지 직접 손으로 써놓았으니 참고하면 도움이 많이 될 것이다.

 

 

 

from typing import List

def quickSort(data: List[int], left: int, right: int):
    if(left >= right):
        return
    
    pivot = left # 기준값
    pl = left + 1 # pointer_left
    pr = right # pointer_right
    
    while(pl <= pr):
    	# pl번째 값이 기준값보다 큰 값이 나올 때까지 pl을 한 칸씩 오른쪽으로 이동
        while(pl <= right and data[pl] <= data[pivot]):
            pl += 1
        
        # pr번째 값이 기준값보다 작은 값이 나올 때까지 pr을 한 칸씩 왼쪽으로 이동    
        while(pr > left and data[pr] >= data[pivot]):
            pr -= 1
        
        # pl와 pr가 엇갈렸다면 기준값과 pr 번째 값을 swap
        if(pl > pr):
            data[pr], data[pivot] = data[pivot], data[pr]
        
        # pl 번째 값과 pr 번째 값을 swap, pl과 pr은 그대로 있음. 값을 변경!
        else:
            data[pl], data[pr] = data[pr], data[pl]
    	
        # 재귀적으로 기준 값을 기준으로 왼쪽 리스트와, 오른쪽 리스트를 정렬한다.
        quickSort(data, left, pr-1)
        quickSort(data, pr+1, right)
    
    return data

 

 

 

 

[3, 7, 8, 1, 5, 9, 6, 10, 2, 4] 를 퀵 정렬하는 Step by Step을 잘 따라와보자

 

 

 

퀵 정렬

 

시간 복잡도

 

평균: O(nlogn)

 

가장 좋은 경우: 기준의 왼쪽, 오른쪽에 같은 수의 원소가 이동할 때

T(n) = 2*T(n/2) + n

T(n) = O(nlogn)

 

가장 나쁜 경우: 기준의 왼쪽 또는 오른쪽 한 쪽으로만 원소가 쏠림

T(n) = T(n-1) + n

T(n) = O(n^2)

 

 

퀵 정렬의 시간 복잡도가 O(n log n)인 이유를 이해하려면 우선 퀵 정렬의 작동 원리와 분할-정복(divide-and-conquer) 전략에 대해 이해해야 합니다.

퀵 정렬은 먼저 리스트를 피벗을 기준으로 두 개의 작은 리스트로 분할합니다. 이를 분할 단계라고 부릅니다. 이 과정은 O(n) 시간이 소요되며, n은 리스트의 크기입니다. 왜냐하면 리스트의 모든 요소를 한 번씩만 검사하면 됩니다.

이후 각 하위 리스트에 대해 퀵 정렬을 재귀적으로 수행합니다. 이것이 바로 분할-정복 전략의 핵심입니다.

재귀 호출의 깊이는 피벗의 선택에 따라 결정되며, 이는 최선의 경우에는 log n이 됩니다. 최선의 경우는 각 단계에서 리스트가 두 동일한 크기의 하위 리스트로 분할되는 경우입니다.

따라서, 각 단계에서 O(n)의 작업을 수행하고 이를 log n 단계에 걸쳐 수행하므로, 퀵 정렬의 시간 복잡도는 O(n log n)이 됩니다.

단, 이것은 최선의 경우나 평균적인 경우의 시간 복잡도입니다. 최악의 경우에는 퀵 정렬의 시간 복잡도는 O(n^2)이 됩니다. 이는 각 분할 단계에서 하나의 하위 리스트가 빈 리스트가 되고, 다른 하위 리스트에 모든 요소가 포함되는 경우입니다. 이런 경우, 퀵 정렬은 기본적으로 버블 정렬이나 삽입 정렬과 같은 시간 복잡도를 가지게 됩니다. 그러나 이러한 최악의 경우는 일반적으로 피벗 선택 전략에 따라 크게 피해갈 수 있습니다.