6.2 퀵 정렬(Quick Sort) [디딤돌 자료구조와 알고리즘 with C++]

6.2 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort) 알고리즘은 재귀적인 방법으로 문제를 해결하는 정렬 알고리즘입니다.

 

퀵 정렬 알고리즘은 피벗 값을 선택하여 피벗 값보다 작은 값들은 왼쪽으로 보내고 큰 값들은 오른쪽으로 보낸 후에 이들 사이에 피벗을 위치시키는 원리를 이용합니다. 이후 피벗보다 작은 값들을 재귀 호출로 정렬하고 피벗보다 큰 값들도 재귀 호출로 정렬하는 방식입니다.

 

그런데 퀵 정렬은 어떠한 요소를 피벗으로 선택하냐에 따라 성능에 차이가 납니다. 만약 전체 요소의 중간 순위의 요소를 선택하면 재귀 호출에서 반씩 나누어 정렬하여 좋은 성능을 발휘합니다. 하지만 가장 작은 값이나 가장 큰 값을 피벗으로 선택하면 최악의 성능을 발휘합니다.

 

여기에서는 맨 앞과 맨 뒤, 그리고 중간 위치의 요소를 비교해 세 값 중에 중간 값을 피벗으로 선택할게요.

퀵 정렬(base:컬렉션,n: 원소 개수, compare:비교 논리)

    조건(n<=1)

        종료

    피벗을 선택한다.

    피벗과 맨 앞의 요소를 교환한다.

    big:=0

    small:=n

    반복(big<small)

            반복(big:=big+1; big<n; big:=big+1)

                조건(compare(base[0],base[big])<0)

                    루프 탈출

            반복(small:small-1;small>0;small:small-1)

                조건(compare(base[0],base[small])>0)

                    루프 탈출

            조건(big<small)

                교환(base [big], base [small])

    교환(base [0], base [small])

    퀵 정렬(base,small, compare)

    퀵 정렬(base+big, n-big, compare)

 

퀵 정렬 알고리즘의 탈출 조건은 n이 1보다 작거나 같을 때입니다.

 

 

 

6.2.1 퀵 정렬 알고리즘 성능 분석

퀵 정렬 알고리즘 성능을 분석합시다.

퀵 정렬(base:컬렉션,n: 원소 개수, compare:비교 논리)

    조건(n<=1)

        종료

    피벗을 선택한다.

    피벗과 맨 앞의 요소를 교환한다.

    big:=0

    small:=n

    반복(big<small)

            반복(big:=big+1; big<n; big:=big+1)

                조건(compare(base[0],base[big])<0)

                    루프 탈출

            반복(small:small-1;small>0;small:small-1)

                조건(compare(base[0],base[small])>0)

                    루프 탈출

            조건(big<small)

                교환(base [big], base [small])

    교환(base [0], base [small])

    퀵 정렬(base,small, compare)

    퀵 정렬(base+big, n-big, compare)

 

n 개의 원소인 배열을 정렬할 때 걸리는 수행 시간을 T(n)이라고 합시다. 퀵 정렬은 재귀적인 방법으로 해결하고 반 씩 나누어 재귀 호출이 이루어지는데 재귀 호출이 진행하기 전에 비교에 걸리는 시간을 S(n)이라고 합시다. 그리고 n 개인 원소를 재귀 호출 전에 비교하는 횟수는 n번이므로 S(n)=n입니다.

T(n) = 2*T(n/2) + n = n^2T(n/n^2) + 2*n = ... = h*n

 

재귀는 원소 개수가 1보다 작으면 탈출하므로 n^h =1 일 때 더 이상 재귀 호출은 발생하지 않습니다.

h = logn이므로 T(n) = nlogn

 

그런데 이처럼 퀵 정렬에서 재귀 호출 시에 절반으로 나누어지는 것은 피벗을 잘 선택하였을 때입니다. 따라서 퀵 정렬의 수행 시간은 ω(nlogn)이라고 말할 수 있습니다. n이 충분히 크면 퀵 정렬의 평균 수행 시간도 위처럼 동작하여 Θ(nlogn)입니다.

 

최악은 매 번 분할 시 피벗이 제일 큰 값이거나 제일 작은 값일 때 발생합니다. 만약 피벗이 제일 큰 값이면 피벗보다 작은 값들이 있는 부분만 재귀 함수가 동작합니다. 따라서 T(n)은 다음과 같습니다.

T(n) = T(n-1) + n = T(n-2) + n + n-1 = T(n-3) +n + n-2 + n-1 = ...

 

이처럼 분할하면 퀵 정렬의 수행 시간은 O(n^2)이라고 말할 수 있습니다. 이러한 최악의 속도가 나오지 않게 하려고 알고리즘 초기에 피벗을 선택하는 작업을 하는 것입니다.

 

 

 

