QuickSort

평균적으로 가장 빠르다는 QuickSort!!

사실 좀 많이 실망했다. 결과를 먼저 말하자면 랜덤 배열일 경우 shellsort보다 5배 정도 빠르다지만 

순열이나 역순일 경우 시간측정이 무의미 할 정도로 오래 걸렸다.(1억개의 배열 기준)

물론 퀵솔트의 원리를 알고 최악의 경우 O(n^2)인 것을 생각해보면 당연하다고 할 수 있으나 그래도 기대했던 만큼의 속도가 나오지 않았다.

stl의 qsort는 quicksort만으로 이루어진 것은 아닌 듯 하다. 

원리

1. 피벗(pivot)이라는 값을 기준으로 더 큰 수는 pivot의 오른쪽 작은 값은 왼쪽으로 정렬시킨다.

2. 정렬이 완료되었으면 피벗을 기준으로 두개의 배열로 나눈다.

3. 나누어진 배열을 다시 1번 부터 재귀적으로 반복한다.

특징

1. 랜덤배열에서 빠른 정렬 속도를 보인다.

2. 피벗(pivot)을 선정하는 방법에 따라 속도가 달라진다.

3. 순열이나 역순의 경우 매우 느린 속도를 보인다.

4. 재귀함수 기반으로 구현시 복잡하게 생각될 수 있다.

연산시간

1. 평균적인 경우(랜덤) : O(n log n)

2. 최악의 경우 :   = n(n-1) / 2 

3. O표기법으로는 O(n^2)이 된다.

코드

// QUICKSORT_ver1
 
 
void q_sort(int numbers[], int left, int right)
{
    int pivot, l_hold, r_hold;
    l_hold = left;
    r_hold = right;
    
    pivot = numbers[left]; // 가장 왼쪽원소를 피봇으로 선택
    while (left < right)
    {
        // 값이 선택한 피봇과 같거나 크다면, 이동할 필요가 없다
        while ((numbers[right] >= pivot) && (left < right))
            right --;
 
        // 그렇지 않고 값이 피봇보다 작다면,
        // left 위치에 현재 값을 넣는다.
        if (left != right)
        {
            numbers[left] = numbers[right];
        }
 
        // left부터 right까지 값을 읽어들이면서
        // 피봇보다 큰 값이 있다면, left값을 right로 이동한다.
        while ((numbers[left] <= pivot) && (left < right))
            left ++;
 
        if (left != right)
        {
            numbers[right] = numbers[left];
            right --;
        }
    }
 
    // 모든 스캔이 끝났다면, 피봇값을 현재 left위치에 입력한다.
    // 이제 피봇을 기준으로 왼쪽에는 피봇보다 작거나 같은 값만 남았다.
    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);
}
void QuickSort(int numbers[], int array_size)
{
    q_sort(numbers, 0, array_size -1);
}
int const MAX = 5;
int g_arr[MAX] = {0, };
int main()
{
    printf("========정렬전========\n");
    //AscendingNumber(g_arr, MAX);     // 순열 배열 생성
    //DescendingNumber(g_arr, MAX);    // 역순 배열 생성
    RandomNumber(g_arr, MAX);          // 랜덤 배열 생성
    
    PrintNumber(g_arr, MAX);           // 배열 출력
    printf("\n");
    clock_t start = clock();           // 시작 시간
    QuickSort(g_arr, MAX);             // ShellSort
    clock_t end = clock();             // 끝 시간
    
    printf("========정렬후========\n");
    PrintNumber(g_arr, MAX);           // 배열 출력
    printf("\nTime : %f\n", ((double)(end-start)) / CLOCKS_PER_SEC);
}

결과

시간

시간은 MAX 값 100,000 과  100,000,000으로 기준을 나누어 측정하였다.

요소 수 :           100,000               100,000,000   

랜덤 배열 :         0.017                     23
역순 배열 :         12.89               너무 오래걸려서 측정 불가
순열 배열 :         13.21               너무 오래걸려서 측정 불가

결론

[QuickSort_ver1]의 경우 일반적인 방법으로 pivot설정을 가장 왼쪽 요소로 하였다.

시간측정에서 보여지듯이 랜덤배열의 경우 매우 빠른 속도를 보여주지만 순차배열이나 역순배열의 경우 매우 오랜 시간이 걸렸다. 

그 이유는 이후에 [피벗설정에 따른 퀵정렬의 속도] 같은 포스트를 통해 이야기 하도록 하겠다.