C++ 퀵정렬 - 정렬4

퀵 정렬은 대놓고 이름에다가 퀵을 붙여놓은 아주 대담한 정렬이다

그동안의 정렬과 다른 점은 시간 복잡도에 있는데

평균적으로 O(n²)의 시간 복잡도를 가지고 있는 선택, 버블, 삽입과 달리 

퀵 정렬은 평균적으로 O(nlogn)의 시간 복잡도를 가지고 있다.

 

퀵 정렬이 log시간을 가질 수 있는 이유는 분할 정복 알고리즘이기 때문이다

퀵 정렬의 아이디어는

1. 피봇을 정하고 (대부분의 경우 가장 앞의 원소)

2. 왼쪽부터 차례로 피봇보다 큰 값을

3. 오른쪽부터 차례로 피봇보다 작은 값을 찾는다

4. 두 값을 찾았다면 서로 자리를 바꾼다

5. 만약 피봇보다 큰 값의 인덱스와 피봇보다 작은 값의 인덱스가 작아지면 (엇갈리면)

6. 피봇보다 작은 값과 피봇의 자리를 바꾼다

7. start ~ 작은 값 인덱스-1, 작은 값 인덱스+1 ~ end로 나누어서 퀵 정렬

int* QuickSort(int*arr, int start, int end){

    if(start >= end){ //재귀 탈출 
        return arr;
    }

    int pivot = start, i=start+1, j=end, temp;

    while(i <= j){
        while(arr[pivot] >= arr[i]){ //피봇보다 큰  값
            i++;
            if(i >= end){
                break;
            }
        }
        while(arr[pivot] <= arr[j]){ //피봇보다 작은  값
            j--;
            if(j <= start + 1){
                break;
            }
        }
        if(i > j){ //엇갈린 경우
            temp = arr[j];
            arr[j] = arr[pivot];
            arr[pivot] = temp;
        }
        else{ //안 엇갈린 경우
            temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
    }
    
    QuickSort(arr, start, j-1);	//j-1과
    QuickSort(arr, j+1, end);	//j+1을 해주는 이유는 피봇은 이미 정렬 되어 있기 때문이다
    return arr;
}

말로 설명하기 굉장히 어려운 정렬이지만 코드를 보면 굉장히 쉽다는 것을 알 수 있다.

 

아무튼 이 퀵 정렬에서 분할 정복 알고리즘이 적용이 된 부분은 7번에 start~작은 값 인덱스-1, 작은 값 인덱스+1~end로 나누어서 퀵 정렬을 반복하는 부분이다.

 

7, 8, 4, 3, 2, 1, 5, 6을 정렬 한다면 

O(n²)의 시간 복잡도를 가진 선택, 버블, 삽입 정렬의 경우

8 * 8 = 64의 시간 복잡도를 가지지만

 

이 두 배열을

7, 8 | 4, 3 | 2, 1 | 그리고 5, 6으로 갈라 정렬을 한다면

2*2 + 2*2 + 2*2 + 2*2 = 16

모두 합하여 정렬을 한다면 N의 시간을 소요하여

16 + 8 = 24 즉 nlogn = 8*log₂8 = 24

총 24의 시간 복잡도를 가진다 

(사실 위의 예는 퀵 정렬 최선의 경우에 해당하고 

합병정렬에 더 가깝다고 볼 수 있다)