Quick Sort 알고리즘

Quick 정렬은 버블정렬과 함께, 가장 쉽게 응용할 수 있는 정렬기법이다. 평균적으로 O(n log n)번의 비교를 수행하며, 최악의 경우에 O(n^2)의 비교를 수행하도록 되어 있다.

정렬할 데이터가 이미 준비되어 있으며, 모든 데이터를 정렬해야 할경우 가장 빠른 수행속도를 보여주는 알고리즘으로 평가되고 있다.

소트효율

가장 비효율적인 '''버블소트'''는 O(N^2)이고, 퀵소트는 평균 O(NlogN)이다.
아무리 뛰어난 정렬 알고리즘(:12)을 개발한다고 하더라도, 데이터의 갯수가 N이면 O(NlogN)보다 더 좋을 수
없다는 것이 증명되어 있다.

즉 정렬알고리즘의 lower bound는 O(NlogN)이다.

단 최대값이 정해져 있는 데이터라면 counting 방식을 쓸수 있고 - counting sort, bucket sort, radix sort - 이 경우 O(n)이 보장될 것이다.

퀵정렬은 다음과 같은 방식으로 진행이 된다.

1. 주어진 데이터 목록에서 임의의 원소를 고른다. 이 원소를 피봇이라 한다.
   
2. 피봇을 기준으로 피봇의 앞에는 피봇보다 작은 숫자가 오도록 하고, 피봇 뒤에는 피봇보다 큰 원소가 오도록한다. 필요할 경우 피봇은 움지일 수 있다.
   

분할과정을 거치게 됨을 알 수 있다. 분할이 끝난뒤에 피봇은 더 이상 움직일 필요가 없이 그 자리에 고정된다. 흔히 분할정복알고리즘이라고 한다. 퀵소트는 분할정복방식을 쓰는 정렬알고리즘이라고 달리 부를 수 있을 것이다.

1. 1,2의 과정을 재귀수행한다. 한번의 피봇이 선택되어서 분할이 이루어질 때마다. 반드시 고정되는 값이 생성이 되므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
   
   

위의 이미지는 Quick Sort가 이루어지는 과정을 나타내고 있다. 좀더 쉬운 이해를 원한다면 Visual Sort문서를 보기 바란다.

위의 프로세스가 퀵소트 알고리즘의 핵심으로 머리속으로 이해했다면, 구현하는 것도 그리 어렵지 않을 것이다. 구현에도 몇가지 방법이 있는데, 그 중에서 별도의 버퍼를 필요로 하지 않는 내부분할 퀵소트가 널리 사용되고 있다. 이 방법은 정렬을 위한 임시버퍼를 필요로 하지 않으므로 메모리를 할당하고 유지하기 위한 비용을 고려할 필요가 없다는 장점이 있다.

다음은 C로 작성된 퀵정렬 알고리즘이다.

void quickSort(int numbers[], int array_size); 
void q_sort(int numbers[], int left, int right); 
 
void quickSort(int numbers[], int array_size) 
{ 
    q_sort(numbers, 0, array_size -1); 
} 
 
void q_sort(int numbers[], int left, int right) 
{ 
    int pivot, l_hold, r_hold; 
    l_hold = left; 
    r_hold = right; 
    pivot = numbers[left]; // 0번째 원소를 피봇으로 선택 
    while (left < right) 
    { 
        // 값이 선택한 피봇과 같거나 크다면, 이동할 필요가 없다 
        while ((numbers[right] >= pivot) && (left < right)) 
            right --; 
 
        // 그렇지 않고 값이 피봇보다 작다면, 
        // 피봇의 위치에 현재 값을 넣는다. 
        if (left != right) 
        { 
             numbers[left] = numbers[right]; 
        } 
        // 왼쪽부터 현재 위치까지 값을 읽어들이면서 
        // 피봇보다 큰 값이 있다면, 값을 이동한다. 
        while ((numbers[left] <= pivot) && (left < right)) 
            left ++; 
        if (left != right) 
        { 
             numbers[right] = numbers[left]; 
             right --; 
        } 
    } 
    // 모든 스캔이 끝났다면, 피봇값을 현재 위치에 입력한다. 
    // 이제 피봇을 기준으로 왼쪽에는 피봇보다 작거나 같은 값만 남았다. 
    numbers[left] = pivot; 
    pivot = left; 
    left = l_hold; 
    right = r_hold; 
 
    // 재귀호출을 수행한다. 
    if (left < pivot) 
        q_sort(numbers, left, pivot - 1); 
    if (right > pivot) 
        q_sort(numbers, pivot+1, right); 
} 
 
int main(int argc, char **argv) 
{ 
    int data[] = {3,7,8,5,2,1,9,5,4}; 
    int i; 
    quickSort(data, 9); 
    for (i =0; i < 9; i++) 
    { 
        printf("%d\n", data[i]); 
    } 
}