퀵 소트 (Quick Sort)

오늘은 Quick Sort를 구현해 보려 한다.

 

퀵 소트는 기준이 되는 값(pivot)을 하나 잡고 , 기준 값 보다 작거나 같은 값을 가지고 있는 자료는 앞쪽으로 보내고, 큰 값을 가지고 있는 자료는 뒤쪽으로 보내 기준 값을 기준으로 분할해서 정렬을 진행하는 방법을 의미한다.

 

정렬 방식은 아래와 같다.

1. 기준 값(pivot)을 정한다. 

2. pivot 앞에는 pivot 보다 작은 값이 오고, pivot 뒤에는 큰값이 오도록 배열을 둘로 분할한다.

3. 분할된 두 개의 배열에 대하여 재귀함수를 통하여 정렬하는 과정을 반복한다.

 

위처럼 이렇게 정렬이 된다.

 

시간복잡도는 평균적인 경우에는 O(nlogn) 이지만 최악의 경우는  O(N²) 이다.

최악의 경우는 피봇을 최소값이나 최대값을 선택할때이다. ( 즉 정렬된 데이터에 퀵소트를 사용하면 ... 성능에 엄청난 영향을 미친다고 생각하면된다.)

 

아래는 구현 예제이다.

public class QuickSort {
    public static void main(String[] args) {
        int[] data = {3,5,-5,1,4,0};

        int[] result = quickSort(data,0, data.length-1);

        for(int num : result) {
            System.out.println(num);
        }
    }

    public static int[] quickSort(int[] data, int l , int r) {
        int left = l;
        int right = r;
        int pivot = data[(l + r) / 2];

        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);

        if(l < right) quickSort(data, l, right);

        if(r > left) quickSort(data, left, r);

        return data;
    }
}