c언어 - 퀵 정렬 (QuickSort)

퀵 정렬은 이름처럼 빠른 정렬이다.

퀵 정렬은 적절한 하나의 기준(피벗)을 잡고 피벗을 기준으로 삼아 값들을 정렬해나간다.

피벗(pivot)을 어떻게 설정하느냐에 따라 정렬 시간에 큰 영향을 준다. 그래서 최악의 경우 O(n^2)의 시간이 걸릴 수 있다.

피벗을 기준으로 작은 값은 왼쪽 큰 값은 오른쪽으로 보내면서 정렬해간다. 정렬할 리스트가 1~0일때 까지 반복하는 정렬이다.

글로 설명하는건 쉬우나 코딩할때 조금 꼬일수있으니 주의하면서 코딩해보자.

low, high 을 좌표로 잡고 피벗과 비교하면서 low 는 피벗보다 큰 수를  high 는 피벗보다 작은수를 서로 교환한다.

low 와 high가 교차하는 순간 low 와 피벗을 교체한다.

그리고 피벗을 기준으로 -1, +1 한 값을 재귀함수를 이용하여 퀵 정렬에 다시 넣어준다.

(left,right) -> (left,피벗-1), (피벗+1,right) 으로 재귀하며 정렬해나간다.

재귀하며 left 와 right 값이 1~0 일때 끝이난다.

 

 

 

퀵 정렬의 과정을 적어볼까 하는데 생각보다 길다.. 참고하고 보면 편할 것 같다.

필자는 가장 오른쪽에 있는 값을 피벗으로 잡고 진행했다.

자세한 과정을 보고 싶다면 더보기를 눌러주세요.

---

---

생각보다 길어졌는데 이해가 가는데, 조금이나마 도움이 되면 좋겠다 싶어 올려본다.

 핵심 알고리즘

---

void QuickSort(int *arr, int left, int right)
{
    if(left < right)
    {
    int NewPivot = Partition(arr, left, right);


    QuickSort(arr, left, NewPivot-1);
    QuickSort(arr, NewPivot+1, right);
    }
}

int Partition(int *arr, int left, int right)
{
    int low, high, pivot = 0;

    pivot = arr[right];
    low = left;
    high = right-1;

    while(low < high)
    {

        while(low<=right && arr[low]<pivot)
        {
            low++;
        }
        while(high>=left && arr[high]>pivot)
        {
            high--;
        }
        if(low<high)
        {
            swap(arr, &arr[low], &arr[high]);
        }
    }
    swap(arr, &arr[low], &arr[right]);
    return low;
}

 

 

코드

---

#include<stdio.hw

void QuickSort(int *arr, int left, int right);
int Partition(int *arr, int left, int right);
void swap(int *arr, int *a, int *b);

int main()
{
    int arr[] = {9,6,5,8,10,1,3,7,4,2};

    QuickSort(arr, 0, 9);
    //정렬된 배열의 출력
    for(int c=0;c<=9;c++){
        printf("%d ",arr[c]);
    }
}

void QuickSort(int *arr, int left, int right)
{
    if(left < right)
    {
    int NewPivot = Partition(arr, left, right);

    //피벗을 기준으로 두 그룹으로 만들어서 다시 정렬한다.
    QuickSort(arr, left, NewPivot-1);
    QuickSort(arr, NewPivot+1, right);
    }
}

int Partition(int *arr, int left, int right)
{
    int low, high, pivot = 0;

    pivot = arr[right];
    low = left;
    high = right-1;

    while(low < high)
    {

        while(low<=right && arr[low]<pivot)
        {
            low++;
        }
        while(high>=left && arr[high]>pivot)
        {
            high--;
        }
        if(low<high)
        {
            swap(arr, &arr[low], &arr[high]);
        }
    }
    //피벗을 중간 자리로 이동시켜준다.
    swap(arr, &arr[low], &arr[right]);
    return low;
}

void swap(int *arr, int *a, int *b)
{
    int t;
    t = *a;
    *a = *b;
    *b = t;
}