[Algorithm] 퀵 정렬 (Quick Sort)

💡퀵 정렬(Quick sort) 알고리즘?

• 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘
• 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속함
• 분할 정복 방법을 통해 리스트를 정렬
  1. 리스트 가운데서 하나의 원소를 고름, 이 원소를 피벗 이라고 한다.
  2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 비펏보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. -> 리스트를 둘로 나누는 것을 분할이라고 한다.
  3. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
  4. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. -> 리스트의 크기가 0이나 1이 될때까지 재귀를 반복

💡구체적으로 알고리즘을 파헤쳐보자

• 퀵 정렬은 다음의 단계로 이루어진다.
  • 분할 : 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열로 나뉘어진다. (왼쪽 : 피벗을 중심으로 작은 수들, 오른쪽 : 피벗을 중심으로 큰 수들)
  • 정복 : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 적지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용
  • 결합 : 정렬된 부분 배열들을 하나의 배열로 합병한다.

    

💡 퀵 정렬 알고리즘 예제

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

 

💡 C++ 코드

#include <iostream>
using namespace std;

// 두 값을 서로 바꾸는 swap 함수 만들기
void swap(int *a, int *b, int temp){
    temp = *b;
    *b = *a;
    *a = temp;
}

// 부분정렬 ( -> pivot의 위치 리턴 )
int partition(int list[], int left, int right){
    int pivot, temp;
    int low, high;

    pivot = list[left];
    low = left;
    high = right+1;

    // 전체 do-while 문 : low와 high가 교차할 때까지 반복 = 교차할 경우 stop!!
    do{
        //low를 먼저 증가시키면서 시작
        //low가 right보다 작거나 같고 && list[low]가 pivot보다 작을 경우 동안 반복
        do{
            low++;
        }while(low<=right && list[low]<pivot);

        //high를 먼저 증가시키면서 시작
        //high가 left보다 크거나 같고 && list[high]가 pivot보다 클 경우 동안 반복
        do{
            high--;
        }while(high>=left && list[high]>pivot);

        // 내부 두개의 do-while 문을 거쳐서 나온 low와 high의 값에서
        // low와 high가 교차하지 않는다면, 두 list[low]와 list[high]의 값을 바꾸어 준다.
        if(low<high){
            swap(&list[low], &list[high], temp);
        }

    }while(low<high);

    //low와 high가 교차했으면, list를 빠져나와 list[left](=pivot)과 list[high]를 교환한다.
    swap(&list[left], &list[high], temp);

    return high;
}

void quickSort(int list[], int left, int right){
    // 정렬 범위가 2개이상의 데이터라면, (리스트의 크기가 0이나 1이 아니면)
    if(left<right){
        // pivot의 위치
        int pivot_lo = partition(list, left, right);

        // pivot을 제외한 2개의 부분 리스트를 순환 호출 (= 재귀)
        // <<left~pivot의 바로 앞>>
        quickSort(list, left, pivot_lo-1);
        // << pivot의 바로 뒤~right>>
        quickSort(list, pivot_lo+1,right);
    }

}

int main(){

    int list[9] = {5, 3, 8, 4, 9, 1, 6, 2, 7};
    int n = 9;
    // 배열의 시작 = 0, 배열의 끝 = 9-1=8
    quickSort(list,0,n-1);

    cout<<"*****quickSort 후*****"<<endl;

    for(int i = 0 ; i < 9 ; i++){
        cout<<list[i]<<endl;
    }
}

 

💡 퀵 정렬 알고리즘의 특징

• 장점
  1. 속도가 빠르다.
     • 불필요한 데이터의 이동을 줄이고 먼거리의 데이터를 교환할 뿐만 아니라,
     • 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문이다.
  2. 추가 메모리 공간을 필요로 하지 않는다. 
     • 비교만을 통해서 구현
     • O(log n) 만큼의 메모리를 필요로 한다.
• 단점
  1. 이미 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
     • 해결방법 : 리스트 내의 몇개의 데이터 중에서 크기순으로 중간 값(medium)을 피벗으로 선택

 

💡 퀵 정렬의 시간복잡도

퀵 정렬의 성능은 피봇 선택이 좌우한다!

• 가장 작은 숫자또는 가장 큰 숫자가 선택되면, 한부분으로 치우치는 분할을 야기-> 최악!

1️⃣ 최선의 경우

• 순환 호출의 깊이
  • 배열의 원소개수 n이 2의 거듭 제곱이라고 가정하자 ( n = 2^k )
  • n = 2^3 일 경우, 2^3 -> 2^2 -> 2^1 -> 2^0 순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있다.
  • n = 2^k 일 경우, 순환 호출의 깊이는 k이고 k = log₂n 이다.
  • log₂n
• 각 순환 호출 단계에서의 비교 연산
  • 평균 n 번
• 이동 횟수  = 비교 횟수보다 적으므로 무시할 수 있다.
• 비교횟수 = 순환 호출의 깊이 * 각 순환 호출 단계의 비교 연산 = nlog₂n
• 최선의 경우 T(n) = O(nlog₂n)

 

 

2️⃣ 최악의 경우

• 리스트가 계속 불균형하게 나누어지는 경우 ( 특히 이미 정렬된 리스트에 대해서 퀵 정렬을 실행하는 경우 ) 

  

• 순환 호출의 깊이
  • 배열의 원소개수 n이 2의 거듭 제곱이라고 가정하자 ( n = 2^k ) 
  • 순환 호출의 깊이는 n
  • n
• 각 순환 호출 단계에서의 비교 연산
  • 평균 n 번
• 이동 횟수  = 비교 횟수보다 적으므로 무시할 수 있다.
• 비교횟수 = 순환 호출의 깊이 * 각 순환 호출 단계의 비교 연산 = n^2
• 최악의 경우 T(n) = O(n^2)

 

 

3️⃣ 평균

• 평균 T(n) = O(nlog₂n)
• 크기가 n인 배열 중 어떤 하나가 pivot으로 선택될 확률 = 1/n
• 최대 n 번 연산을 원소 n개가 진행 = n^2
• 이게 총 log₂n 개의 층으로 구성
• 1/n * n^2 * log₂n = nlog₂n

정렬 알고리즘 시간복잡도 정리

 

 

---

💡 퀵 정렬의 성능 향상 방법

• 입력의 크기가 매우 클때, 퀵 정렬의 성능을 더 향상시키기 위해서 삽입 정렬이 동시에 사용
• 입력의 크기가 작을 때에는 퀵 정렬이 삽입 정렬보다 빠르지만은 않다. 왜냐하면 재귀호출로 수행되기 때문!
• 부분문제의 크기가 작아지면 더이상의 분할(재귀호출)을 중단하고 삽입 정렬을 사용하는 것이다.

 

+ 응용

• 퀵 정렬은 커다란 크기의 입력에 대해서 가장 좋은 성능을 보이는 정렬 알고리즘
• 실질적으로 어느 정렬 알고리즘보다 좋은 성능을 보인다.
• 생물 정보 공학에서 특정 유전자를 효율적으로 찾는데 접미 배열과 함께 퀵 정렬이 활용된다.

 

Reference

• 위키백과
• heejeong Kwon의 블로그

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog