C Data Structure - 퀵 정렬

내가 퀵 정렬까지 공부할 줄은 몰랐(었)다. 역시 차근차근 해 놓는게 중요하다. 더불어 포스팅도 그 때 그 때 하지 않으면 이렇게 개 고생한다.

어찌됐건 오늘은 퀵 정렬이다.

나는 이게 퀵 정렬이 겁나 빨라서 퀵 정렬인가 했는데, 맞다. 겁나 빠른 퀵 정렬 한 번 기록해둔다.

퀵 정렬이란?

퀵 정렬은 이름을 통해서는 대충 어떤 정렬인지 짐작하기가 힘들다. 뭐 병합 정렬과 같은 경우는 뭔가 병합 해나가겠지 싶었는데 퀵 정렬은 아니다. 그래서 퀵 정렬이 무엇인가 라기 보다는 퀵 정렬의 작동 원리를 기록하는게 나의 인생에, 그대의 인생에 더 유익하지 않을까 싶다.

퀵 정렬은 병합 정렬과 매우 비슷하게, 쪼개는 것이 그 기본으로 깔려 있는 정렬이다. 또 쪼개기 시작한다는거다. 쪼갠다는 것의 의미는 병합 정렬에 잘? 설명되어 있는진 모르겠고 애타게 설명을 적어 놓았다.

https://typingdog.tistory.com/122?category=924874

C Data Structure - 병합 정렬

퀵 정렬의 주된? 사상?은 이렇다. 

1. 배열을 쪼개는 것과 동시에 정렬하는 것이 아니다
2. 그렇다고 해서 앞/뒤 비교를 하며 정렬을 한다고 생각하면 안된다.
3. 어떤 기준에 맞는 '하나'의 요소의 정렬된 위치를 찾고, 고정한 뒤, 그 위치를 중심으로 양 옆 두개로 쪼개는 것이다. 이 때, 고정된 요소는 이미 올바른 정렬 위치를 찾았으니 정렬 대상에서 제외한다.

그러니까 결국에는 주어진 범위에 한해서 어떤 기준에 의거하여 단 하나의 요소의 올바른 정렬 위치를 찾아나가고 그 위치를 기준으로 양 옆으로 쪼개는 것을 반복해나간다고 생각하면 된다.

사과해야겠다. 이게 무슨 말이냐? 그림으로 기록해야겠다.

이런 배열이 있다.

이 배열을 아주 오도방정을 떨면서 왔다갔다 할 이상한 인덱스들을 소개하겠다.

자, 그림 내에 설명을 기록했지만, 추가 설명이 필요한 부분을 기록하겠다. 

일단, pivot은 비교의 기준이라고 했는데 꼭 이 기준을 맨 왼쪽에 둘 필요도 없다. 다만 이런 기준이 어디에 있긴 있어야한다는 소리인데, 오름차순 정렬의 경우 맨 왼쪽에 많이 쓴다고 생각한다고 생각한다....ㅋㅋ

left와 right는 무조건 배열 전체 중 인덱스 0과 인덱스 끝을 나타내는게 아니라 주어진 범위 내에서 가장 왼쪽과 오른쪽을 나타내는 것이기 때문에, 물결 표시로 강조를 했다.

기본적인 동작은 다음과 같다.

row를 먼저 쫙~ 증가시킨 다음에 2번 상태를 만들고, high를 쫙~ 감소시켜서 그 이후에 교환을 하는 식이 베스트다.

 

low와 high가 서로를 넘어선 경우이다. 이 경우에는 더 진행해도 (row의 입장에서)pivot보다 작은 값이, (high의 입장에서)pivot보다 큰 값이 나올리가 없기 때문이다. -> 우리는 지금 pivot을 기준으로 작은 값들을 왼쪽으로 몰아왔고, 큰 값들을 오른쪽으로 몰아왔다. 눈으로 잘봐라.

