퀵 정렬

퀵 정렬이란?

말 그대로 빠른(quick) 정렬이다. 분할 정복법을 사용하는 알고리즘의 하나로 병합 정렬과 비슷하지만, 병합 정렬과는 다르게 리스트를 비균등하게 분할한다는 점이 다르다. 오름차순 정렬을 할 경우, 리스트에서 각자의 기준대로 pivot(기준 값)을 하나 선택하고, 그 기준 값보다 작은 요소들은 모두 pivot 왼쪽에, 더 큰 값은 모두 pivot의 오른쪽에 배치하는 방법을 재귀적으로 계속 호출하는 방법이다.

과정

우선 매번 pivot값을 정하고, 그 값을 기준으로 데이터를 분류해야 한다. pivot값을 어떻게 설정하는 지에 따라 퀵 정렬의 성능은 달라지는데, 여기서는 항상 가장 왼쪽에 있는 값을 pivot값으로 정하겠다.

아래와 같이 정렬되지 않은 배열과 pivot값이 있다.

이제 이 pivot값을 제외한 배열에서 첫 번째 배열을 left로, 마지막 배열을 right로 잡고 분류 과정을 진행해 나간다.

이제부터 left를 오른쪽으로 계속 이동시킬건데, 결과적으로 left보다 왼쪽에 있는 값은 pivot값인 5 보다 작아야 한다. 즉 값을 하나씩 오른쪽으로 이동하면서, pivot 값인 5 보다 큰 숫자가 있다면 거기서 더이상 움직이지 않고 stop한다.

동시에 right도 왼쪽으로 움직이는데, left와는 반대로 pivot값보다 작은 숫자를 만나면 stop한다.

둘이 멈춘 상태라면 이 둘의 위치를 바꿔준다. 둘의 위치를 바꾼 아래 그림을 보면, pivot값인 5보다 작은 값들이 점점 왼쪽으로 모이고 있음을 알 수 있다. 이 과정을 계속 진행하다보면 정렬이 될것 같은 느낌이든다(즉, 5보다 큰 숫자는 배열의 뒷 쪽 쯤에, 5보다 작은 숫자는 배열의 앞쪽에 배치되게 된다).

한번더 진행해 보자. left를 오른쪽으로, right를 왼쪽으로 진행시키면서 아까와 같은 행위를 반복한다. 그런데 이번엔 조금 주의해야한다. right와 left의 상대적 위치가 바뀌었다. left가 왼쪽에, right가 오른쪽에 있어야 하는데 서로 자리가 뒤바껴있다. 바로 이 때가 한번의 분류를 끝마칠 때이다. right과 left가 있는 1 과 7 사이에 딱 5가 들어간다면? 그렇다면 5의 왼쪽에 있는 수는 모두 5보다 작을 것이며, 5의 오른쪽에는 모두 5보다 클것이다. 따라서 right 자리에 pivot을 넣고, 원래의 피봇자리인 첫 번째 자리에 right가 가르키고 있는 값 1을 주면 된다.

이로써 한번의 분류가 끝났다. 이제는 두개의 정렬되지 않은 배열이 생긴 셈이다. 즉, 그리고 이렇게 두개의 배열이 있는 것이고, 각각 독립적으로 위에서 했던 방법 그대로 적용하면 된다.

코드

def swap(x, i, j):
    x[i], x[j] = x[j], x[i]

def pivotFirst(x, lmark, rmark):
    pivot_val = x[lmark]
    pivot_idx = lmark
    while lmark <= rmark:
        while lmark <= rmark and x[lmark] <= pivot_val:
            lmark += 1
        while lmark <= rmark and x[rmark] >= pivot_val:
            rmark -= 1
        if lmark <= rmark:
            swap(x, lmark, rmark)
            lmark += 1
            rmark -= 1
    swap(x, pivot_idx, rmark)
    return rmark

def quickSort(x, pivotMethod=pivotFirst):
    def _qsort(x, first, last):
        if first < last:
            splitpoint = pivotMethod(x, first, last)
            _qsort(x, first, splitpoint-1)
            _qsort(x, splitpoint+1, last)
    _qsort(x, 0, len(x)-1)

여기 참조!

시간 복잡도

• 평균 : O(nlogn)
• 최악 : O(n^2)