퀵 정렬 (Quick Sort)

1. 정의 👨‍🚀

퀵 정렬

  퀵 정렬(Quick Sort)은 분할 정복 방법을 이용하는 정렬 알고리즘이다. 퀵 정렬은 피벗(Pivot)을 기준으로 분할과 정복이 이루어지게 된다.

  퀵 정렬은 '피벗을 선택하는 방식'과 '재귀 또는 비재귀 방식'의 선택에 따라 다양한 구현 방법이 존재한다. 이번 글에서는 '왼쪽 피벗을 선택하는 방식'과 '재귀 방식'을 통한 퀵 정렬을 알아보도록 하자.

 

2. 동작 방식 🦸‍♂️

  기본적인 동작 방식은 아래와 같다.

1. 배열에서 임의의 원소인 pivot을 선택한다. (해당 글에서는 배열에서 제일 왼쪽 원소를 pivot으로 선택한다.)
2. pivot을 기준으로 pivot보다 작은 원소는 왼쪽으로, pivot보다 큰 원소는 오른쪽에 오도록 배열을 배치한다.
3. pivot을 기준으로 나누어진 왼쪽 배열과 오른쪽 배열에 1~2번의 과정을 반복한다. (재귀 방식을 사용)

  pivot을 기준으로 '어떻게 pivot보다 작은 원소는 왼쪽에, pivot보다 큰 원소는 오른쪽에' 위치하도록 하는지 자세히 알아보자. 왼쪽에서 시작하는 포인터(lo)와 오른쪽에서 시작하는 포인터(hi)를 이용하여 pivot을 기준으로 원소들을 나누게 된다.

1. hi와 lo라는 인덱스를 가리키는 포인터를 설정한다. (흔히 알고 있는 실제 포인터가 아니다.)
2. hi는 pivot보다 작은 값을 만날 때까지 왼쪽으로 이동한다.
3. lo는 pivot보다 큰 값을 만날 때까지 오른쪽으로 이동한다.
4. 두 개의 포인터가 가리키는 값을 바꾼다.
5. lo가 hi보다 작거나 같을 때까지 2~5번을 반복한다.
6. pivot과 lo를 바꿔준다.

  {5, 3, 7, 8, 2, 4, 6}의 배열이 pivot을 기준으로 어떻게 정렬되는지 그림을 통해서 알아보자.

  마지막에 pivot인 5와 lo인 2를 바꿔주면 pivot인 5는 자신의 자리에 찾아간 것이 된다. 그러면 pivot을 기준으로 왼쪽에는 pivot보다 작은 원소들이 오른쪽에는 pivot보다 큰 원소들이 위치하게 된다.

  계속해서 pivot을 기준으로 왼쪽 영역과 오른쪽 영역을 정렬해 보자.

  정렬이 이루어지는 과정에서 3가지만 주목하면 쉽게 이해할 수 있다.

1. hi와 lo가 pivot보다 작은 것을 찾을 때까지, pivot보다 큰 값을 찾을 때까지 이동한다.
2. lo는 hi보다 큰 인덱스를 가리키지 않는다.
3. 더 이상 움직일 수 없으면 pivot과 lo를 교체한다.  

이렇게 나누어진 배열들을 합치게 되면 정렬된 배열이 된다.

 

3. 구현(JAVA) 🧙‍♂️

public static void main(String[] args) {
    int[] array = {5, 3, 7, 8, 2, 4, 6};

    quickSort(array, 0, array.length - 1);
}

static void quickSort(int[] array, int left, int right) {
    if(left >= right)
        return;

    // pivot을 기준으로 
    // 왼쪽에는 pivot보다 작은 것들이
    // 오른쪽에는 pivot보다 큰 것들이
    // 위치하도록 하는 것
    int pivot = partition(array, left, right);

    // 왼쪽 영역에 대해서 다시 정렬
    quickSort(array, left, pivot - 1);
    // 오른쪽 영역에 대해서 다시 정렬
    quickSort(array, pivot + 1, right);
}

static int partition(int[] array, int left, int right) {

    int pivot = array[left];
    int lo = left, hi = right;


    while(lo < hi) {

        // hi가 pivot보다 작은 것을 찾을 때까지 왼쪽으로 이동
        while(pivot < array[hi]) {
            hi--;
        }

        // lo가 pivot보다 큰 것을 찾을 때까지 오른쪽으로 이동
        // lo는 hi보다 큰 인덱스 값을 가질 수 없다!!
        while(lo < hi && pivot >= array[lo]) {
            lo++;
        }

        // lo가 가르키는 것과 hi가 가르키는 것을 교체
        swap(array, lo, hi);
    }

    // pivot과 lo를 교체
    // 교체하게 되면 pivot을 기준으로 왼쪽에는 작은 값
    // 오른쪽에는 큰 값들이 위치함.
    array[left] = array[lo];
    array[lo] = pivot;

    // pivot의 위치를 return
    return lo;
}

private static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

 

4. 시간복잡도 & 공간복잡도 🦹‍♂️

1. 시간복잡도

  퀵 정렬의 시간복잡도는 pivot이 어떻게 선택되는지에 따라서 달라진다.

  일반적으로 N개의 노드에 대하여 이진트리의 높이는 logN이 되고 각 레벨에서 N번의 비교와 정렬이 일어난다. (병합 정렬 참고) 그렇기 때문에 일반적인 상황에서의 시간복잡도는 O(N logN)이 된다.

  하지만 최악의 경우는 얘기가 달라진다. pivot이 계속해서 가장 작은 값이나 큰 값이 되면(이미 오름차순이나 내림차순으로 정렬이 되어 있는 경우) 트리의 높이 logN이 아닌 N이 되게 된다. 그러므로 최악의 경우 시간복잡도는 O(N^2)가 된다.

	최선(BEST)	평균(AVERAGE)	최악(WORST)
시간복잡도	O(N logN)	O(N logN)	O(N^2)

2. 공간복잡도

  공간복잡도의 경우 주어진 배열 안에서 교환(swap)이 일어나므로 O(N)이다.

 

5. 장점 & 단점 👨‍🔬

1. 장점

• 시간복잡도가 O(N logN)인 다른 정렬 알고리즘에 비해 상대적으로 빠르다. (한번 결정된 pivot이 다음 연산에서 제외된다는 특성 때문)
• 추가적인 메모리 공간을 필요로 하지 않는다.

2. 단점

• 특정 조건에서 성능이 급격히 떨어진다.
  pivot을 가장 작은 값을 선택하거나 큰 값을 계속해서 선택하여 불균형 분할이 이루어지는 경우
• 재귀를 사용하기 때문에 일정 횟수 이상이면 사용하지 못한다. (재귀를 사용하지 않고 구현하는 방법이 있긴 한데 복잡하다.)

 

해당 글은
Gyoogle님의 퀵 정렬(Quick Sort),
Stranger님의 자바-퀵 정렬(Quick Sort)
를 참고하였습니다.