[알고리즘] - 퀵 정렬(Quick sort) #6

드디어 고급 정렬에 들어왔습니다.

이번에는 고급 정렬 알고리즘 중 하나인 퀵 정렬에 알아보도록 하겠습니다.

취업을 위해 알고리즘 문제를 풀게 되는데, 정렬은 이러한 문제를 푸는 데 많이 사용됩니다.

저도 문제를 풀다가 정렬을 해야할 경우 퀵 정렬을 많이 사용하곤 합니다. (왜냐하면 이름처럼 빠르기 때문이죠!)

그럼 이제부터 본격적으로 퀵 정렬에 파헤쳐 보도록 하겠씁니다.

퀵 정렬(Quick sort) - 불안정 정렬(Unstable sort)

퀵 정렬은 전체를 분할 중심보다 작은 구간, 큰 구간 으로 나누는 작업을 재귀적으로 수행하여 정렬하는 알고리즘입니다.

즉, 분할 정복 기법을 활용하는 방법입니다.

동작 하는 과정은 다음과 같습니다.

1) 분할 중심(Pivot)값 을 정합니다.

(분할 중심을 정하는 방법은 여러 가지가 있는데, 저는 마지막 원소를 분할 기준으로 정하는 방법을 사용하도록 하겠습니다.)

2) 주어진 데이터 구간을 분할 중심을 기준으로 대소 관계에 따라 두 구간으로 나눕니다.

3) 분할된 구간 중 기준 값보다 큰 구간의 첫 번째 값과 분할 중심 값을 교환합니다.

4) 나누어진 두 구간 각각에 대해서 1~3 번 과정을 반복(혹은 재귀적)으로 수행합니다.

이렇게 나누고 정렬하는 작업을 분할할 공간이 없을 때 까지 진행하면 정렬은 끝입니다!

 

소스 코드

#include <cstdio>
#define SWAP(x,y,temp) ((temp)=(x),(x)=(y),(y)=(temp)) 
 
//분할
int partion(int * a, int left, int right) {
    //마지막 값을 분할 기준으로 설정
    int pivotValue = a[right];
    int temp;
    int i = left;
    //주어진 구간을 탐색하며 두 구간으로 분리
    for (int j = left; j < right; j++) {
        if (a[j] < pivotValue) {
            SWAP(a[j], a[i], temp);
            i++;
        }
    }
    //작은 구간과 큰 구간 사이에 분할기준 삽입
    SWAP(a[i], a[right], temp);
    return i;
}
 
//퀵 정렬
void quicksort(int * a, int left, int right) {
    int newPivotIndex;
    if (right > left) {
 
        //분할의 결과로 a배열은 pivot을 기준으로 좌측에는 작은 값 우측에는 큰 값이 위치
        newPivotIndex = partion(a, left, right);
 
        //작은 구간에 대해서 재귀적으로 퀵 정렬 진행
        quicksort(a, left, newPivotIndex - 1);
 
        //큰 구간에 대해서 재귀적으로 퀵 정렬 진행
        quicksort(a, newPivotIndex + 1, right);
    }
}
int main() {
    int a[7] = { 7,3,2,1,5,4,6 };
 
    quicksort(a, 0, 6);
 
    for (int i = 0; i < 7; i++)
        printf("%d ", a[i]);
 
    return 0;
}

배열 a : 정렬하고자 하는 데이터 원본 입니다.

Line 11 - 16 : 분할 중심을 기준으로 작은 구간과 큰 구간으로 분리합니다. ( 2) 에 해당하는 과정)

Line 18 : 큰 구간의 첫 번째 값과 분할 중심을 교환합니다. ( 3) 에 해당하는 과정)

Line 19 : 분할 중심의 Index 값을 반환합니다.

Line 28 : 주어진 배열에 대해서 구간을 분리하는 Partion 함수를 호출하고 분할 중심의 Index 값을 구합니다.

