[C언어 알고리즘] 3.3.3 퀵 정렬 알고리즘 소스 코드

[C언어 알고리즘] 3.3.3 퀵 정렬 알고리즘 소스 코드

---

//퀵 정렬(Quick Sort)

#include <stdio.h>

 

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

 

 

int *origin;

int on;

 

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; // 피벗보다 큰 값과 작은 값의 위치를 찾기위한 변수

 

    if (n <= 1)

    {

        return;

    }

 

    left = 0;

    right = n;

 

    while (1)

    {

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

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

 

        if (left<right)

        {

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

            PrintSpace(base - origin);

            ViewArr(base, n);

        }

        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;

    for (i = 0; i<n; i++)

    {

        printf("%2d ", arr[i]);

    }

    printf("\n");

}