그러면 이제 몰려있는 곳의 경계가 있을 것이다. 3과 6 사이이다. 그 사이에 pivot 값을 넣고 뒤에 값들을 하나씩 땡기고 할 것 없이 high의 값과 pivot의 값을 바꾸면 정확하게 맞아떨어진다. 

pivot 기준으로 왼쪽은 pivot보다 작은 값. 오른쪽은 pivot보다 큰 값.

개쩐다.. 5가 고정 되었다. 이걸 재귀로 왼쪽편, 오른쪽 편 쫘르륵 실행해주면 알아서 각각의 pivot들이 제 자리를 찾아 정렬된 결과를 딱 보일 수 있을 것이다. 

이런 방법을 어떻게 생각했단 말인가 진짜..

코드 및 실행 결과

----

 
#include <stdio.h>
 
void SwapData(int* lval, int* rval)
{
    int temp;
    temp = (*lval);
    (*lval) = (*rval);
    (*rval) = temp;
    return;
}
void ShowArrayArea(int arr[], int begin, int end)
{
    int i = 0;
    for (i = begin; i <= end; i++)
        printf("%d ", arr[i]);
    fputc('\n', stdout);
    return;
}
int Partition(int arr[], int left, int right)
{
    int row = left + 1, high = right; // 1개일 때에는 이 부분 때문에 그냥 한 개에 해당하는 인덱스가 반환됨.
    int pivot = left;
 
    printf("타겟 범위 내 값 나열 : \n");
    ShowArrayArea(arr, left, right);
 
    while (row <= high) // while ((high - row) > 0)
    {
        while (arr[row] <= arr[pivot] && row <= right) // <= 와 && 이후 조건인 이유는 동일한 값들이 왔을 때 처리를 위함. 
            row++;
        while (arr[high] >= arr[pivot] && high >= (left+1)) // >= 와 && 이후 조건인 이유는 동일한 값들이 왔을 때 처리를 위함.
            high--;
 
        if (row <= high)
            SwapData(&arr[row], &arr[high]);
    }
    SwapData(&arr[high], &arr[pivot]);
    return high;
}
void QuickSort(int arr[], int left, int right)
{
    if (left <= right) 
    {// 재귀의 탈출 조건 -> right가 left를 역행하면 진행하면 안됨. left와 right가 동일할 때 1개 요소 레벨이기 때문에.
        int pivot = Partition(arr, left, right);
        QuickSort(arr, left, pivot - 1);
        QuickSort(arr, pivot + 1, right);
    }
    return;
}
 
int main(void)
{
    int arr[9] = { 19, 18, 15, 13, 1, 5, 8, 2, 9 };
    // int arr[9] = { 5,5,5,5,5,5,5,5,5 };
    int i = 0;
 
    QuickSort(arr, 0, 8);
 
    for (i = 0; i < 9; i++)
        printf("%d ", arr[i]);
    fputc('\n', stdout);
    return 0;
}

----

QuickSort 함수에서 ' if (left <= right) ' 이 조건! 이 조건은 위 퀵 정렬 과정에서 row와 high 가 서로 넘어서는 경우와는 완전 다른 조건이다. 해당 조건은 쪼개짐의 범위에 대한 조건으로 left와 right가 서로를 넘어서는 것은 이미 요소 하나 단위까지 쪼개고 난 이후라는 의미이다.

잘 정렬되었다. 

병합 정렬에서 재귀에 대해 한 번 설명을 써본 탓에 이번엔 정신이 온전하다.

퀵 정렬의 성능

퀵 정렬의 빅오는 pivot을 어떤 것을 선택하느냐에 따라서 다르다. 잘 선택한 경우

최선의 경우 : O(n log 2 n) - 2는 아래 첨자 2이다.
최악의 경우 : O(n^2) 

최선의 경우를 잘 뽑도록 pivot을 데이터 세트의 특성 상 잘 뽑아야하고, 데이터의 이동이 적기 때문에 매우 효율적이고 빠른 알고리즘이라고 생각하면 되겠다.