4. 퀵 정렬 (Quick Sort)

지난 포스팅에서 살펴본 선택, 버블, 삽입 정렬은 모두 시간복잡도 O(N^2)을 가졌습니다. 그렇기 때문에 데이터의 갯수가 많아지면 일반적인 상황에서 사용하기 매우 어렵습니다.

 

이번에 다룰 퀵 정렬(Quick Sort)은 대표적인 분할정복(divide and conquer) 알고리즘으로, 시간복잡도 O(N*logN)을 가져 매우 빠른편으로, 일반적인 상황에서 사용하기 용이합니다.

 

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하시오.
1 10 5 8 7 6 4 3 2 9

 

문제는 동일합니다. 숫자들을 arr 배열이라고 합시다.

퀵 정렬에서는 기준값(피벗) 을 정해놓고 진행합니다. 보통 첫 번째 원소인 1 을 피벗으로 정합니다.

 

                                           <-j
(1) 10  5  8  7  6  4  3  2  9
     i->

 

P:  1보다 큰 숫자를 왼쪽부터 찾고, 1보다 작은 숫자를 오른쪽부터 찾습니다.

    1보다 큰 숫자의 인덱스: i, 1보다 작은 숫자의 인덱스 : j

 

i > j인 경우, 피벗의 자리와 arr[j]값을 바꿉니다. 그 후 피벗의 왼쪽 배열과 오른쪽 배열에서 다시 P를 실행합니다.

i <= j인 경우, P를 반복합니다.

 

소스코드를 보는게 이해가 빠를 것 같습니다. 윗 부분만으로는 이해하기가 어렵습니다.

 

소스코드

public class TestMain {

    public void quickSort(int start, int end, int[] arr){
        if(start >= end) return;

        int i = start + 1;
        int j = end;
        int key =start;

        while(i<=j){
            while(i<=end && arr[i] <= arr[key]){ // arr[key] 보다 더 큰값 발견
                i++;
            }
            while(j>start && arr[j] >= arr[key]){ // arr[key] 보다 더 작은값 발견
                j--;
            }
            if(i > j){
                int temp = arr[j];
                arr[j] = arr[key];
                arr[key] = temp;
            }
            else{
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        quickSort(start, j-1, arr);
        quickSort(j+1, end, arr);
    }

    public static void main(String[] args) {

        TestMain t = new TestMain();
        int[] arr1 = {1,10,5,8,7,6,4,3,2,9};
        int[] arr2 = {2,4,6,8,10,5,7,9,1,3};

        t.quickSort(0,9,arr1);
        t.quickSort(0,9,arr2);

        for (int i : arr1) {
            System.out.print(i + "  ");
        }
        System.out.println();
        for (int i : arr2) {
            System.out.print(i+"  ");
        }
    }
}

 

위 소스코드에서

arr[i] > arr[key] 

arr[j] < arr[key] 입니다. (애초에 i와 j의 정의가 이러하니까요.)

 

그런데 i < j 인 경우에는 그저 arr[i]값과 arr[j] 값을 바꿔주기만 하면 됩니다. 애초에 arr[i] > arr[j] 인데,

더 큰 값이 배열의 앞에 위치하기 때문입니다. 이 경우는 while문을 통해 다시 한번 탐색을 합니다.

 

그렇게 가다가 i > j 인 순간이 옵니다. 이 경우는 특별합니다. 이 의미는

(1) : i를 기점으로, i 왼쪽의 숫자들은 pivot 값보다 전부 작다. (i 에서 처음 pivot 보다 큰값이 나타나기 때문

(2) : j를 기점으로, j 오른쪽의 숫자들 중에는 pivot 값보다 전부 크다. (j 에서 처음 작은 값을 발견.)

 

(1) 과 (2) 에 의해서 j 왼쪽의 숫자들이 모두 pivot 보다 작다는 결론이 나옵니다. ( i > j 이기 때문)

j 왼쪽은 pivot 값보다 작고, j 오른쪽은 pivot 값보다 크므로 pivot 이 위치할 곳은 인덱스 j 가 됩니다.

 

따라서 arr[key] 와 arr[j] 의 위치를 바꿔줍니다. 

 

우리는 위에서 arr[key] 가 전체 arr에서 봤을 때 정확한 위치에 위치시켰습니다. 따라서 quickSort 의 범위를 j 왼쪽과 j 오른쪽으로 분리하여 실행을 해줍니다. 정렬이 완료될 때까지.

이렇게 나눠서 실행하는 것을 (divide and conquer) 분할정복이라고 부릅니다.

 

 

시간복잡도

퀵 정렬은 기본적으로 N번 탐색하되 반씩 쪼개 들어가므로 O(N*logN) 입니다.

 

하지만 최악의 경우, 퀵 정렬의 시간복잡도는 O(N^2) 까지도 늘어납니다...

1  2  3  4  5  6  7  8  9  10

위 배열의 경우, divide and conquer를 하여도 연산 횟수가 N + N-1 + ...... + 1 이기 때문입니다. 

배열을 분할하여도 큰 의미가 없게 됩니다.

 

이처럼 퀵 정렬은 평균 시간복잡도는 O(N*logN) 으로

앞서 말한 3개의 정렬 알고리즘보다는 월등히 빠르나, 최악의 경우 O(N^2)이라는 단점이 있습니다.