[정렬] Quick Sort

퀵 정렬

 

분할정복을 이용한 정렬의 방법

합병정렬과 달리 분할의 과정에서 정렬이 일어난다!

 

배열에서 한 요소를 피봇으로 설정하고

그 요소보다 작은 수들은 왼쪽, 큰 수들은 오른쪽으로 나누는 것이다

간단하게 엑셀로 정렬과정을 나타내보았다

피봇은 어떤 것이 설정되어도 상관없으므로 첫번째 요소로 설정하고

5보다 작은 수들은 왼쪽으로 큰 수들은 오른쪽으로 보냈다

 

왼쪽 오른쪽으로 나눈후 나뉜 배열에서 또 다시 첫번째 요소를 피벗으로 하여 분할을 진행한다.

모든 배열의 길이가 1이 될때까지 분할을 진행하면 정렬이 완료된다.

나누는 과정에서 정렬이 이루어지니 합병과정에 별다른 로직처리를 하지 않아도 된다

평균적으로 nlogn 시간 복잡도를 가지고

순차적 또는 역순으로 정렬된 배열의 경우에는 최악의 시간복잡도 n^2을 보인다.

 

하지만 일반적인 경우 다른 정렬 알고리즘보다 빠른 수행시간을 보인다.

 

코드로 구현

def qsort(v : list) :
    if len(v) == 1 :
        return [v[0]]
    elif len(v) < 1 :
        return
    # else
    pivot = v[0]
    left = []
    right = []

    for i in range(1, len(v)) :
        if v[i] <= pivot:
            left.append(v[i])
        else :
            right.append(v[i])
    l = qsort(left)
    r = qsort(right)

    # merge
    result = []
    if l is not None :
        for i in l :
            result.append(i)
    result.append(pivot)
    if r is not None :
        for j in r :
            result.append(j)

    return result

분할과정을 재귀로 표현하여 나타냈다