[컴퓨터 알고리즘 기초] 7. 퀵 정렬 알고리즘

퀵(Quick) 정렬 알고리즘

퀵 정렬

- Divide - and - Conquer paradigm을 사용

partition을 이용

 

- Partitioning을 이용한 정렬 방법

파티션이라고 하는 것은 pivot element라고 하는 것을 통해 반으로 나누어 그 기준을 통해 작은 것을 왼쪽으로 큰 것은 오른쪽으로 이동시키는 것을 반복하는 것

- 퀵 정렬의 pseudo code

QUICKSORT(A,p,r)
if p<r
	q = PARTITION(A,p,r)
    QUICKSORT(A,p,q-1)
    QUICKSORT(A,q+1,r)

 

퀵 정렬의 수행 시간 분석

 - 밸런스 된 partitoning

각 하위 문제의 크기가 기존 문제의 크기의 절반 정도인 [n/2] 과 [n/2]-1가 되도록 나누어지는 경우

T(n) <=2T(n/2)+Θ(n) = O(nlogn)

 

 - 언밸런스 된 partitoning

- 최악의 경우

 O(n^2) 가 된다.

하지만 보통은 최악의 경우는 없기 때문에 평균인 O(nlogn) 이라고 생각하면 된다.

 

# 가장 일반적인 퀵 정렬
def quick_sort(array, start, end):
    if start >= end: return # 원소가 1개인 경우
    pivot = start # 피벗은 첫 요소
    left, right = start + 1, end
    
    while left <= right:
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while left <= end and array[left] <= array[pivot]:
            left += 1
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while right > start and array[right] >= array[pivot]:
            right -= 1
        if left > right: # 엇갈린 경우
            array[right], array[pivot] = array[pivot], array[right]
        else: # 엇갈리지 않은 경우
            array[right], array[left] = array[left], array[right]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)