6.2.2 퀵 정렬 알고리즘 구현

이번에는 퀵 정렬 알고리즘을 구현해 보기로 해요.

퀵 정렬(base:컬렉션,n: 원소 개수, compare:비교 논리)

    조건(n<=1)

        종료

    피벗을 선택한다.

    피벗과 맨 앞의 요소를 교환한다.

    big:=0

    small:=n

    반복(big<small)

            반복(big:=big+1; big<n; big:=big+1)

                조건(compare(base[0],base[big])<0)

                    루프 탈출

            반복(small:small-1;small>0;small:small-1)

                조건(compare(base[0],base[small])>0)

                    루프 탈출

            조건(big<small)

                교환(base [big], base [small])

    교환(base [0], base [small])

    퀵 정렬(base,small, compare)

    퀵 정렬(base+big, n-big, compare)

 

참고로 2.1.2에서 공통으로 사용할 코드를 이용하세요.

template <typename data, typename compare>

//퀵 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)

void quick_sort(data *base, size_t n, compare com)

{

퀵 정렬의 탈출 조건은 정렬할 원소 개수가 1보다 작거나 같을 때입니다.

    if(n<=1) //조건(n<=1)

    {

        return; //종료

    }

 

피벗을 선택합시다. 여기에서는 맨 앞, 중간, 마지막 원소 중에 중간 값을 갖는 원소를 피벗으로 선택할 것입니다.

    //피벗 선택

    int pivot = 0; //피벗의 위치를 기억하기 위한 변수

먼저 맨 앞과 맨 마지막 원소를 비교합시다.

    if(com(base[0],base[n-1])>0)

    {

맨 앞의 원소가 마지막 원소보다 큰 것은 알았습니다. 다시 맨 앞과 중간에 있는 원소를 비교합시다.

        if(com(base[0],base[n/2])>0) //base[0]이 제일 큰 값, 이 조건인 거짓일 때는 0번째 원소가 중간 값

        {

맨 앞의 원소가 마지막 원소와 중간에 있는 원소보다 큰 것을 알았습니다. 이제 맨 앞과 중간에 있는 원소 중에 큰 값이 피벗입니다.

            if(com(base[n/2],base[n-1])>0) //둘 중에 큰 값이 중간 값

            {

중간에 있는 원소가 더 크므로 중간 값은 중간에 있는 원소입니다.

                pivot = n/2;

            }

            else

            {

맨 뒤에 있는 원소가 더 크므로 중간 값은 맨 뒤에 있는 원소입니다.

                pivot = n-1;

            }

        }

    }

    else //base[n-1]이 base[0]보다 크거나 같음

    {

맨 앞의 원소가 마지막 원소보다 크지 않습니다. 중간에 있는 원소와 마지막 원소를 비교하세요.

        if(com(base[n/2],base[n-1])>0)

        {

중간에 있는 원소가 크므로 맨 뒤에 있는 원소가 중간 값입니다.

            pivot = n-1; //n-1번째 원소가 중간 값

        }

        else//n-1번째 원소가 제일 큰 값

        {

맨 뒤에 원소가 맨 앞 원소와 중간에 있는 원소보다 작지 않다는 것을 알았습니다. 중간에 있는 원소와 맨 앞의 원소를 비교하세요.

            if(com(base[n/2],base[0])>0)//이 조건인 거짓일 때는 0번째 원소가 중간 값

            {

중간에 있는 원소가 맨 앞의 원소보다 크므로 중간 값은 중간에 있는 원소입니다.

                pivot = n/2;//n/2가 중간 값

            }

        }

    }

 

피벗을 선택하였으면 맨 앞의 원소와 피벗에 있는 요소를 교환하세요.    

    swap(base[0],base[pivot]);//피벗과 맨 앞의 요소 교환

 

이제 피벗을 중심으로 큰 값은 왼쪽으로 작은 값들은 오른쪽으로 배치할 것입니다. 이를 위해 앞에서부터 피벗보다 큰 값을 찾고 뒤에서부터 피벗보다 작은 값을 찾는 과정을 반복할 것입니다. 만약 큰 값이 작은 값보다 앞에 있으면 둘을 교환하는 것을 반복할 거예요.

    size_t big=0, small=n; //피벗보다 큰 값과 작은 값의 위치를 찾기 위한 변수    

    while(big<small)//반복(big<small)

    {

순차적으로 피벗과 비교하면서 더 큰 값을 만나면 반복문을 탈출하세요.

        for(big++; big<n; big++)//반복(big:=big+1; big<n; big:=big+1)

        {

            if(com(base[0],base[big])<0)//조건(compare(base[0],base[big])<0)

            {

                break;//루프 탈출

            }

        }

역순으로 피벗과 비교하면서 더 작은 값을 만나면 반복문을 탈출하세요.

        for(small--; small>0; small--)//반복(small:small-1;small>0;small:small-1)

        {

            if(com(base[0],base[small])>0)//조건(compare(base[0],base[small])>0)

            {

                break;//루프 탈출

            }

        }

큰 값이 있는 위치가 작은 값이 있는 위치보다 앞이면 둘은 교환하세요.

        if(big<small)//조건(big<small)

        {

            swap(base[big],base[small]); //교환(base [big], base [small])           

        }

    }

 

이제 피벗을 중심으로 작은 값들은 왼쪽에 큰 값은 오른쪽에 배치하였습니다. 작은 값들 중에 맨 뒤에 있는 요소와 피벗을 교환하세요.

    swap(base[0],base[small]);//교환(base [0], base [small])   

 

재귀함수로 피벗보다 작은 값들이 있는 배열을 정렬합니다.

    quick_sort(base,small,com);//퀵 정렬(base,small, compare)

재귀함수로 피벗보다 큰 값들이 있는 배열을 정렬합니다.

    quick_sort(base+big,n-big,com);//퀵 정렬(base+big, n-big, compare)

}

 

