[정렬] 퀵 정렬

퀵 정렬

퀵 정렬의 메커니즘은 크게 다음과 같다.

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

 

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

 

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

 

퀵 정렬은 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않는다. 그러므로 '제자리 정렬(in-place sort)이다.'

 

퀵 정렬은 병합정렬과는 다르게 하나의 피벗을 두고 두 개의 부분리스트를 만들 때 서로 떨어진 원소끼리 교환이 일어나기 때문에 불안정정렬(Unstable Sort) 알고리즘이기도 하다.

 

정렬 방법

1. 피벗을 하나 선택한다.

2. 피벗을 기준으로 양쪽에서 피벗보다 큰 값, 혹은 작은 값을 찾는다. 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾는다.

3. 양 방향에서 찾은 두 원소를 교환한다.

4. 왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가 엇갈리지 않을 때 까지 2번으로 돌아가 위 과정을 반복한다.

5. 엇갈린 기점을 기준으로 두 개의 부분리스트로 나누어 1번으로 돌아가 해당 부분리스트의 길이가 1이 아닐 때 까지 1번 과정을 반복한다. (Divide : 분할)

6. 인접한 부분리스트끼리 합친다. (Conqure : 정복)

피벗을 선택하는 과정은 여러 방법이 있는데, 대표적으로 세 가지가 있다.

현재 부분배열의 가장 왼쪽 원소가 피벗이 되는 방법, 중간 원소가 피벗이 되는 방법, 마지막 원소가 피벗이 되는 방법이다.

왼쪽 피벗 방법

코드

 private static void 퀵정렬(int[] arr){
        leftPivot(arr, 0, arr.length-1);
    }

    /**
     * 왼쪽 피봇
     * */
    private static void leftPivot(int[] arr, int lo, int hi){
        if (lo>=hi) return;

        int pivot = partitionLeft(arr, lo, hi);

        leftPivot(arr, lo, pivot-1);
        leftPivot(arr, pivot+1, hi);
    }

    private static int partitionLeft(int[] arr, int left, int right) {
       int lo = left;
       int hi = right;

       int pivot = arr[left];

       while (lo<hi){

           while (arr[hi]>pivot && lo<hi){
               hi--;
           }

           //왼쪽 피봇이기 때문에 같다 라는 조건이 들어감
           while (arr[lo]<=pivot && lo<hi){
               lo++;
           }

           swap(arr, lo, hi);
       }
        swap(arr, left, lo);

       return lo;
    }

    private static void swap(int[] arr, int lo, int hi) {
        int temp = arr[lo];
        arr[lo]=arr[hi];
        arr[hi]=temp;
    }

 

장점

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

단점

1. 특정 조건하에 성능이 급격하게 떨어진다.( 정렬 된 상태의 배열을 정렬하고자 할 경우)
2. 재귀를 사용하기 때문에 재귀를 사용하지 못하는 환경일 경우 그 구현이 매우 복잡해진다.

출처:

https://st-lab.tistory.com/179