[Java][알고리즘][정렬] Quick Sort / 퀵 정렬

퀵 정렬

가장 많이 쓰이는 정렬 알고리즘이다. 최악의 경우는 O(N^2) 이지만 실제로 수행해보면 합병 정렬보다 더 좋은 성능을 낸다. pivot을 기준으로 pivot보다 작은 원소들은 pivot의 왼쪽, 큰 원소들은 오른쪽에 위치 시켜 분할 한 후, 새롭게 pivot을 만들어 재귀적으로 정렬하는 알고리즘이다.

 

위 예시를 보면서 이해해보도록 하자. 일반적으로는 맨 왼쪽 원소를 pivot으로 정한다. 

pivot을 중간값으로 잘 정하는게 퀵 정렬에서의 성능을 좌우한다. 이를 위해 3개의 원소를 정해서 중간값을 pivot으로 하는 Median of Three나 9개의 원소를 뽑아 3개씩 나눠 각 중간값을 구하고 다시 그 3개 중에서 중간값을 정해 pivot으로 정하기도 하지만.. 맨 왼쪽으로 그냥 하도록 하자. (귀찮아서는 아닐 것이다.)

 

코드

public class Quick {
    public static boolean isless(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }
    
    public static void swap(Comparable[] arr, int i,int j) {
        Comparable p = arr[i];
        arr[i] = arr[j];
        arr[j] = p;
    }
    
    public static void show(Comparable[] arr) {
        for(int i=0; i<arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    
    public static void Sort(Comparable[] a) {
        Sort(a,0,a.length-1);
    }
    
    public static void Sort(Comparable[] a, int low, int high) {
        if(low>=high) return;
        int j = partition(a,low,high);
        show(a);
        Sort(a,low,j-1);
        Sort(a,j+1,high);
    }
    
    public static int partition(Comparable[] a, int pivot, int high) {
        int i = pivot+1;
        int j = high;
        Comparable p = a[pivot];
        
        while(true) {
            while(i <= high && !isless(p,a[i])) i++;
            while(j >= pivot && isless(p,a[j])) j--;
            if(i>=j) break;
            swap(a,i,j);
        }
        swap(a,pivot,j);
        return j;
     }
}