Quick 정렬 구현

Quick 정렬을 구헌해보자

 

이전에 공부한 Merge Sort를 안다면 쉽게 공부할 수 있다.

 

Quick 정렬 역시 Merge Sort와 마찬가지로 분할 정복(Divide and conquer)으로 근거하여 만든 정렬 방법이다.

 

다만 Merge Sort와 다른점은 Merge Sort는 균등하게 나누었다면 Quick Sort는 비균등하게 나눈다.

 

Quick Sort에는 3가지 변수를 사용한다.

 

1. Pivot : 중심점

 

2. LeftIndex: Pivot을 제외한 제일 왼쪽 Index

 

3. RightIndex: Pivot을 제외한 제일 오른쪽 Index 

 

 

pivot을 제일 왼쪽으로 하면 다음 그림과 같이 변수가 잡힌다.

 

Quick Sort 과정

 

1. left Index를 Pivot 보다 큰 값을 만날때 까지 증가시킨다.

2. Right Index를 Pivot 보다 작은 값을 만날때 까지 감소 시킨다.

 

교환 전

 

3. left Index와 right Index의 값을 교환한다.

 

교환 후

 

4. left Index와 right Index가 교차되기 전까지 1~3을 반복한다.

 

left Index 와 right Index 교차 후 Index 위치

 

5. Pivot의 위치를 left Index로 바꾼다.

 

6. Pivot을 위치를 기준으로 왼쪽, 오른쪽을 분할 한다.

 

7. 다시 분할 된 배열의 Pivot, left, right Index를 잡아 1 ~ 6을 진행한다.

 

8. left Index 가 right Index가 교차 되지 않을때 까지 1 ~ 7 과정을 반복한다.

 

 

코드 구현

위 1~ 3번을 반복하는 함수이다. 마지막 left Index를 return 함으로써 5번을 실행하게 된다.

int SortAndFindPivot(Data *arr, int startIdx, int endIdx, compFunc comp)
{
    int _pivotIdx = startIdx;
    int _leftIdx = _pivotIdx + 1;
    int _rightIdx = endIdx;

    /* == 1. Pivot을 기준으로 왼쪽, 오른쪽 배열을 정렬하면서 나눈다. == */ 
    while (_leftIdx < _rightIdx)
    {
        /* == pivot 보다 큰 데이터를 찾는다. == */
        while ((arr[_pivotIdx] != comp(arr[_leftIdx], arr[_pivotIdx])) && \
                (_leftIdx <= _rightIdx))
            _leftIdx++;

        /* == pivot 보다 작은 데이터를 찾는다. == */
        while ((arr[_rightIdx] != comp(arr[_rightIdx], arr[_pivotIdx])) && \
                (_leftIdx <= _rightIdx))
            _rightIdx--;

        /* == left Index와 right Index를 찾았으므로 교환한다 == */
        _changeData(&arr[_pivotIdx], &arr[_rightIdx]);

    }
    /* == Pivot 위치를 return 한다 == */
    return _leftIdx;

 

quickSort 구현

int quickSort(Data *arr, int startIdx, int endIdx, compFunc comp)
{
    TR_FUNC(TRACE);
    /* == left, right Index를 움직이면서 교환 후 pivot 위치를 Return 한다 == */
    int pivotIdx = SortAndFindPivot(arr, startIdx, endIdx, comp);
    /* == 둘로 나눈다 end Indexrk Start Index 보다 작지 않는 이상. == */
    if (pivotIdx > 0 && (endIdx - startIdx > 0))
    {
        /* == 분할 된 왼쪽 배열을 다시 퀵 정렬한다. == */
        quickSort(arr, startIdx, pivotIdx - 1, comp);
        /* == 분할 된 오른쪽 배열을 다시 퀵 정렬한다. == */
        quickSort(arr, pivotIdx, endIdx, comp);
    }

    return 0;

}

다음 Main 함수를 실행하여 코드를 검증하였다.

 

int array[] = {2,1,5,6,7,4,3,9,8,10};

int comp(int val1, int val2)
{
    int temp = 0;

    return temp = val1 < val2 ? val1 : val2;
}

int main(void)
{
    printf("Start Quick Sort \r\n");

    for (int i = 0; i <= (sizeof(array) / sizeof(int)) - 1; i++)
    {
        printf(" %d",array[i]);
    }
    printf("\r\n");

    quickSort(array, 0, (sizeof(array) / sizeof(int)) - 1, comp);

    printf("Finish Quick Sort \r\n");

    for (int i = 0; i <= (sizeof(array) / sizeof(int)) - 1; i++)
    {
        printf(" %d",array[i]);
    }
    printf("\r\n");

    return 0;
}

 

실행 결과

 

https://github.com/KJT9109/Data_Structure.git