[정렬] Quick Sort

퀵 정렬의 개념

퀵정렬 Worst-case, 불균형 분할

퀵정렬이란?

분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행속도를 보인다.
하지만 역순으로 정렬되거나 이미 정렬된 데이터가 들어오면 비효율적이다.(불균형 분할이 일어남)
병합정렬과 다르게 똑같은 크기의 리스트로 나누는 것이 아닌, 피봇을 기준으로 리스트를 나누게 된다.
병합정렬은 배열을 우선 가장 작은 단위로 나눈 후에 데이터들이 정렬되는 반면에, 퀵 정렬은 데이터를 조건에 맞게 정렬 후 작은 단위로 나눈다.

동작 방식(오름차순 정렬)

1. 리스트 안에 있는 한 요소를 피봇으로 선택한다. (정렬을 위한 기준이라고 보면 된다)
2. 피봇을 기준으로 피봇보다 작은 요소들은 왼쪽으로, 피봇보다 큰 요소들은 피봇들의 오른쪽으로 옮겨진다. 
3. 피봇을 제외한 왼쪽 리스트와 오른쪽 리스트에 대해서 각각 정렬을 수행한다.
4. 위의 과정을 재귀 호출을 이용하여 리스트의 크기가 가장 작은 단위로 쪼개질 때 까지 반복한다. 

2번 과정을 한번 수행할 때마다 최소 데이터(피봇) 한개의 위치가 무조건 정해지므로 반드시 정렬이 이루어진다.

퀵 정렬 구현 

    private void divide(int left, int right) {
        if(left < right) {
            int pivot = sort(left, right);
            divide(left, pivot - 1);
            divide(pivot + 1, right);
        }
    }

    private int sort(int left, int right) {
        int key = numbers[right];
        int l = left, r = right;

        while(l < r) {
            while(l < r && key >= numbers[l]) {
                l++;
            }
            while (l < r && key <= numbers[r]) {
                r--;
            }
            if(l < r) SWAP(l,r);
        }

        numbers[right] = numbers[l];
        numbers[l] = key;

        return l;
    }

    private void SWAP(int a, int b) {
        int temp = numbers[a];
        numbers[a] = numbers[b];
        numbers[b] = temp;
    }

퀵 정렬의 시간 복잡도

퀵 정렬의 Average-case 

위 Average-case의 재귀 트리는 

n^k = n(k=lgn)

이기 때문에 높이는 lgn인 것을 알 수 있다. 

그리고 각 level마다 n번의 비교가 무조건 발생하기 때문에 Average-case 시간 복잡도는

n * lgn인 O(nlgn)이다.

퀵 정렬의 Worst-case 

재귀 트리

따라서 worst-case 일 때 Big-O는

O(n^2)이다.

퀵정렬의 장단점

장점 

1. 한 번 결정된 피봇들이 추후 연산에서 제외되므로 같은 시간 복잡도를 갖는 정렬 중 가장 빠르다.
2. 병합 정렬과 공통적인 접근 방식이지만, 추가적인 저장공간을 쓰지 않는다.

단점

1. 불균형 분할이 일어날 경우 비효율적이다.
2. 특히 이미 정렬된 리스트나 역순인 리스트에 대해서 과도한 수행시간이 걸린다.
3. Unstable Sort이다.