[알고리즘] 퀵 정렬(Quick Sort)이란?

퀵 정렬이란

• 평균적으로 가장 빠른 정렬 방법
• 분할정복법 사용
• 리스트를 2개의 부분리스트로 합병정렬과는 다르게 퀵정렬은 리스트를 비균등 분할하고, 각각의 부분리스트를 다시 퀵정렬한다(재귀)
• 불안정 정렬에 속하며 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬에 속한다.

분할정복이란? 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
분할 정복 방법은 대개 재귀호출을 이용하여 구현한다.

분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 기준으로 작은 요소들은 왼쪽에, 큰 요소들은 오른쪽에 오게끔)로 분할한다.

정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 재귀 호출을 이용하여 분할 정복 방법 적용한다.

결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.

 

즉, 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

---

 

퀵정렬 알고리즘 과정

1. 리스트 안에 있는 한 요소를 선택한다. 고른 원소를 피벗(pivot)이라고 한다.
2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다.
3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다. (재귀호출을 이용하여 정렬 반복)
4. 부분 리스트들이 더 이상 분할이 불가능할 때 까지 반복한다. (리스트의 크기가 0이나 1이 될때까지 반복)

---

---

1. 피벗값을 입력 리스트의 첫 번째 데이터라고 하겠다.
2. 2개의 인덱스변수(low,high)를 이용하여 리스트를 두 개의 부분 리스트로 나눈다.
3. (피벗이 5인경우)
   a. low는 왼쪽에서 오른쪽으로 탐색해갔다가 피벗보다 큰 데이터(8)을 찾으면 멈춘다.
   b. high는 오른쪽에서 왼쪽으로 탐색해가다가 피벗보다 작은 데이터(2)를 찾으면 멈춘다.
   c. low와 high가 가리키는 두 데이터를 서로 교환한다.
   d. low와 high가 엇갈릴 때까지 반복한다.
4. 2회전: 피벗(1회전의 왼쪽 리스트의 첫번째 데이터)이 1인 경우, 위와 동일한 방법으로 반복
5. 3회전: 피벗(1회전의 오른쪽 리스트의 첫번째 데이터)이 9인 경우, 동일한 방법으로 반복

---

퀵정렬 알고리즘 C언어 코드

# include <stdio.h>
# define MAX_SIZE 9
# define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) )

// 1. 피벗을 기준으로 2개의 부분 리스트로 나눈다.
// 2. 피벗보다 작은 값은 모두 왼쪽 부분 리스트로, 큰 값은 오른쪽 부분 리스트로 옮긴다.
/* 2개의 비균등 배열 list[left...pivot-1]와 list[pivot+1...right]의 합병 과정 */
/* (실제로 숫자들이 정렬되는 과정) */
int partition(int list[], int left, int right){
    int pivot, temp;
    int low, high;

    low = left;
    high = right + 1;
    pivot = list[left]; // 정렬할 리스트의 가장 왼쪽 데이터를 피벗으로 선택(임의의 값을 피벗으로 선택)

    /* low와 high가 교차할 때까지 반복(low<high) */
    do{
        /* list[low]가 피벗보다 작으면 계속 low를 증가 */
        do {
            low++; // low는 left+1 에서 시작
        } while (low<=right && list[low]<pivot);

        /* list[high]가 피벗보다 크면 계속 high를 감소 */
        do {
            high--; //high는 right 에서 시작
        } while (high>=left && list[high]>pivot);

        // 만약 low와 high가 교차하지 않았으면 list[low]를 list[high] 교환
        if(low<high){
            SWAP(list[low], list[high], temp);
        }
    } while (low<high);

    // low와 high가 교차했으면 반복문을 빠져나와 list[left]와 list[high]를 교환
    SWAP(list[left], list[high], temp);

    // 피벗의 위치인 high를 반환
    return high;
}

// 퀵 정렬
void quick_sort(int list[], int left, int right){

    /* 정렬할 범위가 2개 이상의 데이터이면(리스트의 크기가 0이나 1이 아니면) */
    if(left<right){
        // partition 함수를 호출하여 피벗을 기준으로 리스트를 비균등 분할 -분할(Divide)
        int q = partition(list, left, right); // q: 피벗의 위치

        // 피벗은 제외한 2개의 부분 리스트를 대상으로 순환 호출
        quick_sort(list, left, q-1); // (left ~ 피벗 바로 앞) 앞쪽 부분 리스트 정렬 -정복(Conquer)
        quick_sort(list, q+1, right); // (피벗 바로 뒤 ~ right) 뒤쪽 부분 리스트 정렬 -정복(Conquer)
    }

}

int main(void){
    int i;
    int n = MAX_SIZE;
    int list[9] = {5, 3, 8, 4, 9, 1, 6, 2, 7};

    // 퀵 정렬 수행(left: 배열의 시작 = 0, right: 배열의 끝 = 8)
    quick_sort(list, 0, n-1);

    // 정렬 결과 출력
    for(i=0; i<n; i++){
        printf("%d\n", list[i]);
    }
}

---

 

퀵정렬 특징 및 시간복잡도

장점

• 속도가 빠르다 (O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.)
• 추가 메모리 공간을 필요로 하지 않는다.(O(log n)만큼의 메모리를 필요로 한다.)

단점

• 정렬된 리스트에 대해서는 퀵정렬이 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
• 퀵 정렬의 불균형을 방지하기 위하여 피벗을 선택할 때 적절한 피벗을 사용해야 한다.(보통 중간값)

---

시간복잡도

최선의 경우 (거의 균등한 리스트로 분할되는 경우)

• 패스 수: log(n)
• 각 패스 안에서의 비교회수: n
• 총 비교횟수: nlog(n)
• 총 이동횟수: 비교횟수에 비하여 적으므로 무시 가능

---

최악의 경우 (리스트가 불균형하게 나누어지는 경우) (특히 이미 정렬된 경우)

• 패스 수: n
• 각 패스안에서의 비교 회수: n
• 총 비교횟수: n^2
• 총 이동횟수: 무시 가능

예시

중간값(medium)을 피벗으로 선택하면 불균등 분할 완화 가능