분할정복 알고리즘 - 퀵 정렬 (Quick Sort)

퀵 정렬 (Quick Sort)

정의

- 분할 정복 알고리즘에 속하지만 실제로는 정복후 분할하는 알고리즘.

- 피봇(pivot)을 기준으로 왼쪽에는 피봇 값보다 작은 값이 오고 오른쪽에는 큰 값이 오도록 정렬한다. 그리고 피봇을 기준으로 분할하여 각각 왼쪽, 오른쪽을 재귀 함수를 이용해 정렬한다. 

Java 구현

public class QuickSort {
    public void quickSort(int[] data, int first, int last){
        int left = first;
        int right = last;
        int pivot = data[(first + last)/2];
        
        // Pivot 기준으로 양쪽에 정렬
        //(왼쪽에 피봇보다 작은수, 오른쪽에 피봇보다 큰 수가 위치) 
        do {
            while(data[left] < pivot) 
              left++;
            while(data[right] > pivot) 
              right--;
            if(left <= right){    
                int temp = data[left];
                data[left] = data[right];
                data[right] = temp;
                left++;
                right--;
            }
        } while (left <= right);
        
        // 0 부터 pivot 전까지 
        if(first < right) 
          quickSort(data, first, right); 
      
        // pivot 후 부터 마지막까지 
        if(last > left) 
          quickSort(data, left, last); 
    }
    
    public static void main(String[] args) {
        int data[] = {-1, 50, 100, 3, 2, 1, 11, 30, 14, 20};
        QuickSort quick = new QuickSort();
        quick.quickSort(data, 0, data.length - 1);
        for(int i=0; i<data.length; i++){
            System.out.print(data[i] + " ");
        }
    }
}
 

참고: https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

시간 복잡도

- 피봇 선택이 성능을 좌우함. 

- 지속적으로 피봇이 가장 크거나, 가장 작은 값이 선택될 경우가 최악의 경우이다. 역순으로 정렬된 경우 최악의 경우에 해당한다.

- n개의 입력을 받을 경우 최악의 경우 (n-1) + (n-2) + (n-3) + ....... + 2 + 1 = n(n-1)/2 = O(n^2)이 된다.

- 최선의 경우 균등하게 분포되어 지속적으로 중앙값이 피봇으로 선택될 경우이다. 따라서 이 경우 각 층에서 피봇과 1회씩 비교 된다. 따라서 O(n) * (층수) = O(nlog2n)이다. 

---

최적화 방법 3가지 

출처:퀵소트 의 최적화 방법 (Quick Sort Optimization)

Ideal Pivot Selection Algorithm

Pivot 은 전체 정렬을 위한 element 중 가장 중간에 가까운 값이 선정될 수록 정렬에 효율적이다.

- random pick : 모든 정렬범위의 개체중 랜덤하게 1개를 추출

- start, middle, end compare : 시작, 중간, 끝 개체중 중간 값을 pivot으로 사용

Element Shuffling

- linear random swapping : 배열 가장 앞의 index를 기준으로 하여 N개의 모든 index를 한번씩 random swap 하는 셔플링 기법

Block Partitioning

- 3 way partitioning : 선택된 pivot을 기준으로 중복값을 가운데, 작은값을 왼쪽, 큰값을 오른쪽으로 하여 3개의 block으로 파티셔닝 하는 기법