[알고리즘] 정렬(4) - 퀵 정렬

 

퀵 정렬(Quick Sort)

 

정렬 방식

• 분할 정복을 바탕으로 해서, 큰 범위의 정렬을 작은 범위 정렬로 분할시켜서 정렬시킨다.

정렬 과정

퀵정렬 동작

1. 기준 요소 선정 및 정렬대상 분류

• 기준 요소(pivot)를 선정하고 해당 값보다 작으면 기준 요소 왼쪽, 크면 오른쪽으로 옮긴다.
  • 해당 글에서는 기준요소를 배열 안 첫번째 값으로 한다.
  • 기준 요소 선정은 무작위로 선정할 수도 있고 처음 3개의 요소를 중간 값으로 하는 등 여러 방법이 있다.

2. 정렬대상 분할

• 기준 요소 기준으로 왼쪽은 기준 요소보다 작은 그룹들이 생긴다.
• 기준 요소 기준으로 오른쪽은 기준 요소보다 큰 그룹들이 생긴다.
• 각 그룹에서 1번 과정을 반복한다.

3. 반복

• 각 그룹 안에서 1과 2를 반복한다.
• 그룹 크기가 1이하로 되어 분할할 수 없을 때까지 진행
• 재귀적으로 수행

 

배열에서 분할 과정

• 한쪽은 왼쪽부터 오른쪽으로 이동하면서 기준요소보다 큰 요소를 찾는다.
• 다른 한쪽은 오른쪽부터 왼쪽으로 이동하면서 기준요소보다 작은 요소를 찾는다.
• 그리고 교환한다.
• 만약 둘이 접선하게 된다면 기준요소를 왼쪽 그룹의 마지막 요소와 교환한다.

 

퀵 정렬 성능

• 재귀의 깊이와 분할을 위한 비교 횟수로 성능을 확인한다.

최선의 경우

최선의 경우 분할 모습

• 퀵 정렬 호출 시 자료구조가 1/2로 쪼개지는 상황
• 자료구조 크기가 n일 때 퀵 정렬의 재귀 호출 깊이는 log2{n}
• 비교 횟수는 항상 n
  • 2번째 단계: n/2 + n/2 = n
  • 3번째 단계: n/4 + n/4 + n/4 + n/4 = n

 

$$ 퀵\;정렬\;비교\;횟수 $$

$$ =\;재귀 호출 깊이\;x\;각 재귀 호출 단계에서\;비교\;횟수 $$

$$ = n * log_2{n} = nlog_2{n} $$

 

$$ 시간복잡도 :\;O(nlog_2{n}) $$

 

최악의 경우

최악의 경우 분할 모습

• 데이터가 미리 정렬되어 있거나 역순으로 정렬된 경우
• 1:n-1 비율로 쪼개져서 n-1, n-2, ..., 1번 비교해야한다.
  • n(n-1)/2번 비교

 

$$ 시간복잡도:\; O(n^2) $$

 

평균의 경우

• 1.39nlog2{n}회 비교

$$ 시간복잡도:\;O(nlog2{n}) $$

 

퀵 정렬의 최악의 경우는 버블 정렬, 삽입 정렬의 성능과 비슷해질 수 있지만 드물게 발생하기 때문에 성능이 좋다

 

코드 - [언어: C]

#include <stdio.h>

void swap(int* A, int* B){
    int temp = *A;
    *A = *B;
    *B = temp;
}

int partition(int data[], int left, int right){

    int first = left;
    int pivot = data[first]; // 기준 요소를 맨 앞을 고르는 것으로 함

    ++left;
    
    while(left <= right){
        while(data[left] <= pivot && left < right)
            ++left;
        while(data[right] >= pivot && left <= right)
            --right;

        if(left < right)
            swap(&data[left], & data[right]);
        else
            break;
    }

    swap(&data[first], &data[right]);

    return right;
    
}

void quick_sort(int data[], int left, int right){

    if(left < right){
        
        int pivot = partition(data, left, right);

        // (배열, 정렬 범위 시작, 정렬 범위 끝)
        quick_sort(data, left, pivot-1);  // pivot 기준에서 왼쪽 그룹 정렬
        quick_sort(data, pivot+1, right); // pivot 기준에서 오른쪽 그룹 정렬
    }

}

int main() {
    int data[] = {5, 3, 8, 4, 9, 1, 6, 2, 7};
    int length = sizeof(data) / sizeof(data[0]);

    // 퀵 정렬
    quick_sort(data, 0, length-1);

    // 퀵 정렬 결과 출력
    for(int i = 0; i < length; i++){
        printf("%d ", data[i]);
    }
    
    return 0;
}

 

알고리즘 gif 참고

- https://visualgo.net/en/sorting