[ 정렬 ] 퀵 정렬(Quick Sort) (C++)

이번 글에서는 Quick Sort에 대해서 다뤄보겠다.

퀵 정렬은 주어진 배열을 일정한 기준(Pivot)에 따라서 더 큰 값과 더 작은 값으로 나누는 것의 반복이다.

재귀를 이용해서 구현하게 되며 일반적으로 Pivot에 따라 더 큰 값과 더 작은 값으로 나누는 Partition() 함수와 이를 반복하기

위한 QuickSort() 함수 2개로 구현된다.

각각의 함수에서의 하는 일과 진행과정을 구체적으로 알아보자.

1. Partition 함수

- Partition함수는 사용자가 설정한 특정 값을 기준으로 그 값보다 더 큰값과 더 작은 값으로 나누는 과정을 반복한다.

  이 때, 기준으로 삼을 특정한 값은 이 값으로 정하세요 ! 라는 기준이 없고 사용자의 마음이다.

  본인 같은 경우 항상 제일 왼쪽의 값을 항상 기준 값으로 설정한다.

  구체적으로 어떤 변수들을 이용해서 어떻게 나누는지 알아보자.

  먼저, 필요한 함수로는 3개가 있다.

   1. 기준 값(Pivot Value)

   - 기준 값으로 삼을 값이 저장되어 있는 Index번호를 저장해 두는 변수이다.

   - 모든 값은 이 값과 비교를 하게 된다.

   2. 비교 값(Store_Index)

   - 퀵 정렬 실행 시, Pivot값을 기준으로 비교를 하지만, Pivot값은 마지막 과정에서 바뀔 때만 사용될 뿐, 중간 과정에서의

     swap은 임시 저장한 이 Index값을 이용해서 해준다. 구체적인 부분은 아래에서 계속 설명할것이니 일단 이정도만 이해

     하도록 하자.

   3. 탐색 하는 값(i)

   - Pivot Value와 이 값을 이용해서 비교를 하면서 swap은 Store_Index와 하는 형식이다.

  

   Partition함수의 진행과정은 다음과 같다. (본인은 Pivot값 설정은 항상 제일 왼쪽 값 & 오름차순 기준)

   Partition함수는 int형으로 반환형으로 int형을 해줘야 하고, 매개변수로 (Left와 Right)값을 호출한다.

   1. 초기상태. Pivot_Value값과 Store_Index값 모두 'Left'값으로 설정.

   2. Left+1 부터 Right까지 탐색. 이 때 탐색에서 쓰이는 변수가 위에서 말한 3번 변수.

   3. 만약, Arr[Pivot_Value] > Arr[i] 인 배열의 값을 만날 경우,

      1) Store_Index 를 1 증가시킨다.

      2) Arr[i]와 Arr[Store_Index]를 swap !

   4. 탐색이 모두 끝난 경우, Arr[Pivot_Value]와 Arr[Store_Index]를 swap !

   5. Pivot_Value= Store_Index로 값 갱신 후 Pivot Value 값 return !

   무슨 소리인지 하나도 모르겠다. 본인조차 모르겠다. 그림을 통해서 위의 과정을 이해해 보도록 하자.

  

   위와 같은 배열이 존재한다. 현재 Partition함수는 (0, 4) 로 호출되있으며 이 값이 의미하는 것은

   Left = 0 , Right = 4 로, 0번 Index부터 4번Index까지 Pivot값을 기준으로 큰 값과 작은 값으로 나누겠습니다. 라는 걸

   의미한다.

   초기상태의 Pivot_Value = 0 (Left이므로, 0번Index. 즉, '7'의 값이 기준 값. 기준 Pivot = 0)

   Store_Index = 0 (처음에는 Pivot_Value와 같은 Index 번호를 가짐)

   i = 1 (1부터 4까지 탐색하기 위한 변수)

   지금부터 Pivot_Value = 빨강색 동그라미, Store_Index = 주황색 동그라미, i = 파랑색 동그라미 로 표현해보겠다.

  

    항상 생각하자. 비교는 'Pivot_Index'와 , Swap은 'Store_Index'와 ! 그리고 Swap하기 전 Store_Index++ 하기 !

    Arr[Pivot_Index]와 Arr[i]를 비교한다. 즉 '7'과 '4'를 비교한다. '4'가 더 작기 때문에 Swap이 일어나야한다.

    Swap이 일어나기전에? Store_Index++ 시켜주기 ! 그리고 Swap ! 하게 되면 다음과 같아진다.

   

     사실상, Arr[1]과 Arr[1]을 비교한 꼴이 되어서 값의 변동이 일어나진 않지만, Store_Index값에는 변화가 생겼다.

     이어서 탐색을 진행해보자.

     탐색을 진행하기 위해 i 값이 ++될 것이다.

  

      Arr[Pivot_Value]와 Arr[i]를 비교해본다. 즉, 7과 8을 비교해본다. 8이 더 크기 때문에 Swap이 일어나지 않는다.

      계속 탐색을 위해서 i값을 ++ 시켜주자.

  

     Arr[Pivot_Value]와 Arr[i]의 값을 비교해본다. 7과 15이므로 15가 더크기 때문에 Swap이 일어나지 않는다.

     계속 탐색을 위해서 i값을 ++ 시켜주자.

    

     Arr[Pivot_Value]와 Arr[i]를 비교해본다. 7과 2를 비교했을 때, 2가 더 작으므로 Swap이 일어나야한다.

     하지만! 그 전에 Store_Index++해주기. Store_Index를 ++해준 후, Swap을 하게 되면 다음과 같아진다.

    

     이제 i값이 Right까지 왔으므로 탐색이 끝났다. 하지만, 배열의 상태가 어떻게 보더라도 정렬이 되어 있지 않다.

     우리가 지금 이 과정을 왜 했을까??? 우리가 지금까지 한 과정은 정렬을 하기 위한 과정이 아니었다.

     단지, 내가 사용한 기준값인(Pivot_Value) 7보다 더 큰값과 작은 값으로 나눠주기 위한 과정이었다.

     하지만, 7보다 더 큰값과 작은값으로도 나뉘지 않았다.

     따라서, 마지막으로 한 가지 과정을 더 추가해줘야 한다.

     바로, Store_Index와 Pivot_Value의 값을 Swap 해주고 Pivot_Value의 값을 갱신해 주는 것 !

     무슨 소리일까?? 일단 말 그대로 한번 해보자.

    

     말 그대로 했더니 Pivot_Value의 값이 0에서 2가 되었고, 배열의 상태가 위와 같이 되었다.

     즉, 7을 기준으로 더 작은 값은 7보다 앞에, 7을 기준으로 더 큰 값은 7보다 더 뒤에 가게 되었다.

     우리는 이 과정을 계속해서 반복할 것이다.

     그렇다면 이 다음 과정은 무엇일까?? 아마도, 7보다 이전에 있는 값들을 위와 같은 방식으로 정렬하는 것과

     7보다 이후에 있는 값들을 위와 같은 방식으로 정렬하는 것일 것이다. 그렇다면 7보다 이전에 있는지 이후에 있는지는

     어떻게 판단해줘야할까??

     처음에 말했지만 Partition 함수는 int형 함수로써, return값이 필요하다. 즉, return Pivot_Value를 해주면

     위의 경우 '2'가 return 될 것이다. '7'이 2번Index에 위치하기 때문에 !

     그렇다면 이 후 과정은 어떻게 될까?? 바로 (Left부터 Pivot-1)까지, (Pivot+1부터 Right)까지 위의 과정을 재귀호출을

     해주면 되는 방식인 것이다.

     이렇게 진행되는 것이 Quick 정렬이다. Quick Sort의 재귀호출부분은 다음과 같이 구현된다.

