[Algorithm Tech] 퀵 정렬(Quick Sort)

* 퀵 정렬(Quick Sort)    =>평균 O(nlogn), 최악 O(n^2)

자바에서 Arrays.sort를 사용하변 내부는 Quick Sort로 구현되어있다.

평균 O(nlogn) 이지만 최악에 O(n^2) 이므로 데이터가 많은 경우 조심해야 한다.

최악의 경우란 아이러니하게도 정렬된 경우를 의미한다.

< 작동 방식 >

퀵 정렬은 pivot값을 중심으로 왼쪽에는 pivot 보다 작은 값들, 오른쪽에는 pivot보다 크거나 같은 값을 정렬한다.

기준을 잡고, left, right 포인터를 이동하면서 num[left] > pivot 과 num[right] < pivot 인 경우 서로 교환한다.

소스 코드와 그림으로 이해하자.

num[left] > pivot, num[right] < pivot 조건을 만족할 때까지 left, right를 움직인다.

pivot을 가운데 값으로 설정하고 Left, Right 를 각 끝의 idx를 지정한다.

둘의 위치를 바꾼다. 이렇게 되면 pivot 왼쪽에는 pivot보다 작은 값, 오른쪽에는 큰값이 정렬된다.

3번 idx를 제외하고 0~2 idx, 4~7 idx를 재귀호출한다.

왼쪽을 먼저 정렬할 때, num[left] > pivot, num[right] < pivot 조건을 만족하는 값을 찾는다.

두 값을 서로 바꾼다.

3번 idx 기준 왼쪽 정렬 끝

오른쪽을 정렬할 때 pivot, left, right를 설정한다.

num[left] > pivot, num[right] < pivot 조건을 만족하는 값을 찾는다.

두 값을 서로 바꾼다. left는 이동하지 않고, right만 이동하는데 조건을 만족하는 값이 없다.

5~7 idx 퀵소트 재귀 호출

num[left] > pivot, num[right] < pivot 조건을 만족하는 값을 찾아 다시 바꿔준다.

< 소스 코드 >

public static int partition(int left, int right, int[] num) {
    int pivot = num[(left + right) / 2];
    while (left <= right) {
        while (num[left] < pivot) left++;
        while (num[right] > pivot) right--;
        if (left <= right) {
            swap(left, right, num);
            left++;
            right--;
        }
    }
    return left;
}
 
public static void QuickSort(int left, int right, int[] num) {
    if (left < right) {
        int pivot = partition(left, right, num);
        if (left < pivot - 1) QuickSort(left, pivot - 1, num);
        if (right > pivot) QuickSort(pivot, right, num);
    }
}