[알고리즘/Algorithm] 퀵 소트(Quick Sort)

QuickSort

Quicksort는 Divide and Conquer 알고리즘으로, 어떤 원소를 기준점(Pivot)으로 고른 후 그 기준으로 어레이를 나누는 알고리즘이다. 우선 Psuedo Code로 간략하게 알고리즘에 대해 이해해보자.

퀵 소트의 Pseudo Code

Partition 부분의 Pseudo Code

우선 Partition의 목적은 A[p....i] 어레이는 모두 Pivot보다 작은 값으로. A[j...n] 어레이는 모두 Pivot보다 큰 값으로 만들고자 하는 것이다. 위 Psuedo Code를 하나하나 차례대로 뜯어보자.

우선 Pivot x를 A[p]값으로 설정한다. i는 p보다 하나 작은 값, j는 r보다 하나 큰 값으로 설정한다.  r은 partition할 어레이의 맨 마지막 부분이다. 이렇게 하면 Pivot P를 기준으로 P의 오른쪽 부분에서 스위칭이 일어나게 된다.

A[j]가 기준점 x보다 작아질때까지 반복하며 j를 감소시킨다.

A[i]가 기준점 x보다 커질때까지 반복하며 i를 증가시킨다.

이렇게 결정되어진 i, j값을 이용한다. 만약 j값이 i보다 크다면 i위치와 j위치의 어레이를 스왑한다.

더이상 Swapping이 불가능해진 경우 j값을 리턴한다. 그러고나서 이 j값에 Pivot을 삽입하면 된다.

 

위의 pseudo code를 바탕으로 퀵 정렬을 C언어로 구현해보았다.

#include <stdio.h>
#include <stdlib.h>
 
void Swap(int A[], int i, int j)
{
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
}
 
int Partition(int A[], int p, int r){
        int x = A[p];
        int i = p-1;
        int j = r+1;
        while(1){
                while(1){
                        j--;
                        if(A[j] <= x) break;
                }
                while(1){
                        i++;
                        if(A[i] >= x) break;
                }
                if( i < j){
                        Swap(A, i, j);
                }
                else{
                        return j;
                }
        }
}
 
void Quicksort(int A[], int p, int r){
        if(p < r)
        {
                int q = Partition(A, p, r);
                Quicksort(A,p,q);
                Quicksort(A,q+1,r);
        }
}

 

 Quick Sort와 Insertion Sort를 비교해보기 위해서 1Meg(1,048,576)개 Elements를 각각 정렬해보고 수행시간을 비교해보았다.

Insertion Sort 결과

Quick Sort 결과

동일한 어레이에 대해서 정렬을 수행했음에도 어마어마한 차이를 보인다.

 

Quick Sort의 경우 엄청나게 빠른 정렬 방식이지만 이미 정렬된 어레이에 대해서는 그만큼의 성능을 기대할 수 없다.

이를 어느정도 해결하기 위한 방법이 있다.

바로 기준점 Pivot을 변경하면 된다.

Improvement of Quick Sort Pseudo Code

위 Pseudo code를 바탕으로 C언어 코드의 Quicksort부분을 수정해보자.

void Quicksort(int A[], int p, int r){
        if(p < r)
        {
            int pivot = rand()%(p-r);
                Swap(A, p, pivot);
                int q = Partition(A, p, r);
                Quicksort(A,p,q);
                Quicksort(A,q+1,r);
        }
}

Improved Quick Sort

Quick Sort

정렬된 Array의 경우를 입력으로 해서 실험해 보았다.

그 결과 Improved Quick Sort를 수행했을 때 훨씬 빨랐다.

 

다음은 Quick Sort를 BST(Binary Tree)로 구현해 볼 것이다.