void QuickSort(int Left, int Right)
{
    if (Left < Right)        // Left >= Right인 경우, 데이터가 0개이거나 1개 있다는 말. 즉 정렬이 필요 없는 순간.
    {
        int Pivot = Partition(Left, Right);    // Pivot을 Partition함수를 통해서 return 받음.
        QuickSort(Left, Pivot - 1);              // Left부터 Pivot-1까지 재귀호출
        QuickSort(Pivot + 1, Right);            // Pivot+1부터 Right까지 재귀호출
    }

}

# 시간복잡도

- 그렇다면 퀵정렬의 시간복잡도에 대해서 알아보자. 물론 지금 말하는 시간복잡도는 정말 이상적으로, 특정 Pivot을 골랐을

   때, 그 Pivot값을 기준으로 정확하게 반으로 나눠진 경우의 시간복잡도이다.

   만약 배열이 8칸이 있다고 생각해보자. 그렇다면 다음과 같이 Pivot을 기준으로 나뉘게 될 것이다.

  

     위의 그림과 같이 총 3번을 나누게 될것이다. 그렇다면 한번 식을 세워보자.

     8칸 = 3번나눌수있다... 즉, 나누는 횟수 으로 둘 수 있다.

     그렇다면 각 단계에서는 몇번씩 일어날까?? 처음 8칸일 때는 바로 8번 비교하는 연산이 일어날 것이다. 즉 N번 연산.

     두 번째 4칸, 4칸으로 나눠진 단계에서는 N/2 번연산 + N/2 번연산 = N번 연산.

     세 번재, 2칸, 2칸, 2칸, 2칸으로 나눠진 단계에서는 N/4 + N/4 + N/4 + N/4 번 연산으로 N번연산.

     마지막 1칸으로 나눠졌을 때는 더 이상 비교 대상이 없으므로 연산이 일어나지 않는다.

     즉, N번연산이 나눠진 횟수 만큼 일어난다는 것을 알 수 있다. 그림으로 나타내면 다음과 같다.

   

     따라서 시간표기법 빅오로 나타내게 되면 으로 표기할 수 있다.

     위에서 N번 연산이 아니라 N - 1번 연산 아닌가? 라는 생각이 들 수 있지만 빅오 표기법으로 계산하게 되면 상수들을

     모두 빼고 계산하기 때문에 대략적으로 위와 같은 계산이 가능하다.

     하지만 ! 언제까지나 위와 같은 방법은 이상적으로 Pivot을 선택했을 때, 정확하게 반으로 갈라진다는 조건일 때이다.

     다음과 같은 배열을 한번 생각해보자.

    

     이 때, Pivot을 Random적으로 골랐는데 하필 0이 나왔다. 그러면 어떻게 될까???

    

      이렇게 0에 대해서는 더 이상 정렬이 필요하지 않고, 나머지에 대해서 Pivot을 다시 설정할 것이다. 그 다음 단계로 Pivot

      을 또 골랐는데 하필 ! 1이 나왔다... 그렇게 되면 어떻게 될까..??

     

     또 이런식으로 배열이 나뉘게 될 것이다. 이 다음 상황도 최악으로 Pivot을 2, 3, 4, 5, 7을 순서적으로 골랐다고 생각해

      보자. 이 경우에는 시간복잡도가 어떻게 될까??

      가장 처음에 0을 기준으로 탐색을 하기 위해서 총 N - 1번 탐색, 두 번째 1을 기준으로 N - 2번 탐색, 세번째는

      N - 3번.... 이런식으로 진행될 것이다. 즉, (N - 1) + (N - 2) + (N - 3) + ... + 1이 될 것이다.

      이를 식으로 나타내면 N(N-1) / 2가 되고 빅오 표기법으로 써보면 이 된다.

      즉, 퀵 정렬은 최악의 경우와 일반적인 경우 혹은 최선의 경우 시간 복잡도가 달라지는 정렬 방식이다 !

     

