[Algorithm] 퀵 정렬(Quick Sort)에 대해 알아보자!

안녕하세요. 게임개발자 놀이터 입니다.

이번 포스팅에선 퀵 정렬에 대해 정리해보려고 해요.

퀵정렬 (Quick Sort)

퀵정렬은 '찰스 앤터니 리처드 호어(1962)'가 개발한 정렬 알고리즘 이라고 합니다.

퀵 정렬은 기준(pivot)을 선택하여 기준보다 작은 데이터를 왼쪽에 위치시키고, 큰 데이터는 오른쪽에 위치시킵니다.

이 과정이 끝나면 기준(pivot)이 된 요소는 정렬된 위치를 찾습니다. 결과적으로 기준보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽에 위치하게됩니다. 이러한 알고리즘을 pivot을 기준으로 왼쪽 데이터 그룹과 오른쪽 데이터 그룹에 재귀적으로 더이상 불가능 할때까지 반복합니다. (데이터 그룹의 갯수가 0 이거나 1개일때까지 반복)

반복이 종료되면 정렬된 데이터 그룹을 얻을 수 있습니다.

(출처 : 위키백과 퀵정렬)

정렬과정

임의의 데이터 배열을 가지고 정렬 해보겠습니다.

15 13 9 10 26 24 85

1. 먼저 Pivot을 설정합니다.

15 13 9 10 26 24 85

2. Pivot(15)를 기준으로 보다 작으면 왼쪽, 크면 오른쪽에 위치시켜 분할합니다

13 9 03 15 26 24 85

3. 좌 우 로 분할된 데이터로 다시 (1,2)의 과정을 실행합니다.

( 13 9 10 )   15   ( 26 24 85 )

( 13 9 10 )   15   ( 26 24 85 )

( 9 10 13 )   15   ( 26 24 85 )

( 9 10 )   13 15   ( 26 24 85 )

9 10 13 15   ( 26 24 85 )

9 10 13 15   ( 26 24 85 )
9 10 13 15   ( 24 26 85 )

9 10 13 15 24 26 85

정렬 완성!

예제 코드

2개의 함수와 재귀함수를 이용한 방법

void QuickSort(int arrays[], int left, int right)
{
    if(left<right)
    {
        int pivot = Partition(arrays,left,right);
        QuickSort(arrays, left, pivot-1);
        QuickSort(arrays, pivot+1, right);
    }
}
 
int Partition(int arrays[],int left, int right)
{
    int pivot = left;
    right = right +1;
 
    while(left<right)
    {
        do
        {
            ++left;
        }while(arrays[left] < arrays[pivot]);
 
        do
        {
            --right;
        }while(arrays[right] > arrays[pivot]);
 
        if(left<right)
        {
            int swap = arrays[left];
            arrays[left] = arrays[right];
            arrays[right] = swap;
        }
    }
 
    int swap = arrays[pivot];
    arrays[pivot] = arrays[right];
    arrays[right] = swap;
 
    return right;
}

1개의 재귀 함수를 이용한 방법

void QuickSort(int arrays[], int left, int right)
{
    int row = left;
    int high = right;
    int pivot = arrays[(left + right) / 2];
 
    while (row <= high) {
        while (arrays[row] < pivot)
            row++;
        while (arrays[high] > pivot)
            high--;
 
        if (row <= high) {
            int tmp = arrays[row];
            arrays[row] = arrays[high];
            arrays[high] = tmp;
            row++;
            high--;
        }
    };
 
    if (left < high)
        QuickSort(arrays, left, high);
 
    if (row < right)
        QuickSort(arrays, row, right);
}

알고리즘 분석

가장 평균의 상황에서의 시간복잡도가 알고리즘의 시간 복잡도라고 할 수 있다.

크게 2가지 상황을 추축할수있다.

1. 최고의 경우, 나누어지는 족족 마다 반씩 분할되는 경우.

2. 최악의 경우, 나누어지는 족족마다 1개와 나머지로 분할되는 경우.

우선 1번의 경우를 계산하면. 

횟수 = (2ⁿ - 1) + 2 x (2ⁿ-¹ - 1) ...

= ⁿ-¹Σ 2... 이거 수식을 어떻게 적어야 할지 모르겠다..

계산하면.. NLogN이 나온다.

2번의 경우는 N² 이 나온다.

나중에 수식을 제대로 추가할수있는 방법을 알게된다면.. 그때 수정 해야겠다.

쨋든 2번의 경우는 극단적인 상황이므로, 시간 복잡도는 1번의 경우를 사용해서 O(N logN) 이다.

감사합니다.

동영상 예시

출처 : 유투브동영상