테스트 코드도 2.1.3에서 작성한 코드에서 sequential_sort 부분을 quick_sort로 변경하세요.

#define MAX_DATA 1000

 

int main()

{

    Member *base[MAX_DATA];

퀵 정렬이 잘 동작하는지 10개 원소를 번호 순으로 정렬하여 확인하고 이름 순으로 정렬하여 확인하세요.

    MakeRandomMembers(base,10);

    cout<<"정렬 전"<<endl;

    ViewMembers(base,10);

    quick_sort(base,10,CompareByNum);

    cout<<"번호로 정렬 후"<<endl;

    ViewMembers(base,10);

    quick_sort(base,10,CompareByName);

    cout<<"이름으로 정렬 후"<<endl;

    ViewMembers(base,10);

    RemoveMembers(base,10);

 

그리고 MAX_DATA 개일 때 수행 속도와 MAX_DATA/10 개일 때 수행 속도를 비교해 보세요.

    clock_t st,et;

 

    MakeRandomMembers(base,MAX_DATA);

    cout<<"수행 성능 테스트1 자료 개수:"<<MAX_DATA<<endl;

    st = clock();   

    quick_sort(base,MAX_DATA,CompareByName);   

    et=clock();

    cout<<"수행 속도:"<<et-st<<endl;

    RemoveMembers(base,MAX_DATA);

 

    MakeRandomMembers(base,MAX_DATA/10);

    cout<<"수행 성능 테스트2 자료 개수:"<<MAX_DATA/10<<endl;

    st = clock();

    MakeRandomMembers(base,MAX_DATA/10);

    quick_sort(base,MAX_DATA/10,CompareByName);

    et=clock();

    cout<<"수행 속도:"<<et-st<<endl;

    RemoveMembers(base,MAX_DATA/10);

    return 0;

}

 

다음은 실행 결과예요.

▷실행 결과

정렬 전

0000757147,이름0167851000

0301413356,이름0336971124

0659598368,이름0160567225

0391749387,이름0004890851

0035766290,이름0026239572

0473038164,이름0000597006

0003615544,이름0326051436

0392289610,이름0118341522

0170427798,이름0037215528

0675016433,이름0168544290

번호로 정렬 후

0000757147,이름0167851000

0003615544,이름0326051436

0035766290,이름0026239572

0170427798,이름0037215528

0301413356,이름0336971124

0391749387,이름0004890851

0392289610,이름0118341522

0473038164,이름0000597006

0659598368,이름0160567225

0675016433,이름0168544290

이름으로 정렬 후

0473038164,이름0000597006

0391749387,이름0004890851

0035766290,이름0026239572

0170427798,이름0037215528

0392289610,이름0118341522

0659598368,이름0160567225

0000757147,이름0167851000

0675016433,이름0168544290

0003615544,이름0326051436

0301413356,이름0336971124

수행 성능 테스트1 자료 개수:1000

수행 속도:79

수행 성능 테스트2 자료 개수:100

수행 속도:6

 

퀵 정렬의 결과를 보면 자료 개수가 MAX_DATA일 때 MAX_DATA/10일 때보다 130배 정도 느린 것을 알 수 있습니다. 앞에서 알고리즘 성능을 분석할 때 O(nlogn)과 비슷하죠. 이제까지 구현했던 순차, 거품, 선택, 삽입 정렬 알고리즘보다 수행 성능이 뛰어난 것을 알 수 있습니다.