[ 소스코드 ]

#include<iostream>
#include<cstdlib>
#include<algorithm>
 
#define MAX 100
using namespace std;
 
int Arr[MAX];
bool Flag[10000];
 
void Print()
{
    cout << "##########################################################################################################" << endl;
    int Cnt = 0;
    for (int i = 0; i < MAX; i++)
    {
        printf("%3d ", Arr[i]);
        Cnt++;
        if (Cnt == 20)
        {
            Cnt = 0;
            cout << endl;
        }
    }
    cout << "##########################################################################################################" << endl;
    cout << endl;
}
 
int Partition(int Left, int Right)
{
    int Pivot_Value = Left;
    int Store_Index = Pivot_Value;
 
    for (int i = Left + 1; i <= Right; i++)
    {
        if (Arr[Pivot_Value] > Arr[i])
        {
            Store_Index++;
            swap(Arr[i], Arr[Store_Index]);
        }
    }
    swap(Arr[Pivot_Value], Arr[Store_Index]);
    Pivot_Value = Store_Index;
 
    return Pivot_Value;
}
 
void QuickSort(int Left, int Right)
{
    if (Left < Right)
    {
        int Pivot = Partition(Left, Right);
        QuickSort(Left, Pivot - 1);
        QuickSort(Pivot + 1, Right);
    }
}
 
int main(void)
{
    for (int i = 0; i < MAX; )
    {
        Arr[i] = rand() % 300 + 1;
        if (Flag[Arr[i]] == false)
        {
            Flag[Arr[i]] = true;
            i++;
        }
    }
    cout << "[ Initialize Array State ]" << endl;
    Print();
 
    QuickSort(0, MAX - 1);
    cout << "[ After Sorting Array State]" << endl;
    Print();
 
    return 0;
}