Quick Sort - 퀵 정렬과 코드

앞서 다른 정렬들은 영어부분을 번역해서 "ㅁㅁ정렬" 이렇게 부르던데

퀵소트는 그냥 퀵정렬이라고 부르는부분이 약간 웃기다.

 

퀵정렬은 분할 정복을 사용한다.

 

1. 배열의 끝에 있는 수를 Pivot으로 설정한다. (기준값)

그리고 맨 처음에 Pivot보다 작은 수를 세기위한 low와 (오름차순)

차례 차례 수를 확인하고 비교하기위한 ptr 을 둔다.

2. ptr에 있는 값과 Pivot값을 비교한다.

오름차순의 경우 ptr값이 더 작으면 low값을 뒤로 한칸 옮긴다.

(++ 그리고 이때 만약 ptr값과 low값이 다르면 두 값을 Swap한다)

비교가 끝나면 ptr을 한 칸 뒤로 옮긴다.

 

3. 계속해서 ptr과 Pivot값을 비교한다.

ptr에 있는 값이 더 크다면  low는 그대로 두고 ptr을 뒤로 옮긴다.

4. pivot과 ptr의 위치가 같다면 비교는 끝난 것이다.

5. Pivot값과 low값을 Swap한다.

low는 pivot값이 있어야할 위치이다. 

low의 앞에는 pivot값보다 작은 값들이 놓이게 되고

low의 뒤에는 pivot값보다 큰 값들이 놓이게 되기 때문이다.

6. 분할하고 앞의 과정을 반복한다.

pivot보다 작았던 그룹 따로, 컸던 그룹따로 분리하여 과정을 반복

나누어진 그룹의 크기가 1보다 작거나 같다면 끝난 것이다.

 

퀵 정렬은 재귀를 이용해서 구현하는게 효과적이다.

이에 대해서 의사코드를 작성해보면 다음과 같다.

QuickSort(start, end, arr[]){
    if(start >= end)
    	return;
    pivot = end;
    low = start;
    ptr = start;
    while(ptr < pivot){
    	if(arr[ptr] < arr[pivot]){
        	if(low != ptr){
            	swap(arr[low], arr[ptr]);
            }
            low ++;
        }
    	ptr ++;
    }
    swap(arr[low], arr[pivot]);
    QuickSort(start, low - 1, arr);
    QuickSort(low + 1, end, arr);
}

 

퀵소트는 최선/평균의경우 시간복잡도 O(NlogN)이고 최악의경우 O(N^2)이다.

 

퀵정렬을 C언어로 표현하면 아래와 같다. 

#include <stdio.h>
#include <string.h>

void swap(int* a, int* b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

//오름차순 정렬
void quick_sort(int start, int end, int arr[]){
    if(start >= end) return;
    int i, pivot = end, low = start, ptr = start;
    while(ptr < pivot){
        if(arr[ptr] < arr[pivot]){
            if(low != ptr){
                swap(&arr[low], &arr[ptr]);
            }
            low ++;
        }
        ptr++;
    }
    if(low != pivot){
        swap(&arr[low], &arr[pivot]);
    }
    quick_sort(start, low -1, arr);
    quick_sort(low +1, end, arr);
}

int main(void)
{
    int i;
    const int N = 5;
    int arr[N];
    for(i = 0; i < N; ++i){
        scanf("%d", arr + i);
    }
    quick_sort(0, N-1, arr);

    for(i = 0; i < N; ++i){
        printf("%d ", arr[i]);
    }
}