[python] Quick Sorting 퀵 정렬 Hoare(호어), Lomuto(로무토) 분할 정복을 사용한 정렬 알고리즘

Quick Sorting 

퀵 정렬이란 Charles Antony Richard Hoare가 개발한 정렬 알고리즘으로 다른 원소와의 비교만으로 정렬을 수행하는 분할 정복 알고리즘이다. 평균적으로 다른 정렬알고리즘보다 수행속도가 매우 빠르기 때문에 퀴 정렬이라고 한다. 

퀵 정렬의 정렬 과정을 설명하면 다음과 같다.

1. 배열 중에 임의의 데이터를 pivot으로 선택한다.
2. 배열에 있는 데이터들을 pivot 보다 작은 데이터 그룹은 왼쪽으로 pivot보다 큰 데이터 그룹은 오른쪽으로 나눈다. 
3. pivot을 중심으로 왼쪽과 오른쪽으로 나누어진 두 그룹에 대해 재귀를 통해 위의 과정을 반복한다.
4. quick sort가 반복 호출 되면서 정렬이 완료된다. 

 

 

퀵 정렬은 Top-down방식으로 구현되며, 평균 시간 복잡도는 O(nlogn)이고 worst case는 O(N^2)이다. 

worst

또한 quick sort는 Stable하지 않고 In-place 하지 않다는 특징을 가지고 있다. 

 

퀵 sort에서는 pivot을 고르는 방식과 partition을 하는 방법에 따라 여러 변형이존재한다. 

 

Pivot 데이터 선택하는 방법들 

1. 가장 왼쪽에 있는 데이터를 선택한다. 
2. 랜덤하게 선택하여 가장 왼쪽으로 보낸다. 
3. 가장 왼쪽, 가장 오른쪽, 중앙에 있는 세 데이터 중에 크기가 중간인 데이터를 선택하고 가장 왼쪽에 있는 데이터와 교환

이 3가지 방법 중에서 3번째 방법을 제일 많이 사용하는데, 이 방법을 median - of - three라고 한다. 따라서 오늘 소개하는 quick sort는 모두  median - of - three기법으로 pivot을 선택한다고 가정한다. 

 

partition기법으로는 Tony Hoare와 Nico Lomuto의 방법을 가장 많이 사용하는데 두 방식 모두 평균적인 시간복잡도는 O(nlogn)이지만 worst case는 O(n^2)이다. 

 

Lomuto(로무토)의 partition 기법

Lomuto방식을 다음과 같다. 

1. pivot값 보다 큰 값들은 오른쪽으로, 작은 값들은 왼쪽 보낸다. 
2. pivot 값을 두 집합의 가운데에 위치시킨다. 

초기상태

pivot: 배열의 제일 왼쪽값

j : 제일 왼쪽값 

i : j + 1

 

/* 초기값 */
pivot = a[left]; /* pivot에 배열의 제일 왼쪽값 넣어줌 */ 
j = left;  /* j도 제일 왼쪽부터 시작 */

for (i = left + 1; i <= lenght; i++)  /*i는 j+1부터 배열 끝까지 순환*/
{
	/* 값이 피봇보다 작다면 swap을 진행 */
	if(a[i] <= pivot) 
    {
    	j++;
        /* swap */  
        tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

 

Case 1 :

i가 가리키는 값이 pivot보다 크면 그냥 넘어감

 

 

 

Case 2 : 

i가 가리키는 값이 pivot보다 작으면 swap 진행

 

위의 두 과정을 반복하면 왼쪽에는 pivot보다 작은 값 오른쪽에는 pivot보다 큰 값들이 자연스럽게 모이게 된다. 

그러면 처음에는 아래의 그림과 같이 되어있던 배열이 ....

 

마지막 step에서는 pivot을 기준으로 나누어지게 된다. 

/* pivot을 중심으로 큰값 작은 값들이 나누어지면 
마지막에 pivot을 자기자리로 swap해준다. */
pivotPos = j;
tmp = a[left];
a[left] = a[pivotPos];
a[pivotPos] = tmp;

이렇게 pivot을 기준으로 오른쪽 왼쪽 나누어져있다면, 마지막으로 제일 왼쪽에 있던 pivot을 pivot보다 작은 그룹의 제일 오른쪽에 있는 값과 swap을 해준다. 

 

 

그러면 이렇게 pivot은 자신의 자리를 찾아가게 된다. 

 

그 다음부터는 이 과정을 큰 쪽 작은 쪽 모두 반복적으로 수행하면 정렬이 완료된다. 

 

숫자로 살펴보면 다음과 같다. 

 

 

Hoare(호어)의 partition 기법

Hoare의 방식은 다음과 같다.

 

배열이 a라고 할 때, 

1. a[j]가 pivot값 보다 작으면 a[i]의 값과 a[j]의 값을 swap한다. 
2. pivot 값을 두 집합의 가운데에 위치시킨다. 

초기상태

pivot: 배열의 제일 왼쪽값

j : 배열의 끝 index

i : 시작 Index -1

 

def partition(int a[], int low, int high){
	// 초기값 설정
    int i, j;
    int pivot;
	
    pivot = a[low];  // pivot은 제일 왼쪽에 

    i = low - 1; //시작 인덱스 -1
    j = high + 1; // 끝 인덱스 +1

    while (true){
        while(a[++i] < pivot); // pivot 보다 값이 작다면 계속 증가
        while(a[--j] > pivot); // pivot 보다 값이 크다면 계속 감소 
        
        // sawp을 통해 교환
        if(i<j)
            swap( a[i], a[j]);
        else
            return j;
    }
}

 

 

 

Case 1 

a[i]가 pivot 보다 작다면 i 계속 증가

a[j]가 pivot 보다 크다면 j 계속 감소

 

 

 

Case2

a[i]가 pivot 보다 크다면 while 문 stop

a[j]가 pivot 보다 작다면  while 문 stop

 

 

이때 i가 j보다 작다면 a[i]와 a[j]의 위치를 swap한다. 

위의 과정을 계속 반복하다가 i가 j보다 커진다면 j를 return 한다.

 

Hoare방식을 전체적으로 나타내면 아래와 같다.