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

알고리즘

퀵 정렬(Quick Sort)의 알고리즘은 다음과 같습니다.

 

정렬의 기준 값인 피봇(Pivot) 값을 설정합니다.

 

• 피봇 값보다 큰 숫자를 왼쪽부터 찾고, 피봇 값보다 작은 숫자를 오른쪽부터 찾습니다.
• 만약 작은 숫자의 index가 큰 숫자의 index보다 작으면 엇갈린 상황으로, 왼쪽의 작은 값과 피봇 값의 위치를 바꿔줍니다.
• 큰 숫자와 작은 숫자의 위치를 바꿔줍니다.
• 이를 배열이 정렬될 때까지 반복합니다.

 

이렇게 보면 처음에는 무슨 말인지 이해하기 어렵습니다.

 

예를 들어 다음 배열을 정렬해보며 쉽게 이해해 봅시다.

[4 , 6 , 8 , 1 , 3 , 5 , 7 , 2 , 10 , 9]

---

1-1) 피봇 값을 선택합니다. 보통 첫 번째 원소를 피봇 값으로 설정합니다. 피봇 값 = 4

피봇 값인 4보다 큰 숫자를 왼쪽인 6부터 6, 8, 1, ... 순으로 찾고, 4보다 작은 숫자를 오른쪽인 9,10,2, ... 순으로 찾습니다.

[4 , 6 , 8 , 1 , 3 , 5 , 7 , 2 , 10 , 9]

피봇 값인 4보다 큰 수를 오른쪽부터 찾으면 6, 4보다 작은 수를 왼쪽부터 찾으면 2가 나온다.

1-2) 이 둘의 위치를 바꿔 줍니다.

1-3) 작은 숫자의 index가 큰 숫자의 index보다 작지 않으므로 엇갈린 상황이 아닙니다.

[4 , 2 , 8 , 1 , 3 , 5 , 7 , 6 , 10 , 9]

---

2-1) 피봇 값인 4보다 큰 숫자를 왼쪽인 2부터 2, 8, 1 ... 순으로 찾고, 4보다 작은 숫자를 오른쪽인 9, 10, 6 ... 순으로 찾습니다.

[4 , 2 , 8 , 1 , 3 , 5 , 7 , 6 , 10 , 9]

2-2) 이 둘의 위치를 바꿔 줍니다.

2-3) 작은 숫자의 index가 큰 숫자의 index보다 작지 않으므로 엇갈린 상황이 아닙니다.

[4 , 2 , 3 , 1 , 8 , 5 , 7 , 6 , 10 , 9]

---

3-1) 피봇 값인 4보다 큰 숫자를 왼쪽인 2, 3, 1 ... 순으로 찾고, 4보다 작은 숫자를 오른쪽인 9, 10, 6 ... 순으로 찾습니다.

[4 , 2 , 3 , 1 , 8 , 5 , 7 , 6 , 10 , 9]

3-2) 작은 숫자인 1의 index가 큰 숫자인 8의 index보다 작으니 엇갈린 상황입니다.

이때 왼쪽의 작은 값과 피봇 값의 위치를 바꿔 줍니다.

[1 , 2 , 3 , 4 , 8 , 5 , 7 , 6 , 10 , 9]

이 상태가 되면, 기존의 피봇 값이었던 4를 기준으로 왼쪽에는 4보다 작은 값, 오른쪽에는 4보다 큰 값만 남게 됩니다.

---

4-1) 새로운 피봇 값을 설정해 줍니다. 4를 기준으로 작은 왼쪽, 큰 오른쪽이 구분되었으니, 각각 새로운 피봇 값을 설정해 줍니다. 4를 기준으로 양쪽 두 개의 배열의 첫 번째 원소들을 새로운 피봇 값으로 설정해 줍니다. 1과 8.

[1 , 2 , 3 , 4 , 8 , 5 , 7 , 6 , 10 , 9]

새로 설정된 피봇 값인 1, 8로 퀵 정렬 알고리즘을 수행합니다.

 

5-1) 피봇 값 1을 기준으로 큰 숫자를 2, 3 중에서 찾아보면 2이고, 작은 숫자를 3, 2, 1 순으로 찾아보면 1 자기 자신입니다.

5-2) 작은 값인 1의 index가 큰 값인 2의 index보다 작으니 엇갈린 상황이므로 1을 작은 값인 1과 바꿔주므로, 1은 그 자리에 고정되게 되고, 새로운 피봇 값 2를 설정하게 됩니다.

이렇게 1이 고정된 방법과 같은 방법으로 2, 3의 정렬이 완료되어 1, 2, 3, 4가 정렬된 상태로 남게 됩니다.

---

