[정렬] 퀵정렬

퀵정렬 (Quick Sort)

• 매우 빠른 수행속도를 자랑하는 정렬방법, 분할 정복 알고리즘에 해당
• 분할 정복(divide and conquer) 방법 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 합쳐 원래의 문제를 해결하는 전략.

 

• 과정

1. 배열 내에서 하나의 요소(피벗(pivot))를 선택한다.
2. 피벗을 기준으로 피벗보다 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 분류한다. (Divide)
3. 왼쪽, 오른쪽 배열도 피벗을 선택한 후 왼쪽/오른쪽 배열로 분류한다. (재귀)
4. 배열의 크기가 0 혹은 1이 될 때까지 반복한다. (Conquer)
5. 모든 정렬된 배열을 합친다. (Combine)

• 구현

public class Main {
	
	public static void quickSort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int low, int high) {
        if (low >= high) return;

        int mid = partition(arr, low, high);
        sort(arr, low, mid - 1);
        sort(arr, mid, high);
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[(low + high) / 2];
        while (low <= high) {
            while (arr[low] < pivot) low++;
            while (arr[high] > pivot) high--;
            if (low <= high) {
                swap(arr, low, high);
                low++;
                high--;
            }
        }
        return low;
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    

	public static void main(String[] args) {
		int[] array = {2, 4, 1, 5, 3};
		int length = array.length;
		quickSort(array);
	}
}

• 평균 O(nlogn), 최악 O(N^2)의 시간복잡도를 갖는다고 한다.