[Java] 퀵 정렬 Quick Sort

퀵 정렬 - pivot 이라는 임시원소를 하나 설정하고 pivot에 의해 작은원소 큰 원소들로 정렬된다. 재귀적 

pivot은 어떤걸 지정해도 상관이 없다. 밑의 코드는 중간에 위치한 원소를 pivot으로 지정하였다.

두개의 리스트로 분리하는 시간복잡도는 O(n) 이고

각각의 재귀 호출은 각 리스트 숫자의 절반만큼 발생한다

평균 복잡도 O(n log n)

최악의 경우 O(n^2) 

public void sort(int num[], int start, int end) {

    if (start >= end) return;

    int left = start;
    int right = end;
    int pivot = num[(left + end) / 2];

    do {
        while (num[left] < pivot) left++;
        while (num[right] > pivot) right--;
       
        if (left <= right) {
            int temp = num[left];
            num[left] = num[right];
            num[right] = temp;
            System.out.println(Arrays.toString(num));
            left++;
            right--;
        }
    } while (left <= right);
    
    if (start < right) sort(num, start, right);
    if (end > left) sort(num, left, end);

}