Line 31 : 작은 구간에 대해서 재귀적으로 수행합니다.

Line 34 : 큰 구간에 대해서 재귀적으로 수행합니다.

시간 복잡도

우선, 앞서 설명했던 알고리즘 들과 같이 최악의 경우를 고려한 시간 복잡도를 말씀 드리겠습니다.

퀵 정렬에서 최악의 경우는 분할 기준이 매번 제일 크거나 작은 값으로 선택되는 상황입니다.

다시 말해, 이미 정렬된 데이터에 대해서 퀵 정렬을 수행하는 경우입니다.

이럴 때, 분할은 결국 N-1 번 발생하고 각 분할당 최소 1번부터 최대 N-1 번까지 비교하게 됩니다.

그렇게 된다면 결국 퀵정렬의 최악의 경우는 복잡도를 가지게 됩니다.

그럼에도 퀵 정렬을 사용하는 포인트는 다음과 같습니다.

1) 평균적인 경우를 고려하자!

우선 분할의 가장 이상적인 경우는 반반씩 나뉘는 것입니다.

다시 말해, 매 분할마다 정렬해야할 데이터의 크기가 반씩 줄어든다는 의미입니다.

따라서 그럴 경우에는  만큼 분할이 발생하고 각 분할마다 최대 N번의 데이터 비교가 발생합니다.

이런 경우에는 분할 깊이 * 비교 횟수인  시간 복잡도를 가집니다.

2) 분할 기준이 다음 정렬의 대상이 아니다!

퀵 정렬의 경우에는 분할 기준이 다음 정렬에서 정렬 대상이 포함되지 않습니다.

그렇기 때문에,  만큼의 깊이를 가져가는 정렬 방법에서 매우 효과적입니다.

왜 불안정 정렬인가?

선택 정렬이 불안정 정렬임을 보였을 때 처럼 아주 간단한 예시를 보여드리겠습니다.

(이번에도 제가 자주 사용하는 카드를 통해서 알아보겠습니다!)

우선 아래와 같이 스페이스3 - 하트5 - 클로버5 있다고 생각해 봅시다!

원본 데이터가 정렬되어 있지만, 보통 우리는 데이터가 정렬되있다고 판단하기 어렵습니다.

그렇기 때문에 데이터의 정렬 상태를 파악하지 않고 정렬을 진행하게 되는 것이죠!

이제 위 카드를 퀵 정렬 수행하게 된다면,  작은 구간(스페이스 3) / 큰 구간(하트 5) /정렬기준(클로버 5) 분리 됩니다.

그리고 나서 분할 기준(클로버 5)을 큰 구간의 첫 번째 값(하트 5)과 교환하게 됩니다.

교환 후에, 재귀적으로 수행하기 위해서 인덱스 위치를 살펴보니 더 이상 정렬할 구간이 없으므로 종료하게 됩니다.

결과를 살펴보면 기존에는 숫자 5를 가진 카드는  하트5 - 클로버5 순서로 존재했지만,

정렬 후에는 클로버 5 - 하트 5 순서로 존재함을 확인 할 수 있습니다.

따라서 퀵 정렬은 불안정 정렬이 됩니다.

여기서 추가적으로 분할 기준을 다르게 잡으면 가능할까? 라는 생각을 가지신 분들이 있을 수도 있습니다.

하지만, 퀵 정렬의 경우에는 분할 기준과의 값에 대한 교환이 필연적으로 나올 수 밖에 없기 때문에 불안정 정렬이 됩니다. 

퀵 정렬에 대한 내용은 여기까지입니다! 다음 포스팅에서는 퀵 정렬과 가장 많이 비교되는 병합 정렬에 대해서 알아보겠습니다!

개인적인 일 때문에 이번 포스팅이 많이 늦어졌는데 다음 포스팅 부터는 최대한 노력해서 빨리 올려볼게요!

감사합니다 : )