3.3.2 퀵 정렬 알고리즘 구현

2 장에서 만들었던 정렬 알고리즘과 같은 방법으로 시뮬레이션 코드를 작성합니다. 여기에서는 퀵 정렬 알고리즘만 구현할게요. 참고로 퀵 정렬 알고리즘을 내부 알고리즘을 별도의 함수로 구현하지 않고 직접 구현할게요. 정렬 알고리즘은 수행 속도가 중요한 이슈이므로 복잡하더라도 하나의 함수로 구현할게요.

void quick_sort(Element *base, int n, Compare compare)
{

먼저 교환에 사용할 임시 변수와 피벗의 위치와 피벗보다 큰 값과 작은 값의 위치를 기억하기 위한 변수를 선언합시다.

    Element temp;//교환을 위한 임시 변수
    int pivot = 0; //피벗의 위치를 기억하기 위한 변수
    int big=0, small=0; //피벗보다 큰 값과 작은 값의 위치를 찾기 위한 변수

만약 원소의 개수가 1보다 작거나 같으면 함수를 종료합니다. 이 부분이 재귀 함수의 탈출 조건입니다.

    if(n<=1)
    {
        return;
    }//    조건(n<=1)   종료

피벗을 선택합니다. 여기에서는 맨 앞의 원소와 중간에 있는 원소, 맨 뒤에 있는 원소 중에 중간 값을 피벗으로 선택할게요. 먼저 맨 앞의 원소와 맨 뒤의 원소를 비교합시다.

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

만약 맨 앞의 원소가 크면 중간에 있는 원소와 다시 비교합니다.

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

이 때도 맨 앞의 원소가 크면 일단 제일 큰 값은 맨 앞에 있는 원소입니다. 이 때는 중간에 있는 원소와 맨 뒤에 있는 원소를 비교해야 중간 값을 알 수 있습니다. 이 둘을 비교하여 큰 값이 중간 값입니다.

            if(compare(base[n/2],base[n-1])>0) //둘 중에 큰 값이 중간 값
            {
                pivot = n/2;
            }
            else
            {
                pivot = n-1;
            }
        }
    }

만약 n-1번째 원소가 0번째 원소보다 크거나 같을 때의 피벗을 찾아봅시다.

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

중간에 있는 원소와 맨 뒤의 원소를 비교하여 중간에 있는 원소가 더 크면 맨 뒤의 원소가 중간 값입니다.

        if(compare(base[n/2],base[n-1])>0)
        {
            pivot = n-1; //n-1번째 원소가 중간 값
        }

그렇지 않다면 맨 뒤에 있는 원소가 제일 큰 값입니다.

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

이 때는 다시 중간에 있는 원소와 맨 앞의 원소를 비교합니다. 이 둘 중에 큰 값이 중간 값입니다.

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

이제 피벗과 맨 앞의 요소를 교환합니다.

    //피벗과 맨 앞의 요소를 교환한다.
    temp = base[pivot];
    base[pivot] = base[0];
    base[0] = temp;

앞쪽부터 피벗보다 큰 값이 있는지 확인할 것입니다. 그리고 뒤쪽부터 작은 값이 있는지 확인할 것입니다. big을 0으로 초기화하고 small을 n으로 초기화하는 이유는 이전에 찾은 위치 다음으로 이동한 후에 찾는 작업을 할 것이기 때문입니다.

    big=0;//big:=0
    small = n;//small:=n

피벗보다 큰 값을 발견한 위치가 작은 값을 발견한 위치보다 앞이면 아직 피벗을 기준으로 작은 값들과 큰 값들을 배치하는 작업을 계속 해야 합니다.

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

먼저 피벗보다 큰 값을 찾습니다. 이전에 위치 뒤로 이동한 후에 마지막 요소까지 순차적으로 이동하면서 찾습니다.

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

만약 피벗보다 big위치의 원소가 더 크면 루프를 탈출합니다.

            if(compare(base[0],base[big])<0)//            조건(compare(base[0],base[big])<0)
            {
                break;//                루프 탈출
            }
        }

피벗보다 작은 값을 찾습니다. 이전에 위치 앞으로 이동한 후에 맨 앞까지 순차적으로 이동하면서 찾습니다. 그리고 피벗보다 small 위치의 원소가 더 작으면 루프를 탈출합니다.

        for(small--; small>0; small--)//        반복(small:small-1;small>0;small:small-1)
        {
            if(compare(base[0],base[small])>0)//            조건(compare(base[0],base[small])>0)
            {
                break;//                루프 탈출
            }
        }

만약 big 위치가 small 위치보다 앞이면 두 원소를 교환합니다.

        if(big<small)//        조건(big<small)
        {
        //            교환(base [big], base [small])
            temp = base[big];
            base[big] = base[small];
            base[small] = temp;
        }
    }

이제 피벗과 small위치의 원소를 교환합니다. 이를 수행하면 피벗보다 작은 값들은 왼쪽에 존재하고 큰 값들은 오른쪽에 존재하고 피벗은 정렬을 완료한 상태에 있어야 할 위치에 존재합니다.

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

피벗보다 앞쪽을 재귀함수로 정렬합니다. 그리고 뒤쪽도 재귀함수로 정렬합니다.

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

재귀 함수의 깊이가 깊어지면 스택 메모리가 부족할 수 있습니다. 필요하면 프로젝트 속성 창을 열어 스택 크기를 설정하세요.

테스트를 해 보면 자료 개수가 10배 늘었을 때 20배 정도의 속도 차이가 나는 것을 알 수 있습니다.  하지만 피벗을 선택하여 맨 앞의 원소와 교환하는 부분을 주석 처리하고 정렬 상태의 배열이나 역순으로 정렬 상태의 배열을 정렬 요청하면 최악의 속도가 나오는 것을 확인할 수 있습니다.