[알고리즘 C언어] 3.3.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)

//퀵 정렬(Quick Sort)
#include <stdio.h>

먼저 두 개의 값을 교환하는 매크로 함수를 작성합니다.

#define SWAP(a,b)  {int t; t = a; a=b; b=t;}//a와 b를 교환

여기에서는 정렬하는 과정을 출력하는 부분이 있습니다. 이를 위해 정렬을 수행하는 배열의 시작 주소와 원소 개수를 기억하는 전역 변수를 선언하세요. 만약 정렬 과정을 출력할 필요가 없다면 주석 처리하세요.

int *origin;
int on;

이 책에서는 정수 형식 배열을 정렬하는 함수를 만들기로 할게요. 원소 형식에 관계없이 정렬하는 방법은 디딤돌 정렬 알고리즘 (C언어)를 참고하세요.

void QuickSort(int *base, int n);
void ViewArr(int *arr, int n);
int main(void)
{
    int arr[10] = { 9,4,3,10,5,8,7,6,2,1 };

정렬해 나가는 과정을 출력하기 위한 목적으로 배열 주소와 원소 개수를 전역 변수에 설정합니다. 만약 테스트 과정을 출력할 필요가 없다면 주석 처리하세요.

    origin = arr;
    on = 10;
    ViewArr(arr, 10);
    QuickSort(arr, 10);
    ViewArr(arr, 10);
    return 0;
}

void PrintSpace(int n);
void QuickSort(int *base, int n)
{

피벗 위치를 기억하는 변수와 피벗보다 큰 값과 작은 값의 위치를 찾기 위한 변수를 선언하세요.

    int pivot = 0; // 피벗의 위치 기억하는 변수
    int left = 0, right = 0; // 피벗보다 큰 값과 작은 값의 위치를 찾기위한 변수

재귀 함수의 탈출 조건은 원소 개수가 1보다 작거나 같을 때입니다.

    if (n <= 1)
    {
        return;
    }

피벗보다 큰 값은 앞에서 부터 뒤로 이동하면서 찾을 것입니다. 그리고 피벗보다 작은 값은 뒤에서부터 앞으로 이동하면서 찾을 것입니다. 반복문 내부에서 이전에 찾은 위치 다음부터 진행하므로 초기값을 0과 n으로 설정합니다.

    left = 0;
    right = n;

    while (1)
    {

이전에 찾은 위치를 변경한 후에 뒤로 이동하면서 피벗보다 큰 값을 만날 때까지 left를 이동합니다.

        for (left++; (left<n) && (base[0] >= base[left]); left++);

이전에 찾은 위치를 변경한 후에 앞으로 이동하면서 피벗보다 작은 값을 만날 때까지 left를 이동합니다.

        for (right--; (right>0) && (base[0]<base[right]); right--);

만약 left가 right보다 작다면 피벗과 비교하였을 때 작은 값이 큰 값보다 뒤에 있으니 교환합니다.

        if (left<right)
        {
            SWAP(base[left], base[right]);

정렬 과정을 보여주기 위해 출력하는 것입니다. 만약 정렬 과정을 보여줄 필요가 없다면 주석 처리하세요.

            PrintSpace(base - origin);
            ViewArr(base, n);
        }

left가 right보다 작지 않다면 피벗을 중심으로 작은 값들과 큰 값들을 분리하는 것이 끝났습니다. 따라서 반복문을 탈출합니다.

        else
        {
            break;
        }
    }

이제 피벗을 작은 값들과 큰 값들 사이로 보냅니다.

    SWAP(base[0], base[right]);

정렬 과정을 보여주기 위해 출력하는 것입니다. 만약 정렬 과정을 보여줄 필요가 없다면 주석 처리하세요.

    PrintSpace(base - origin);
    ViewArr(base, n);

피벗보다 작은 값들이 있는 앞쪽을 재귀 호출로 정렬합니다.

    QuickSort(base, right);

피벗보다 큰 값들이 있는 뒤쪽을 재귀 호출로 정렬합니다.

    //피벗보다 큰 값들이 있는 뒤쪽을 재귀 호출로 정렬합니다.
    QuickSort(base + left, n - left);
}

출력 과정을 표시하기 위해 제공하는 합수입니다. 먼저 재귀 과정에서 자신의 위치 앞쪽을 공백을 출력하기 위한 함수를 작성하세요.

void PrintSpace(int n)
{
    int i = 0;
    for (i = 0; i<n; i++)
    {
        printf("   ");
    }
}

테스트 목적으로 배열의 내용을 출력하는 함수입니다.

void ViewArr(int *arr, int n)
{
    int i = 0;

인덱스 0에서 마지막 요소까지 값을 출력합니다.

    for (i = 0; i<n; i++)
    {
        printf("%2d ", arr[i]);
    }

전체 요소 값을 출력한 후에 개행 문자를 출력합니다.

    printf("\n");
}
퀵 정렬
퀵 정렬

