퀵 정렬

퀵 정렬은 피벗(pivot)이라 불리는 특정 원소를 기준으로 주어진 원소들을 두 부분으로 나눈 뒤 각 부분을 정렬하는 방식이다. 이때 나뉜 각 부분의 정렬에는 다시 퀵 정렬이 이용된다.

초기의 배열 상태

들어가기 전 용어 설명
 * pivot : 중심점 또는 기준점
 * left : 정렬 대상의 가장 왼쪽을 가리키는 이름
 * right : 정렬 대상의 가장 오른쪽을 가리키는 이름
 * low : 피벗을 제외한 가장 왼쪽을 가리키는 이름
 * high : 피벗을 제외한 가장 오른쪽을 가리키는 이름

초기의 배열 상태에서 용어에 대한 위치

 

① 가장 왼쪽에 있는 원소 50을 pivot으로 정한다.

50이 가장 왼쪽에 있는 원소이기 때문에 pivot이 됨

② low는 오른쪽으로만 이동을 하며 high는 왼쪽으로만 이동을 한다. 이때 이동기준은 아래와 같다.
* low : 피벗보다 큰 값을 만날 때까지 이동
* high : 피벗보다 작은 값을 만날 때까지 이동
위의 방법을 이용하여 이동을 하면 아래의 그림과 같이 이동이 된다. low는 50보다 큰 값인 80을 만날 때까지
이동하였고 high는 50보다 작은 값인 40을 만날 때까지 이동하였다.

low와 high는 이동하여 각각 80과 40의 위치를 가리킴

③ low와 high의 이동이 완료된 후 두 개의 값을 서로 교환한다. 

low와 high의 값을 교환한 결과

④ low와 high의 교환이 완료된 후에도 low는 high보다 값이 커지지 않을 때까지 계속 이동을 한다.
다음 이동 위치와 교환한 위치는 아래의 그림과 같다.

low와 high는 이동하여 각각 60과 10의 위치를 가리키게됨

low와 high의 값을 교환한 결과

⑤ 다음 이동을 하면 low가 high보다 커지는 상황이 발생한다. low가 high보다 값이 같거나 커지는 상황이
발생할 때에는 값을 교환하지 않는다. 이동 및 교환이 완료되었기 때문에 이 상황에서는 high와 pivot을 교환한다.

low와 high의 값보다 커지는 그림

high와 pivot의 교환이 완료된 그림

⑥ 지금까지 설명한 내용이 퀵 정렬의 핵심이다. 바로 위의 그림을 보면 50의 pivot으로 왼쪽에는 50보다 작은 숫자,
오른쪽에는 50보다 큰 숫자들이 정렬되어있다. 이로써 50이라는 숫자는 홀로 정렬이 완성되었다. 

정렬이 완료된 50을 기준으로 ① ~ ⑤ 방법을 이용하여 재귀적으로 풀어나가야함

⑦ 다음 작업으로는 피벗의 왼쪽 부분부터 오른쪽 부분까지 ① ~ ⑤의 방법을 재귀적으로 실행하여 정렬을 완성시키는 것이다.

이제 코드로 퀵 정렬을 구현해보자.

 

#include <iostream>
 
using namespace std;
 
// 원소 개수
#define MAX_LENGTH 10
 
void Swap(int arr[], int index1, int index2)
{
    int temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}
 
int Partition(int* arr, int left, int right)
{
    // pivot, low, high의 위치 설정
    int pivot = arr[left];
    int low = left + 1;
    int high = right;
 
    // left와 right가 교차되지 않을 때까지 순회
    while (low <= high)
    {
        // 피벗보다 큰 값을 찾는 과정
        while (pivot > arr[low])
            low++;
 
        // 피벗보다 작은 값을 찾는 과정
        while (pivot < arr[high])
            high--;
 
        // 교차되지 않은 상태일 경우 값을 교환
        if (low <= high)
            Swap(arr, low, high);
    }
 
    // pivot과 high를 교환
    Swap(arr, left, high);
 
    // 교환된 pivot의 값을 반환
    return high;
}
 
void QuickSort(int* arr, int left, int right)
{
    if (left <= right)
    {
        // 파티션 함수를 이용하여 둘로 나눈다
        int pivot = Partition(arr, left, right);
 
        // 왼쪽 정렬
        QuickSort(arr, left, pivot - 1);
 
        // 오른쪽 정렬
        QuickSort(arr, pivot + 1, right);
    }
}
 
int main()
{
    // 정렬할 배열 선언
    int arr[MAX_LENGTH] = { 50, 30, 80, 60, 20, 10, 40, 100, 70, 90 };
 
    // 퀵 정렬 호출
    QuickSort(arr, 0, MAX_LENGTH - 1);
 
    // 출력 결과 확인
    for (int i = 0; i < MAX_LENGTH; ++i)
    {
        cout << arr[i] << endl;
    }
}