퀵정렬(Quick Sort)

분할정복 기반의 정렬

 

정렬방법

1. 데이터 집합에서 기준점이 될 피벗 값 선정

2. 피벗을 기준으로 피벗보다 작은 값을 왼쪽, 큰 값을 오른쪽으로 2개의 부분 집합을 만들어냄

3. 왼쪽, 오른쪽 각각의 부분집합에서 앞선 1,2번 반복

4. 부분집합내 데이터가 1이 될때까지 반복한다.

 

시간복잡도

최선 : NLogN

재귀 호출이 일어날 때 마다 부분 리스트의 크기가 절반씩 줄어들게 되므로 n개의 원소에 대해 logN만큼 연산을 하기때문에 시간복잡도는 NLogN이 된다.

최악 : n^2

피벗 선택이 항상 데이터 집합의 최소값을 선정했다고 가정한다면 부분집합의 크기가 절반씩 줄어드는 것이 아닌 n n-1 n-2 ... 로 줄어드므로 n번의 연산을 거치게 되면 O(n^2)이 되게 된다.

 

공간복잡도

정렬을 함에 있어 분할된 데이터 공간이 logN 만큼 공간을 차지하게 된다.

Code

피벗 선정은 항상 중앙값을 기준으로 한다고 가정

public class MyQuickSort {

    public int[] MyQuickSort(int[] data) {
        sort(data, 0, data.length-1);
        return data;
    }

    public void sort(int[]data, int left, int right) {
        int pivotIdx = (left + right) / 2;
        int pivot = data[pivotIdx];
        int leftIdx = left;
        int rightIdx = right;

        if (leftIdx >= rightIdx) {
            return;
        }

        while (leftIdx <= rightIdx) {
            while (data[leftIdx] < pivot) {
                leftIdx++;
            }
            while (data[rightIdx] > pivot) {
                rightIdx--;
            }
            if (leftIdx <= rightIdx) {
                swap(data, leftIdx, rightIdx);
                leftIdx++;
                rightIdx--;
            }
        }
        sort(data, left, pivotIdx-1);
        sort(data, pivotIdx+1, right);
    }

    private static void swap(int[] data, int idx1, int idx2) {
        int temp = data[idx1];
        data[idx1] = data[idx2];
        data[idx2] = temp;
    }
}