1. 어디서 나왔니?

보통 자바의 Arrays.sort(arr)은 Dual-Pivot QuickSort을 쓴다고 한다. 그렇다면 QuickSort는 무엇일까? 한번 알아보도록 하자.

2. 퀵정렬이란?

퀵 정렬이란 특정 피벗 기준으로 왼쪽은 피벗보다 작은값 오른쪽은 피벗보다 큰 값으로 정렬해나가는 방법이다.

피벗은 중앙값인 5로 잡았을 때, 위의 사진처럼 start와 end를 양 끝단으로 잡는다.

그리고 start를 피벗보다 작은 값이면 계속 ++를 시켜준다. 만약 피벗보다 큰거나 같은 값이이 나온다면 멈춘다.

while(start<pivot) -> start++ 이런식으로 구현

또한 end를 피벗보다 큰 값이면 계속 --를 시켜주고 만약 작거나 같은 값이 나온다면 멈춘다.

그리고 아래 사진처럼 서로 스왑한다.

그리고 s와 e가 같아지면 한 사이클이 종료된 것이다.

첫번째 사이클이 돌면 피벗을 기준으로 정렬된 양쪽 구간에서 또 각자의 피벗을 정하고 한번 더 실행된다. 만약 왼쪽 구역이 하나가 남거나 오른쪽 구역이 하나가 남았을 시, 해당 부분은 퀵소트를 더 이상 하지 않는다. 아래와 같은 상항이 그 예시이다.

만약 이렇게 계속 퀵정렬를 하다보면 아래와 같은 트리가 완성된다.

맨 처음 사진인 경우는 QuickSort(0,0)일 것이고 해당 스탑 조건은 start<pivot-1 이런식으로 될 것이다.

3. 시간복잡도

위와 같은 트리의 형태로 보았을 때, 시간 복잡도는 nlogn이 나오는 것을 확인할 수 있다.

4. 수도 코드

가. Partition에서 Swap
1) pivot을 배열의 중앙 값으로 설정한다.
2) start와 end를 0 그리고 배열의 마지막 인덱스로 할당한다.
3) arr[start]가 피벗보다 작으면 start++
4) arr[end]가 피벗보다 크면 end--
6) start와 end가 stop되고, start<=end라면 arr[start]와 arr[end]를 swap한다.
7) 위 과정을 start<=end동안 반복한다.
8) start를 Return한다.

❓ : 왜 Start를 Return할까?
파티션 안에서 스왑이 이루어지고, 결국 2개로 나눠진 첫번째 배열의 인덱스를 start가 가리키기 때문이다.

나. 전체적인 흐름
1) 파티션 진행
2) 파티션 후 왼쪽배열의 원소가 2개 이상이면 다시 퀵소트를 재귀적으로 호출해서 파티션을 진행한다.
3) 오른쪽도 3번과 동일

💡 그렇다 재귀 = 트리이므로 트리형태로 퀵소트가 진행된다.

5. 코드

import java.util.Arrays;

public class P19 {

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

    static void quickSort(int[] arr, int start, int end) {
        int part2 = partition(arr,start,end); // part2 : 두번째 배열의 첫번째 idx
        if(start+1<part2){
            partition(arr,start,part2-1);
        }
        if(part2<end){
            partition(arr,part2,end);
        }

    }
    static int partition(int[] arr, int start, int end){
        int pivot = arr[(arr[start]+arr[end])/2];

        while(start<=end){
            while(arr[start]<pivot) start++;
            while(arr[end]>pivot) end--;
            if(start<=end){
                swap(arr, start, end);
                start++;
                end--;
            }
        }

        return start;
    }

    static void swap(int[] arr, int start, int end){
        int tmp = arr[start];
        arr[start] = arr[end];
        arr[end] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{2,3,4,1};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));

    }
}