퀵 정렬

하나의 리스트를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분리스트, 다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 위 처럼 재귀적으로 수행하여 정렬하는 방법

퀵 정렬은 기본적으로 '분할 정복' 알고리즘을 기반으로 정렬되는 방식이다.
다만 병합정렬과 다른 점은 병합정렬의 경우 하나의 리스트를 '절반'으로 나누어 분할 정복을 하고, 퀵 정렬(Quick Sort)의 경우 피벗의 값에 따라 피벗보다 작은 값을 갖는 부분리스트와 피벗보다 큰 값을 갖는 부분리스트의 크기가 다를 수 있기 때문에 하나의 리스트에 대해 비균등하게 나뉜다는 점이다.

실제로도 정렬 방법에서 병합 정렬과 퀵 정렬은 많이 비교된다.
(다만 일반적으로 병합정렬보다 퀵정렬이 빠르다.)

퀵 정렬은 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않는다. 그러므로 '제자리 정렬'이다
퀵 정렬은 병합정렬과는 다르게 하나의 피벗을 두고 두 개의 부분리스트를 만들 때 서로 떨어진 원소끼리 교환이 일어나기 때문에 불안정정렬 알고리즘 이기도 하다

1. 피벗을 하나 선택한다
2. 피벗을 기준으로 양쪽에서 피벗보다 큰 값, 혹은 작은 값을 찾는다. 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾는다
3. 양 방향에서 찾은 두 원소를 교환한다
4. 왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가 엇갈리지 않을 때까지 2번으로 돌아가 위 과정을 반복한다
5. 엇갈린 기점을 기준으로 두 개의 부분리스트로 나누어 1번으로 돌아가 해당 부분리스트의 길이가 1이 아닐 때 까지 1번 과정을 반복한다 (Divide : 분할)
6. 인접한 부분리스트끼리 합친다. (Conqure : 정복)

대부분의 구현은 현재 리스트의 양 끝에서 시작하여 왼쪽에서는 피벗보다 큰 값을 찾고, 오른쪽에서는 피벗보다 작은 값을 찾아 두 원소를 교환하는 방식이다.
그래야 피벗보다 작은 값은 왼쪽 부분에, 피벗보다 큰 값들은 오른쪽 부분에 치우치게 만들 수 있기 때문이다. 이를 흔히 호어(Hoare) 방식이라고 한다

피벗을 선택하는 과정은 여러 방법이 있는데, 대표적으로 세 가지가 있다.
현재 부분배열의 가장 왼쪽 원소가 피벗이 되는 방법, 중간 원소가 피벗이 되는 방법, 마지막 원소가 피벗이 되는 방법이다.
위 3가지 방식 모두 특정은 '피벗'을 하나 설정하고 피벗보다 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 치중하도록 하는 것이다. 이 과정을 흔히 파티셔닝(Partitioning)이라고 한다
파티셔닝을 했따면 파티셔닝을 통해 배피 된 피벗의 위치를 기준으로 좌우 부분리스트로 나누어 각각의 리스트에 대해 재귀호출을 해주면 된다

위 원리를 이해해야 앞으로 구현할 이중 피벗 퀵 정렬 또한 이해하기가 쉽다

[장점]
1. 특정 상태가 아닌 이상 평균 시간 복잡도는 NlogN이며, 다른 NlogN 알고리즘에 비해 대체적으로 속도가 매우 빠르다. 분할정복 방식은 merge sort에 비해 2~3배 정보 빠르다
2. 추가적인 별도의 메모리를 필요로 하지 않으며 재귀 호출 스택프레임에 의한 공간복잡도는 logN으로 메모리를 적게 소비한다.

[단점]
1. 특정 조건하에 성능이 급격하게 떨어진다
2. 재귀를 사용하기 때문에 재귀를 사용하지 못하는 환경일 경우 그 구현이 매주 복잡해진다
퀵 정렬의 최대 단점은 정렬 된 상태의 배열을 정렬하고자 할 때다.
=> 중간 피벗을 사용하면 정렬된 배열이더라도 거의 중간지점에 가까운 위치에서 왼쪽 리스트와 오른쪽 리스트가 균형에 가까운 트리를 얻어낼 수 있기 때문이다.

위와 같이 정렬하는 경우 별도의 배열이나 플래그(flag)를 부여하지 않는 한 대부분의 정렬의 경우 안정정렬은 안된다.

정렬된 상태에서 성능이 떨어진 다는 점을 고려할 때, 임계값을 설정하여 일정 크기 이하로 떨어 질 경우 정렬 된 배열에서 좋은 성능을 발휘하는 삽입정렬을 하도록 바꾸면 거의 정렬 된 배열에서도 어느정도 성능 하락을 방지할 수 있으니 혼합하여 구현해보는 방법도 있다

// 왼쪽 피벗 선택 방식
public class QuickSort {
    public static void sort(int[] a){
        pivot_sort(a,0,a.length-1);
    }

    private static void pivot_sort(int[] a, int lo, int hi) {
        // lo가 hi보다 크거나 같다면 정렬할 원소가 1개 이하이므로 정렬하지 않고 리턴한다
        if(lo>=hi){
            return;
        }
        int pivot = partition(a,lo,hi);
        // Recursion
        pivot_sort(a,lo,pivot-1); // left
        pivot_sort(a,pivot+1,hi); // right
    }

    private static int partition(int[] a, int left, int right) {
        int lo = left;
        int hi = right;
        int pivot = a[left]; // 부분리스트의 왼쪽 요소를 피벗으로 설정

        while(lo<hi) {
            // hi가 lo보다 크면서 hi의 요소가 pivot보다 작거나 같은 찾을 때까지 hi 감소
            while (hi > lo && a[hi] > pivot) {
                hi--;
            }
            // hi가 lo보다 크면서 lo의 요소가 pivot보다 큰 원소를 찾을 때 까지 lo증가
            while (hi > lo && a[lo] <= pivot) {
                lo++;
            }
            swap(a,lo,hi); // 교환 될 두 원소를 찾았으면 두 요소를 바꾼다
        }
        // 마지막으로 맨 처음 pivot으로 설정했던 위치(a[left])의 요소와 lo가 가리키는 원소를 바꾼다
        swap(a,left,lo);
        // 두 요소가 교환되었다면 피벗이였던 요소는 lo에 위치하므로 lo 반환
        return lo;
    }

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

    private static void printArray(int[] arr) {
        for(int i:arr){
            System.out.print(i+" ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {3, 9, 4, 7, 5, 0, 1, 6, 8, 2};
        printArray(arr);
        sort(arr);
        printArray(arr);
    }
}
// 3 9 4 7 5 0 1 6 8 2 
// 0 1 2 3 4 5 6 7 8 9 결과