[알고리즘] 퀵소트(Quick Sort) - C/C++

<퀵소트(Quick Sort)> 

- 피봇(pivot)을 기준으로 왼쪽에 작은 값 / 오른쪽에 큰 값으로 분류한 후, 

이 두 부분 집합에 대해 각각 퀵소트를 동일하게 반복하는 분할 정복 (Divide and Conquer) 기법의 정렬 알고리즘

- 재귀호출 이용

<시간복잡도>

* 최선, 평균 :

- 상당히 효율적인 정렬 알고리즘임을 알 수 있다.

* 최악 :

- 부분집합이 한 쪽으로만 계속 몰리는 경우 효율성이 떨어진다.

 

<quickSort>

void quickSort(int arr[], int start, int end) {
    if (start < end) {
        int left = start;
        int right = end;
        int pivot = end;
        
        while(left < right) {
            while(arr[left] <= arr[pivot] && left < right)  ++left;
            while(arr[right] >= arr[pivot] && left < right) --right;
            if (left >= right) {
                SWAP(arr[right], arr[pivot]);
            } else {
                SWAP(arr[left], arr[right]);
            }
        }
        quickSort(arr, start, right - 1);
        quickSort(arr, right + 1, end);
    }
}

 

<main>

#define SIZE 12
#define SWAP(a,b) {int t=a;a=b;b=t;}

void printAll(int arr[], int size){
    for(int i = 0; i < size; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
    return;
}


int main(){
    int arr[SIZE] = { 80, 50, 70, 10, 90, 100, 90, 22, 60, 20, 40, 30};
    
    printf("before : ");
    printAll(arr, SIZE);
    
    quickSort(arr, 0, SIZE - 1);
    
    printf("after : ");
    printAll(arr, SIZE);
    
    return 0;
}

 

<결과>