자료구조 QuickSort

/*
1. 데이터 집합 내에서 임의의 기준 요소를 선택하고, 기준요소보다 작은 요소들은 순서에 관계없이 무조건 기준 요소의 왼편에, 큰 값이 오른편에 위치시킵니다.
2. 기준 요소 오니편에는 기준 요소보다 작은 요소들이 모여있고 오른편에는 큰 요소들이 모여있습니다.
이렇게 나눈 데이터 집합들을 다시 1에서와 같이 임의의 기준 요소를 선택하고 같은 방법으로 데이터 집합을 분할합니다.
3. 1과 2의 과정을 더 이상 데이터 집합을 나눌 수 없을 때까지 반복하면 정렬된 데이터 집합을 얻게됩니다. */

//방법1. swap함수 만들어 사용하기

#include <stdio.h>

void swap(int *x, int *y) {
        int temp = *x;
        *x = *y;
        *y = temp;
}

int Partition(int DataSet[], int Left, int Right) {
        int First = Left;
        int Pivot = DataSet[First];

        ++Left;

        while (Left<=Right) {
                while (DataSet[Left]<=Pivot && Left<Right)
                ++Left;
                while (DataSet[Right]>Pivot && Left<=Right)
                --Right;

                if (Left< Right)
                        swap(&DataSet[Left], &DataSet[Right]);
                else break;
        }
        swap(&DataSet[Right], &DataSet[First]);
        return Right;
}

void QuickSort(int DataSet[], int Left, int Right) {
        if (Left< Right) {
                int index = Partition(DataSet, Left, Right);

                //재귀 2번 (왼쪽 파티션에 대한 재귀, 오른쪾 파티션에 대한 재귀)
                QuickSort(DataSet, Left, index - 1);
                QuickSort(DataSet, index + 1, Right);
        }
}

void sort(int DataSet[], int l, int r) {
        int left = l;
        int right = r;
        int pivot = DataSet[(l + r) / 2];

        do {
                while (DataSet[left] < pivot) left++;
                while (DataSet[right] > pivot) right--;
                if (left <= right) {
                        swap(&DataSet[left], &DataSet[right]);
                        left++;
                        right--;
                }
        } while (left <= right);

        if (l < right) sort(DataSet, l, right);
        if (r < left) sort(DataSet, left, r);
}

void main() {
        int DataSet[] = { 6,4,2,3,1,5 };
        int Length = sizeof(DataSet) / sizeof(int);
        QuickSort(DataSet, 0, Length - 1);
        for (int i = 0; i < Length; i++)
                printf("%d", DataSet[i]);
        printf("\n");
}

=========================================================================
//방법2. 라이브러리의 qsort함수 이용하기

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/*
void qsort(
        void *base, : 데이터 집합 배열의 주소
        size_t num, : 데이터 요소의 개수
        size_t width : 한 데이터 요소의 크기
        int(_cdecl *compare)(const void *, const void *)
        비교함수에 대한 포인터
)
int compare((void *)&elem1, (void *)& elem2);
*/
/*
return 값이
<0 : _elem1이 _elem2보다 작다.
0 : 같다
>0 : _elem1이 _elem2보다 크다.
*/

int CompareScore(const void*_elem1, const void*_elem2) {
        int* elem1 = (int *)_elem1;
        int* elem2 = (int *)_elem2;

        if (*elem1 > *elem2) return 1;
        else if (*elem1 < *elem2) return -1;
        else return 0;
}

void main() {
        int DataSet[] = { 6,4,2,3,1,5 };
        int Length = sizeof(DataSet) / sizeof(int);
        qsort((void*)DataSet, Length, sizeof(int), CompareScore);

        for (int i = 0; i < Length; i++)
                printf("%d", DataSet[i]);
        printf("\n");
}
=========================================================================
//출력