퀵 정렬(Quick Sort) 동작 - 까먹지 않도록 하기 위한 방법..

퀵 정렬 동작을 까먹지 않도록 하기 위해 퀵정렬의 느낌과 동작을 정리를 해보았다. (오름 차순 기준)

퀵 정렬의 전체적인 그림은 배열에서 pivot이라는 기준을 정하고, 그 기준으로 왼쪽 영역은 pivot보다 더 작은(같거나) 원소들이 놓이도록, 오른쪽 영역은 더 큰(같거나) 원소들이 놓이도록 하는 것이다. 왼쪽 오른쪽 영역이 정렬되어 있을 필요는 없다. 그냥 pivot을 기준으로 크기가 작거나 크면된다.

이후엔 나뉜 왼쪽과 오른쪽 영역에 대해 다시 재귀적으로 quicksort를 진행한다. 그러면 왼쪽 영역에서 또 pivot을 정하고 영역을 나눌 것이고, 오른쪽 영역에 대해서도 마찬가지일 것이다. 이는 왼쪽 영역과 오른쪽 영역이 더 이상 나뉘지 않을 때, 즉 나누려는 영역이 1개이면 리턴한다.

이를 코드로 표현하면 다음과 같다.

void QuickSort(int array[], int left, int right)
{
    if(left < right)
    {
    	int pivotIndex = Partition(array, left, right);
        
        QuickSort(array, left, pivotIndex - 1);
        QuickSort(array, pivotIndex + 1, right);
    }
}

 

 pivot을 선정하는 기준은 여러가지가 있으므로 대략적인 동작만 정의

int Partition(int array[], int left, int right)
{
    // pivot 선정
    
    // pivot을 기준으로 왼쪽에 더 작은 값들만 존재하도록 배열
    
    // 자연스레 pivot을 기준으로 오른쪽은 더 크거나 같은 값들만 존재하게 됨
    
    // pivot의 위치를 반환
}

 

항상 맨 오른쪽의 값을 pivot으로 선정하는 코드를 예로 들면 다음과 같음

int Partition(int array[], int left, int right)
{
    // pivot 선정
    int pivot = array[right];
    
    // pivot을 기준으로 왼쪽에 더 작은 값들만 존재하도록 배열
    int j = left;
    for(int i = left; i < right; ++i) // pivot이 [right]에 존재하므로 이를 제외한 모든 영역을 검사
    {
        if(array[i] < pivot) // pivot보다 작은 값은 그냥 왼쪽으로 미룬다.
        {
            swap(array[i], array[j]);
            ++j;
        }
    }
    
    // 자연스레 pivot을 기준으로 오른쪽은 더 크거나 같은 값들만 존재하게 됨
    int prevPivotPos = right;
    int newPivotPos = j;
    swap(array[newPivotPos], array[prevPivotPos]);
    
    // pivot의 위치를 반환
    return newPivotPos; 
}

위 코드에서 하려는 동작을 설명하면 다음과 같다.

오른쪽 값을 pivot으로 선정한다. pivot 이전의 각 원소들을 pivot과 비교한다. 만약 pivot보다 크거나 같다면 아무 동작도 하지 않고 다음 원소로 넘어간다. 만약 pivot보다 작다면 [j] 원소와 swap한다. j의 역할을 말로 설명하기가 좀 애매하다.

j는 최종적으로 pivot보다 작은 원소들이 모여있는 영역에서 가장 오른쪽의 위치를 가리키게 된다. 이 위치 이후부터는 pivot보다 작은 값이 존재하지 않는다. 따라서 마지막에 j를 pivot의 위치로 변경함으로써 pivot의 왼쪽엔 모두 pivot보다 더 작은 값, 오른쪽엔 더 크거나 같은 값들이 되도록 하는 것이다.