• 퀵소트 알고리즘 :: 마이구미
    알고리즘 2018. 4. 10. 15:51

    이 글은 정렬 중 퀵소트(Quick Sort), 퀵정렬이라고 불리는 정렬을 다뤄본다.

    누구나 한번쯤 들어봤고, 구현해본 정렬 중 하나이다.

    빠른 정렬에 분류되고 기본적인 버블 정렬처럼 많이 언급되는 정렬이다.


    1. 퀵소트란 무엇인가?

    2. 퀵소트는 어떻게 구현하는가?

    3. 퀵소트는 어떻게 개선할 수 있는가?


    -위키-


    퀵소트는 분할 정복 방법을 통해 구현된다.

    분할 정복이란, 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식이다.


    시간복잡도는 최악의 경우 O(n^2), 평균적으로 O(nlogn) 을 가진다.

    시간복잡도가 O(n^2) 임에도 불구하고 퀵소트가 빠른 정렬에 속하는 이유에 대해 의문을 가질 수 있다.

    하지만 O(n^2) 은 설계를 통해 개선이 가능한 부분이다.


    관련 내용은 아래에서 다루니 끝까지 읽는다면 왜 그런지 알 수 있을 것이다.


    또한 불안정 정렬로 분류된다. 

    불안정 정렬의 의미를 모른다면 다음 글을 참고하면 된다. (http://mygumi.tistory.com/94)


    퀵소트는 재귀방식을 사용하기 때문에 코드는 굉장히 짧다.

    다음 코드는 글에서 계속해서 활용하기 때문에 참고하길 바란다.


    public void quicksort(int[] array, int left, int right) { if (left >= right) { return; } int pi = partition(); quicksort(array, left, pi - 1); quicksort(array, pi + 1, right); }


    퀵소트하면, 피벗(Pivot) 이라는 용어가 존재한다.

    피벗이 전부라고 생각해도 될 정도로 중요하다.

    피벗을 선택하는 방법에는 여러가지가 존재한다.

    크게 첫번째 요소, 중간 요소, 마지막 요소, 랜덤으로 선택하는 방식이 있다. (상단의 위키의 gif 이미지는 랜덤 방식이다)

    피벗을 선택하는 방식은 꽤 중요하다.

    그 방식에 따라 처리 속도가 달라질 수 있기 때문이다.


    우선 피벗은 첫번째 요소를 선택하는 방식을 통해 전체적인 진행을 한다.(이유는 끝까지 읽어보길 바란다)

    피벗의 역할은 피벗을 기준으로 왼쪽 요소들은 피벗보다 작고, 오른쪽 요소들은 큰 수를 배치하고자한다.

    즉, 피벗을 기준으로 작은 수들은 왼쪽, 큰 수들은 오른쪽으로 분리한다.


    위 과정은 코드에서 partition() 함수를 뜻한다.

    이 함수의 실행 순서는 다음과 같다.


    1. 피벗을 선택한다.
    2. 오른쪽(j)에서 왼쪽으로 가면서 피벗보다 작은 수를 찾는다.
    3. 왼쪽(i)에서부터 오른쪽으로 가면서 피벗보다 큰 수를 찾는다.
    4. 각 인덱스 i, j 에 대한 요소를 교환한다.
    5. 2, 3, 4번 과정을 반복한다.
    6. 2, 3번을 더이상 진행할 수 없다면, 현재 피벗과 교환한다.
    7. 그 결과 교환된 피벗를 기준으로 왼쪽은 피벗보다 작은 수들이 존재하고, 오른쪽은 큰 수들이 존재한다.


    public int partition(int[] array, int left, int right) { int pivot = array[left]; int i = left, j = right; while (i < j) { while (pivot < array[j]) { j--; } while (i < j && pivot >= array[i]) { i++; } swap(array, i, j); } array[left] = array[i]; array[i] = pivot; return i; }


    우선 1 ~ 5번 과정을 그림으로 표현하면 다음과 같다.


    퀵소트


    그 후에는 i, j 가 교차하게 되어 더이상 2, 3, 4 번을 중단하고 6번 과정을 진행하게 된다.


    퀵소트


    결과적으로 배열은 20, 10, 30, 40, 70, 50, 80 으로 변한 것을 볼 수 있다.

    피벗 30을 기준으로 왼쪽은 피벗보다 작은 수이고, 오른쪽은 큰 수인 모습을 볼 수 있다.

    다시 한번 코드로 가서 i, j 인덱스의 변화를 살펴본다면 피벗에 대한 이해를 할 수 있을 것이다.


    여기까지가 partition 함수의 실행 ~ 완료 과정이다.


    public void quicksort(int[] array, int left, int right) { if (left >= right) { return; } int pi = partition(); quicksort(array, left, pi - 1); quicksort(array, pi + 1, right); }


    partition() 함수가 실행된 후는 피벗을 기준으로 왼쪽과 오른쪽으로 아래처럼 분할된 모습을 볼 수 있다.



    분할된 왼쪽 영역과 오른쪽 영역은 각 분할된 영역에서 다시 partition() 과정을 진행하게 된다.

    즉, 왼쪽 영역은 피벗(20)을 기준으로 같이 또 쪼개질 것이고, 오른쪽 영역 피벗(40) 을 기준으로 쪼개질 것이다.

    계속해서 이렇게 과정이 쪼개질 수 있을 때까지 쪼개는 과정으로 재귀적으로 두 영역을 위해 quicksort() 함수를 호출하게 되는 부분이다.


    public void quicksort(int[] array, int left, int right) { if (left >= right) { return; } int pi = partition(); quicksort(array, left, pi - 1); quicksort(array, pi + 1, right); }


    그림으로 나타내면 다음과 같다.


    퀵소트


    여기까지가 퀵정렬의 전체적인 흐름이다.

    간단하게 퀵정렬이 빠른 정렬에 속하는 이유는 단순히 O(n^2) 을 가진 버블정렬과 비교하면 알 수 있다.

    버블정렬은 모든 배열의 요소에 대해 인덱스를 하나하나 증가하면서 비교해나간다.

    즉, 인접한 요소를 비교한다는 것은 짧은 거리를 통해 비교한다고 보자.

    퀵정렬의 경우에는 인접한 요소가 아닌 서로 먼 거리에 있는 요소를 교환하는 것을 통해 차이를 체감할 수 있을 것이다.


    하지만 위에서 언급했듯이, 퀵정렬 또한 최악의 경우 시간복잡도가 O(n^2) 이 나온다.

    이 경우에는 요소들이 역순으로 존재했을 때를 예로 들 수 있다.


    퀵소트


    위와 같이 퀵소트의 장점을 전혀 살리지 못하고 있는 모습을 볼 수 있다.

    하지만 설계를 통해 개선할 수 있기에 크게 문제되지않는다.

    지금껏 피벗에 있어, 첫번째 요소를 선택하는 방식을 통해 설명했다.

    첫번째 요소를 선택했기 때문에 역순과 같은 경우 이러한 문제점이 발생한다.

    그렇기에 단순히 피벗을 중간 요소로 선택한다면, 이 문제를 해결할 수 있다.


    기존 코드에서 피벗의 첫번째 요소와 중간 요소를 교환만 해주면 된다.


    public int partition(int[] array, int left, int right) { int mid = (left + right) / 2; swap(array, left, mid); ................ }


    결과적으로 최악의 경우인 O(n^2) 를 피할 수 있다.

    또한 다른 O(nlogn) 의 시간복잡도를 가지는 다른 소트보다 빠르다고 알려져있다.

    그 이유는 먼 거리 교환 처리와 캐시 효율(한번 선택된 기준은 제외한다) 등으로 인해 웬만한 O(nlogn) 보다 빠르게 동작한다.


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    private void solve() {
        int[] array = { 80706050403020 };
        quicksort(array, 0, array.length - 1);
     
        for (int v : array) {
            System.out.println(v);
        }
    }
     
    public static int partition(int[] array, int left, int right) {
        int mid = (left + right) / 2;
        swap(array, left, mid);
     
        int pivot = array[left];
        int i = left, j = right;
     
        while (i < j) {
            while (pivot < array[j]) {
                j--;
            }
     
            while (i < j && pivot >= array[i]) {
                i++;
            }
            swap(array, i, j);
        }
        array[left] = array[i];
        array[i] = pivot;
        return i;
    }
     
    public static void swap(int[] array, int a, int b) {
        int temp = array[b];
        array[b] = array[a];
        array[a] = temp;
    }
     
    public static void quicksort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
     
        int pi = partition(array, left, right);
     
        quicksort(array, left, pi - 1);
        quicksort(array, pi + 1, right);
    }
    cs


    댓글 6

Designed by Tistory.