자료구조 :: 퀵 정렬 Quick sort (c/c++ 구현)

퀵 정렬 (Quick sort)

특정한 값(Pivot)을 기준으로 큰 숫자와 작은 숫자를 구분하자

 

'분할 정복' 알고리즘으로 평균속도가 O(N * logN) 이다.

퀵정렬에는 기준이 되는 값이 존재한다.

이때, 기준값을 피봇(pivot)이라고 부른다.

 

맨 앞의 숫자 4를 pivot으로 설정한다.

 

i, j 포인터를 설정한다.

 

i는 피봇을 제외한 처음 원소부터 피봇보다 큰 값을 찾는다.

피봇보다 큰 값은 8이다.

 

j는 끝에서부터 피봇보다 작은 값을 찾는다.

피봇보다 작은 값은 1이다.

 

1과 8을 바꾼다. (i번째와 j번째를 바꾼다.)

 

다시 i는 피봇보다 큰값을, j는 피봇보다 작은 값을 찾는다.

찾는도중에 i > j 가 되었다. (엇갈렸다.)

이럴 경우는 i와 j를 바꾸는 것이 아니라

피봇과 j를 바꾼다.

 

 

바꾸게 되면, 피봇(4)의 좌측으로는 피봇보다 작은값들만 존재하게 된다.

반대로 피봇(4)의 우측으로는 피봇보다 큰 값들만 존재하게 된다.

 

분할정복 알고리즘을 통해

피봇을 기준으로 좌측과 우측에서 각각 다시 퀵 정렬을 수행한다.

 

이렇게 분할정복 알고리즘을 사용하기 때문에 빠른 속도로 정렬을 수행할 수 있다.

 

#include <stdio.h>
 
int data[10] = {4, 1, 2, 3, 9, 7, 8, 6, 10, 5};
 
void quick_sort(int *data, int start, int end){
    if(start >= end){
        // 원소가 1개인 경우
        return; 
    }
    
    int pivot = start;
    int i = pivot + 1; // 왼쪽 출발 지점 
    int j = end; // 오른쪽 출발 지점
    int temp;
    
    while(i <= j){
        // 포인터가 엇갈릴때까지 반복
        while(i <= end && data[i] <= data[pivot]){
            i++;
        }
        while(j > start && data[j] >= data[pivot]){
            j--;
        }
        
        if(i > j){
            // 엇갈림
            temp = data[j];
            data[j] = data[pivot];
            data[pivot] = temp;
        }else{
            // i번째와 j번째를 스왑
            temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }
    } 
    
    // 분할 계산
    quick_sort(data, start, j - 1);
    quick_sort(data, j + 1, end);
}
 
int main(void){
    quick_sort(data, 0, 9);
    
    // 결과 확인
    for(int i=0; i<10; i++){
        printf("%d ", data[i]);
    }
    
    return 0;
}

 

핵심1.

피봇을 설정하고,

data[i] > data[pivot]이고, data[j] < data[pivot]인 i, j를 구한다.

 

핵심2.

i > j 처럼 엇갈린경우, 피봇과 j를 스왑한다.

i <= j 이고, data[i] > data[pivot] 이고 data[j] < data[pivot] 인 경우 data[i]와 data[j]를 스왑한다.

 

핵심3.

재귀 함수를 이용해서, 분할 알고리즘을 실행한다.

 

 

퀵정렬의 평균적인 시간복잡도는 O(N * logN)

하지만, 최악의 경우 O(N^2)의 시간복잡도를 갖는다.

(1 2 3 4 5 6 7 8 9 10 의 경우처럼 이미 정렬이 되어 있는경우, 분할 정복 알고리즘이 활용이 안됨)

 

참고

만약 오름차순이 아니라

내림차순으로 정렬하고 싶다면...

while(data[i] <= data[pivot]){
    i++;
}
while(data[j] >= data[pivot] && j > start){
    j--;
}​

윗 부분에서 while문의 부호만 바꿔주면 된다.

 

while(data[i] >= data[pivot]){
    i++;
}
while(data[j] <= data[pivot] && j > start){
    j--;
}
​

위와같이 하면 내림차순으로 정렬이 된다.

 

관련 글

2018/04/28 - [Algorithm] - 자료구조 :: 선택정렬 Selection sort (c/c++ 구현)

2018/04/28 - [Algorithm] - 자료구조 :: 버블정렬 Bubble sort (c/c++ 구현)

2018/04/28 - [Algorithm] - 자료구조 :: 삽입정렬 Insertion sort (c/c++ 구현)

2018/04/29 - [Algorithm] - 자료구조 :: 병합정렬 Merge sort (c/c++ 구현)