시뮬레이션 코드는 다음과 같습니다.

//퀵 정렬(Quick Sort)
#include 
#include 

#define SWAP(a,b)  {int t; t = a; a=b; b=t;}//a와 b를 교환
#define LENGTH(arr)  (sizeof(arr)/sizeof(arr[0]))

enum Color
{
    BLACK, BLUE, GREEN, JADE, RED, PURPLE, YELLOW, WHITE, GRAY,
    LIGHT_BLUE, LIGHT_GREEN, LIGHT_JADE, LIGHT_RED, LIGHT_PURPLE, LIGHT_YELLOW, LIGHT_WHITE
};
void changecolor(int color)
{
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), color);
}

#define MAX_ELEM 30
void QuickSort2(int* obase, int on,int *base,int n);
void MakeRandoms(int* base, int n, int end);
void ViewArr(int* arr, int n);
int main(void)
{   
    int arr[MAX_ELEM];
    MakeRandoms(arr, MAX_ELEM, 100);
    
    ViewArr(arr, MAX_ELEM);    
    QuickSort2(arr, MAX_ELEM,arr, MAX_ELEM);
    ViewArr(arr, MAX_ELEM);    
    return 0;
}
void MakeRandoms(int* base, int n, int end)
{
    srand((unsigned)time(0));
    int i = 0;
    for (i = 0; i < n; i++)
    {
        base[i] = rand() % end;
    }
}

void PrintSpace(int n);
void View2(int *obase, int on, int *base, int n, int left, int right,int how);
void QuickSort2(int* obase, int on, int* base, int n)
{
    int pivot = 0; // 피벗의 위치 기억하는 변수
    int left = 0, right = 0; // 피벗보다 큰 값과 작은 값의 위치를 찾기위한 변수

    if (n <= 1)
    {
        return;
    }

    left = 0;
    right = n;
    while (1)
    {
        Sleep(300);
        for (left++; (left < n) && (base[0] >= base[left]); left++)
        {
            View2(obase, on, base, n, left, right,0);
            
        }
        View2(obase, on, base, n, left, right, 0);
        changecolor(LIGHT_YELLOW);
        PrintSpace(base - obase + left);
        printf("BIG\n");
        for (right--; (right > 0) && (base[0] < base[right]); right--)
        {
            View2(obase, on, base, n, left, right,0);
        }
        View2(obase, on, base, n, left, right, 0);
        changecolor(LIGHT_YELLOW);        
        PrintSpace(base-obase+right);
        printf("small\n");
        if (left < right)
        {               
            SWAP(base[left], base[right]);            
            View2(obase, on, base, n, left, right,1);
        }        
        else
        {
            break;
        }
    }        
    
    SWAP(base[0], base[right]);          
    View2(obase, on, base, n, left, right,2);
    Sleep(300);
    int gap = base - obase;
    if (right >1)
    {
        changecolor(LIGHT_YELLOW);
        printf("Recursice call start:%d count:%d\n", gap,right);
    }
    QuickSort2(obase,on,base, right);    
    if (n - left >1)
    {
        changecolor(LIGHT_YELLOW);
        printf("Recursice call start:%d count:%d\n", gap+left, n-left);
    }
    QuickSort2(obase,on,base + left, n - left);
}
void View2(int* obase, int on, int* base, int n, int left, int right,int how)
{    
    int gap = base - obase;
    n += gap;
    left += gap;
    right += gap;
    int i = 0;
    for (i = 0; i < on; i++)
    {
        changecolor(WHITE);
        if (i < gap)
        {
            changecolor(BLACK);
        }
        if (i == gap)
        {
            changecolor(LIGHT_RED);
            if (how == 2)
            {
                changecolor(LIGHT_PURPLE);
            }
        }
        if (i == left)
        {
            if (how == 0)
            {
                changecolor(LIGHT_GREEN);
            }
            if (how == 1)
            {
                changecolor(LIGHT_PURPLE);
            }
        }
        if (i == right)
        {
            if (how == 0)
            {
                changecolor(LIGHT_PURPLE);
            }
            if (how == 1)
            {
                changecolor(LIGHT_GREEN);
            }
            if (how == 2)
            {
                changecolor(LIGHT_RED);
            }
        }
        if (i >= n)
        {
            changecolor(BLACK);
        }
        printf("%2d ", obase[i]);
    }
    printf("\n");
    changecolor(WHITE);
}

void ViewArr(int* arr, int n)
{
    int i = 0;
    for (i = 0; i < n; i++)
    {
        printf("%2d ", arr[i]);        
    }
    printf("\n");
}
void PrintSpace(int n)
{
    int i = 0;
    for (i = 0; i < n; i++)
    {
        printf("   ");
    }
}