퀵소트 알고리즘 :: 마이구미

이 글은 정렬 중 퀵소트(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) 보다 빠르게 동작한다.

private void solve() {
    int[] array = { 80, 70, 60, 50, 40, 30, 20 };
    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);
}