6. 분할과 정복_퀵정렬(Quick Sort)

#퀵 정렬 알고리즘

1. 배열 a에서 pivot을 선택한다.

2. 배열 a를 다음과 같이 분할한다: pivot보다 같거나 작은 수는 pivot의 왼쪽으로, pivot보다 큰 수는 pivot의 오른쪽으로 이동하여 재 배열한다. 

3. 분할된 두 리스트를 각각 재귀적으로 정렬한다. 즉, 같은 방법(단계1과 단계2)을 적용한다.

 

한번의 루프(재귀)를 돌고나면 다음과 같이 원소들이 나뉜다. (단계1과 2를 거친 배열의 모습)

pivot보다 같거나 작음

pivot

pivot보다 큼

여기서 pivot이란 기준 값으로 정렬하고자 하는 원소들 중 첫 인덱스, 중간 원소, 마지막 인 원소, 무작위 선택 등 하나를 정하면 된다. 무작위로 선택하는 방법이 가장 많이 사용된다. 하지만 여기서는 pivot이 첫 번째 원소인 경우와 pivot이 마지막 원소인 경우를 구현할 것이다. partition함수가 분할의 과정을 나타낸다. partition함수를 거치고 나면 위의 표처럼 pivot값에 의해 앞 뒤로 구분이 된다.

 

 

#병합정렬과 비교

병합정렬의 경우, 병합하는 과정에서 해야할 일이 많고, 분할할 때 상수시간이 걸린다. 

퀵정렬의 경우 분할된 정렬들에 대해 특별히 해야할 일이 없다. 앞쪽 배열이 뒤쪽 배열보다 이미 작기 때문이다. 따라서 병합정렬과 달리 병합하는 과정이 간단하다. 하지만 분할할 때, 모든 원소를 비교하기 때문에 시간이 오래 걸린다. 

	병합정렬	퀵정렬
분할	간단(시간↓)	복잡(시간↑)
병합	복잡(시간↑)	간단(시간↓)

 

#구현

#include <iostream>
using namespace std;

void quicksort(int* a, int first, int last);
int partition(int* a, int frist, int last);
void swap(int* a, int* b);

int main(){
    int n;
    cin>>n;
    int* a = new int[n];
    for(int i=0; i<n; i++)
        cin>>a[i];
        
    quicksort(a,0,n-1);
    
    for(int i=0; i<n; i++)
        cout<<a[i]<<" ";
        
    return 0;
}

void quicksort(int* a, int first, int last){
    if(first>=last) return; //원소가 1개인 경우
    
    int pivotPoint = partition(a,first,lat);
    quicksort(a,first,j-1); //pivot보다 작거나 같은 쪽
    quicksort(a,j+1,last); //pivot보다 큰 쪽
}

int partition(int* a, int first, int last){
    int pivot = first;
    int i = first+1;
    int j = last;
    while(i<=j){
        while(i<=last && a[i]<=a[pivot]) //왼쪽에서 오른쪽으로 이동하며 pivot보다 큰 값 찾기
            i++;
        while(first<j && a[j]>=a[pivot]) //오른쪽에서 왼쪽으로 이동하며 pivot보다 작은 값 찾기
            j++;
        if(j<i) //엇갈린 경우
            swap(&a[pivot], &a[j]);
        else
            swap(&a[i], &a[j]);
    }
}

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

분할 방법2) pivot값을 마지막으로 설정

int partition(int* a, int first, int last){
    int pivot=a[last];
    int pivotPoint = first-1;
    for(int i=first; i<last; i++){
        if(a[i]<=pivot){
            pivotPoint++;
            swap(&a[i],&a[pivotPoint]);
        }
    }
    swap(&a[pivotPoint],&a[last]);
    return pivotPoint+1;
}

 

#시간복잡도 분석

*최악의 경우: pivot값이 최댓값 혹은 최솟값일 경우 //분할과 정복의 특징을 살리지 못하는 경우

 => O(n*n)

*평균적인 경우: O(n log n)

*가장 좋은 경우: pivot 원소들을 두 부분으로 나눌 때, 항상 같은 크기로 나눌 경우 => O(n log n)

 

#공간

O(n)의 스택 메모리가 필요하다.