[컴][알고리즘] Quicksort 퀵소트 설명

 

출처 : http://i5on9i.blogspot.kr/2013/04/quicksort.html

 

QuickSort

quicksort 의 전체적인 내용은 ref. 1 을 참고하자. 여기서는 ref.1 의 내용 중에서 in-place version , 그러니까 storage space 를 별로 사용하지 않는 방법에 대해서만 얘기할 것이다.

partition 의 역할은 partition 함수를 실행하면, pivot 값을 중심으로 pivot 보다 작은 녀석들을 모두 왼쪽으로 옮기면, 자동으로 오른쪽에는 pivot 보다 큰 녀석이 남게 된다.

이 상황에서 마지막으로 pivot 값을 옮겨 놓으면, pivot 의 왼쪽에 pivot 보다 작은 값들이 있게 되고, 오른쪽에 pivot 보다 큰 값이 있게 된다. 아래에서 좀 더 자세하게 얘기하기로 하자.

 

Partition

여기서는 pivot 보다 작거나 같은 값들을 swap 하기로 하자.

value <= pivot

 

5를 pivot 으로 선택했다.

먼저 pivot 을 가장 오른쪽으로 옮긴다.

2, 3, 4, 5, 7, 5, 3

2, 3, 4, 3, 7, 5, 5

왼쪽에서 부터 pivot 보다 작은지 검사하고, 작으면 왼쪽으로 옮긴다.(왼쪽으로 옮기는 것을 enqueue 하는 것처럼 생각하면 된다.)

2, 3, 4, 3, 7, 5, 5
2 3, 4, 3, 7, 5, 5
 
2, 3  4, 3, 7, 5, 5
 
2, 3, 4 , 3, 7, 5, 5
 
2, 3, 4, 3 , 7, 5, 5
 

그러다가 pivot 보다 큰 값이 나오면 아무 일도 하지 않고, 그 다음 값을 검사한다.

2, 3, 4, 3 , 7, 5, 5
2, 3, 4, 3 , 7, 5, 5
 
2, 3, 4, 3, 5 , 7, 5

이제 pivot 바로 전까지 검사를 마쳤으면, 마지막으로 pivot 을 왼쪽으로 옮긴다.

2, 3, 4, 3, 5, 5  , 7

그러면, pivot 이 가장 오른쪽에 있는 list 가 하나 만들어진 것이다.

이 녀석을 남아있는 list 의 앞쪽으로 합치면, pivot 왼쪽에는 pivot 보다 작거나 같은 값들이 모여 있게 되고, 오른쪽에는 pivot 보다 큰 값만 남게 된다.

이 때의 pivot 이 가진 index 값이 중요하다.

pivot 을 중심으로 왼쪽을 partition 을 하고, 오른쪽을 partition 한다.

계속 partition 을 하면서 pivot 을 중심으로 계속 왼쪽에는 작은 수, 오른쪽에는 큰 수를 넣으면, 결국 모든 부분이 정렬되게 된다.

 

Pseudocode

ref. 1 에 보면 pseudocode 를 볼 수 있다.

그리고, 아래에는 python 으로 짠 간단한 코드를 볼 수 있다. 이해를 위해서 swap 과 enqueue 는 같은 역할을 하지만 구분해 놨다.

def swap(input, tail, b) :

    tmp = input[tail]
    input[tail] = input[b]
    input[b] = tmp


    

def enqueue(input, tail, b) :

    tmp = input[tail]
    input[tail] = input[b]
    input[b] = tmp


    

def partition(input, left, right, pidx) :
    pivot = input[pidx]

    # swap(pidx, right)
    swap(input, pidx, right)

    tailIndex = left
    for i in range(left, right) :
        # enqueue value equal or less than pivot into left side queue
        if input[i] <= pivot :
            # swap(i, tailIndex)
            enqueue(input, i, tailIndex)
            tailIndex = tailIndex + 1
    enqueue(input, tailIndex, right)

    return tailIndex


def quicksort(input, left, right) :


    if left < right :
        # select and remove a pivot value from input
        pivotIdx = right/2

        pivotNewIdx = partition(input, left, right, pivotIdx)
        
        print pivotNewIdx, input[left:pivotNewIdx], input[pivotNewIdx+1:right+1]
        
        quicksort(input, left, pivotNewIdx - 1)
        quicksort(input, pivotNewIdx + 1, right)



if __name__ == '__main__':
    str = '2345753'
    left = 0
    right = len(str)-1
    quicksort(list(str), left, right)

 

Reference

1. http://en.wikipedia.org/wiki/Quicksort