챕터5-3. 정렬 | 퀵 정렬(Quick Sort) - Hoare(호어) / Lomuto(로무토) 분할 알고리즘

개념

- 병합정렬 처럼 두 부분으로 쪼개어지는 것은 동일하나 Pivot item이 존재하여 이를 기준으로 나뉘어진다.
   이를 기준으로 나눌 때 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시키게 된다.
   또한, 병합정렬과 다르게 병합과정이 존재하지 않는다.
- 분할 알고리즘을 무엇으로 사용하느냐, 그리고 피봇값을 무엇으로 하느냐에 따라 효율이 크게 달라진다.
- Top-down 방식으로(재귀) 구현됨
- 평균 시간복잡도는 O(nlogn), 최악의 경우 O(N^2)

시간복잡도

* 분할 방법에 따라 Hoare(호어), Lomuto(로무토) 방법이 존재함.

* 위 두 방식 모두 평균적인 시간복잡도는 O(NlogN) 이지만 최악의 시간복잡도는 모두 O(N^2)이 될 수 있음.

* 특정 상황에 의해서 Hoare(호어)방식이 더 효율적임 이유는 아래 참고.

* 일반적으로 피봇값이 레코드들의 중간 값으로 채택되면 효율이 높아지게 되는데 
   간단한 방법으로 피봇값을 '맨 왼쪽, 중간, 맨 오른쪽' 3개의 값 중에서 중간 값을 선택하여 이를 아래 그림의 Pivot 위치와
   swap해준 뒤 정렬하는 것을 통해 최상의 피봇값 지정을 함으로써 효율을 높일 수 있다.

 

# 둘 중 뭐가 더 유리한가
- Hoare Partiton 방식이 더 유리하다. 평균적으로 swap을 3배이상 덜 발생시키기 때문이다. 
   배열의 모든 인자가 같은 수 일 경우에 모든 짝에 대해 swap을 발생시키기는 하지만 i와 j가 교차하는 순간 그만두기 때문에
   O(NlogN)의 시간복잡도를 유지한다. 또한, 배열이 이미 정렬된 상태라면 한번도 swap을 일으키지 않는다.
   이와 대조적으로 lomuto방식은 구현이 상대적으로 쉽지만 배열의 모든 인자가 같은 수이거나 이미 정렬된 배열에 대해 
   swap을 끝까지 계속 발생시키기 때문에 시간복잡도가 O(N^2)이 된다.

 

# 최악의 시간복잡도 O(N^2)가 되는 경우
@ Hoare Partition 방식
- 피봇의 값을 맨 왼쪽의 값으로 채택하는 경우, 레코드들 중 최소값이 피봇으로 선택되면 분할이 안일어나 
   다른 정렬 알고리즘과 다를게 없어지므로 효율이 떨어져 시간복잡도 O(N^2)이 될 수 있다.
   (피봇을 맨 오른쪽 값으로 채택하는 경우는 그 반대)

 

@ Lomuto Partition 방식
-  모든 인자가 같은 수이거나 이미 정렬된 배열일지라도 swap을 계속 발생시키기 때문에 시간복잡도가 O(N^2)이 될 수 있다.
- Hoare Partition 방식과 마찬가지로 피봇의 잘못된 선택으로 분할이 안일어나면 효율이 떨어지게 됨.

그림으로 이해하는 정렬 과정

# Hoare(호어) Partition(분할) 방법을 사용한 퀵 정렬

- 1) 피봇 값보다 큰 값들은 오른쪽, 작은 값들은 왼쪽 집합에 위치시킴(아래에서 i와 j가 교차했을 때가 이것이 완성된 때임)
- 2) 피봇 값을 두 집합의 가운데에 위치시킴(아래서 i와 j가 교차했을 때 피봇의 값과 j의 위치와 swap해주는 것)
'2)' 과정을 거친 피봇 값은 다음 정렬 과정에서 제외되며, 피봇 값이 위치한 곳은 정렬된 상태일 때 자기가 있어야 할 위치에 놓임

 

@ 초기상태

@ 이후동작

# Lomuto(로무토) 분할 방법을 사용한 퀵 정렬

* Hoare 방식과 가장 큰 차이점은 i와 j가 모두 증가하는 방식이라는 것이다.

- 1) 피봇 값보다 큰 값들은 오른쪽, 작은 값들은 왼쪽 집합에 위치시킴
- 2) 피봇 값을 두 집합의 가운데에 위치시킴(아래에서 j가 끝까지 진행되었고, i+1와 피폿값이 swap 될 때 이것이 완성된 때임)
'2)' 과정을 거친 피봇 값은 다음 정렬 과정에서 제외되며, 피봇 값이 위치한 곳은 정렬된 상태일 때 자기가 있어야 할 위치에 놓임

 

@ 초기상태

@ 이후동작

 

구현코드

# C++(lomuto partition 알고리즘 이용)
- https://www.geeksforgeeks.org/hoares-vs-lomuto-partition-scheme-quicksort/
- 위의 링크를 참고한다면 Hoare partition 알고리즘을 이용한 구현도 해볼 수 있다.

#include <iostream>

using namespace std;

int a[1000000];

void swap(int &x, int &y) 
{
    int z = x;
    x = y;
    y = z;
}

int choosePivot(int low, int high) 
{
    return low + (high-low)/2; // 중간 index 반환
}

/* i와 j가 모두 증가하는 Lomuto Partition방식의 구현으로 swap을 진행하고 분할기준점을 반환함*/
int partition(int low, int high) 
{
    int pivotIndex = choosePivot(low, high); // 피봇을 레코드에서 그냥 중앙에 위치한 값으로 지정해 줬는데 이 함수를 수정하면 내가 원하는 방식대로 지정 가능
    int pivotValue = a[pivotIndex];
    
    swap(a[pivotIndex], a[high]);
    
    int storeIndex = low;                    // 블로그에 필기해둔 거에서 i의 역할
    
    for (int i=low; i<high; i++)             // 블로그에 필기해둔 거에서 j의 역할
    {
        if (a[i] < pivotValue) 
        {
            swap(a[i], a[storeIndex]);
            storeIndex += 1;
        }
    }
    
    swap(a[storeIndex], a[high]);            // 이때 피봇이 옮겨진 자리가 정렬이 되어 고정된 자리.
    
    return storeIndex;                       // 피봇이 옮겨진 자리의 Index값을 반환함
}

/* 한번 일단 partition알고리즘(정렬 + 분할기준점얻기)을 수행한 뒤 기준점을 얻고 좌우에 대해 재귀적으로 실행*/
void quicksort(int low, int high) 
{
    if (low < high) 
    {
        int pivot = partition(low, high);
        quicksort(low, pivot-1);            // 피봇이 옮겨진 자리를 기준으로 왼쪽 정렬
        quicksort( pivot+1, high);          // 피봇이 옮겨진 자리를 기준으로 오른쪽 정렬
    }
}

int main() 
{
    int n;
    cin >> n;
    for (int i=0; i<n; i++)
        cin >> a[i];
    
    quicksort(0, n-1);
    
    for (int i=0; i<n; i++)
        printf("%d\n",a[i]);
}