6-1) 다른 피봇 값인 8에 대해 8보다 큰 숫자를 왼쪽부터 5, 6, 7, ... 순으로 찾고, 작은 숫자를 오른쪽부터 9, 10, 6, ... 순으로 찾습니다.

[1 , 2 , 3 , 4 , 8 , 5 , 7 , 6 , 10 , 9]

6-2) 작은 값인 6의 index가 큰 값인 10의 index보다 작으니 엇갈린 상황이므로 8을 작은 값인 6과 바꿔줍니다.

[1 , 2 , 3 , 4 , 6 , 5 , 7 , 8 , 10 , 9]

엇갈린 상황에서 정리하면, 8을 기준으로 작은 값들은 왼쪽에, 큰 값들은 오른쪽으로 구분되며 8은 고정됩니다.

그리고 6, 10을 새로운 피봇 값으로 설정합니다.

[1 , 2 , 3 , 4 , 6 , 5 , 7 , 8 , 10 , 9]

 

이제 위와 같은 알고리즘을 계속 적용하면 다음과 같이 정렬된 배열을 확인할 수 있습니다.

[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10]

 

이렇게 퀵 정렬을 분할 정복식으로 빠르게 정렬합니다. 4-1)에서, 4를 기준으로 양쪽에 두 개의 배열로 나눠 동시에 정렬하며 분할 정복 알고리즘을 만족합니다.

 

즉, 퀵 정렬은 한번 정렬했을 때, 그 값을 기준으로 왼쪽과 오른쪽이 나누어진다는 특징 덕분에 매우 빠릅니다.

 

(C언어 Library의 sort함수가 퀵 정렬로 작성되어있을 정도로 빠릅니다.)

---

시간 복잡도

퀵 정렬의 시간 복잡도는 O(N x logN)입니다.

 

O(N x logN)의 시간 복잡도는 삽입, 선택, 버블 정렬의 시간 복잡도인 O(N^2) 보다 훨씬 좋습니다.

 

하지만 퀵 정렬에도 치명적인 단점이 존재합니다.

 

비록 시간 복잡도가 O(N x logN)이지만, 피봇 값을 설정하는 경우에 따라 최악의 경우 O(N^2)이 될 수 있습니다.

 

예를 들어 이미 정렬되어 있는 배열 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]의 경우, 1을 피봇 값으로 설정하면 첫 단계에서 1이 고정되고 분할 정복 알고리즘을 수행하지 못합니다.

 

즉, 시간 복잡도를 O(N x logN)으로 만들어 주는 퀵 정렬의 장점을 활용하지 못하는 것입니다.

 

제일 효율 적인 상황은, 5나 6 같은 숫자를 초기 피봇 값으로 설정하여 분할점으로 선정돼야 퀵 정렬이 가장 효율적으로 작용됩니다.

---

소스코드

위의 내용을 바탕으로 C++로 소스코드를 작성해 보겠습니다.

 

퀵 정렬의 장점인 분할 정복을 구현하기 위해 보통 재귀를 많이 사용합니다.

 

#include <bits/stdc++.h>
using namespace std;

//배열 원소 갯수
int number = 10;
//정렬할 배열
int arr[] = {4,6,8,1,3,5,7,2,10,9};

void quickSort(int arr[], int start, int end) {
    //원소가 1개인 경우 정렬 수행 X
    if(start>=end)
        return;

    //첫 번째 수를 피봇 값으로
    int pivot = start;
    //피봇 값보다 큰값 오른쪽에서 부터 탐색 하기 위한 index i
    int i = start + 1;
    //피봇 값보다 큰값 왼쪽에서 부터 탐색 하기 위한 index j
    int j = end;
    //나중에 Swap 할때 사용할 temp
    int temp;
    
    //엇갈릴 때 까지 반복
    while(i <= j) {
        //피봇 값 보다 큰값 찾을때까지 i++
        while(i <= end && arr[i] <= arr[pivot])
            i++;
        //피봇 값 보다 작은값 찾을때까지 i++
        while(j > start && arr[j] >= arr[pivot])
            j--;

        //작은 값의 index가 큰 값의 index보다 커서 엇갈린 상태면
        //피봇 값과 작은 값 위치 변경
        if(i > j) {
            temp = arr[j];
            arr[j] = arr[pivot];
            arr[pivot] = temp;
        } //엇갈린 상태 아니면 i 와 j 교체
        else {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    //재귀적으로 분할 정복 실행
    quickSort(arr, start, j-1);
    quickSort(arr, j+1, end);
}

int main(void){
    
    quickSort(arr, 0, number-1);

	//정렬된 배열 출력해 확인
    for(int i=0;i<10;i++)
        cout << arr[i] << " ";
    
    return 0;
}

 

위 코드를 실행시켜 보면 다음과 같이 정렬된 배열을 확인할 수 있습니다.