퀵정렬(Quick Sort) 구현

 

퀵정렬(Quick Sort)

- 찰스 앤터니 리처드 호어가 개발한 알고리즘이다.

- 평균 O(n log n)으로 매우 빠른 정렬속도를 자랑한다.

- 기준(Pivot) 값을 기준으로 나머지 원소에 대해 대소관계를 비교하여 큰 것과 작은 것으로 이분한 다음 다시 해당 작업을 반복한다.

  ※ 이와 같이 문제를 작은 문제로 분할하여 해결하는 방법을 분할 정복(Devide and Conquer)이라 한다.

 

 

 

원리(오름차순 기준)

  1. Pivot의 값은 배열의 제일 오른쪽 원소로 정한다.

    ※ Pivot의 위치는 정해져있지 않다. (왼쪽도 되고 중앙도 된다.)

  2. Low는 오른쪽으로, High는 왼쪽으로 돌면서 각 원소를 Pivot 원소와 대소관계를 파악한다.

    2-1. Low는 Pivot보다 작아야한다. 즉, Pivot의 값보다 크면 순회를 멈춘다.

    2-2. High는 Pivot보다 커야한다. 즉, Pivot의 값보다 작으면 순회를 멈춘다.

    2-3. Low와 High의 값을 SWAP한다.

  3. Low와 High가 교차할때까지 2번의 작업을 반복한다.

  4. Low와 High가 교차를 하게되면 Low와 Pivot의 값을 SWAP한다.

  5. Pivot의 값을 기준으로 왼쪽 원소들은 Pivot보다 작은 값들, 오른쪽 원소들은 큰 값들만 있으므로, 왼쪽과 오른쪽의 원소들을 분할하여 1 ~ 4번의 과정을 반복한다.

    ※ Left와 Right가 더이상 쪼개지지 않을때까지 반복한다. (재귀함수를 이용)

    ※ Pivot을 기준으로 두개의 배열로 나누는걸 파티션(Partition)이라고 한다.

 

 

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX 10
#define ASCENDING 1
#define DESCENDING 2

void SetArr(int arr[])
{
    for (int i = 0; i < MAX; i++)
    {
        arr[i] = rand() % 100;
    }
}

void PrintArr(int arr[])
{
    for (int i = 0; i < MAX; i++)
    {
        printf("%d\n", arr[i]);
    }
}

void Swap(int* n1, int* n2)
{
    int tmp = *n2;
    *n2 = *n1;
    *n1 = tmp;
}

int Sorting(int arr[], int left, int right, int sortType)
{
    int pivot = right;
    int low = left, high = pivot - 1;
	
    while (low <= high)
    {
        switch (sortType)
        {
        case ASCENDING:
            //find low index
            for (; low <= high && arr[low] <= arr[pivot]; low++);
            //find high index
            for (; high >= low && arr[high] >= arr[pivot]; high--);
            break;
        case DESCENDING:
            //find low index
            for (; low <= high && arr[low] >= arr[pivot]; low++);
            //find high index
            for (; high >= low && arr[high] <= arr[pivot]; high--);
            break;
        }
		
        if (low <= high)
        {
            Swap(&arr[low], &arr[high]);
        }
    }
	
    Swap(&arr[low], &arr[pivot]);
    return low;
}

void QuickSort(int arr[], int left, int right, int sortType)
{
    if (left >= right) return;
	
    int pivot = Sorting(arr, left, right, sortType);
	
    //Left partition
    QuickSort(arr, left, pivot - 1, sortType);
    //Right partition
    QuickSort(arr, pivot + 1, right, sortType);
}

void main()
{
    srand(time(NULL));
    int iArr[MAX] = { 0 };
	
    SetArr(iArr);
	
    QuickSort(iArr, 0, MAX - 1, ASCENDING);
    //PrintArr(iArr);
	
    QuickSort(iArr, 0, MAX - 1, DESCENDING);
    //PrintArr(iArr);
}