퀵 정렬 Quick Sort

퀵 정렬 Quick Sort *한 원소 기준(pivot)으로 왼쪽 오른쪽으로 보내기!!

퀵 소트는 가장 빠른 알고리즘은 아니지만 평균적으로 매우 효율적인 알고리즘이다.
기본 아이디어는 배열의 한 원소를 기준으로 (보통 arr[0]) 작거나 같은 요소는 왼쪽으로, 큰 값은 오른쪽으로 보내고 각각 왼쪽과 오른쪽 배열을 다시 재귀적으로 정렬하는 것이다.
가장 첫 원소를 기준으로 작거나 같은 값은 모두 왼쪽, 큰것은 오른쪽으로 보내고 작거나 같은 쪽의 마지막 요소와 첫 요소를 스왑한다.
밑의 예시에서는 pivot을 배열 맨 앞의 원소로 잡았다.

public class Main
{
    public static int partition(int[] arr, int start, int end)
    { // start 기준으로 분할
        int i = start + 1; // p보다 작거나 같은 요소들 시작 부분
        int j = end; // p보다 큰 요소들 시작 부분
        int temp;
        while (i <= j)
        { // 제자리일떄 한칸씩 다음으로
            if (arr[i] <= arr[start]) i++; // 작거나 같은 요소들 제자리에 있을때
            else if (arr[j] > arr[start]) j--; // 큰 요소들 제자리에 있을때
            else // 둘다 제자리 아닐때 스왑 후 각각 한칸씩
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        } // i > j시 종료 후 p와 작거나 같은값 끝 요소 스왑
        temp = arr[start];
        arr[start] = arr[j];
        arr[j] = temp;
        
        return j; // 자리 확정된 pivot값 반환
    }
    
    public static void quickSort(int[] arr, int start, int end)
    {
        int pivot; // 확정된 기준값
        if (start < end)
        {
            pivot = partition(arr, start, end);
            quickSort(arr, start, pivot-1); // pivot 왼쪽 값 
            quickSort(arr, pivot+1, end); // pivot 오른쪽 값
        }
    }
    
    public static void printArr(int[] arr)
    {
        for (int i=0; i<arr.length; i++)
		    System.out.print(arr[i]+" ");
		 System.out.println();
    }
    public static void main(String[] args)
    {
        int[] arr = {91, 85, 68, 70, 98, 24, 1,2,3,4,5,6,7,8,9};
        quickSort(arr, 0, arr.length-1);
        printArr(arr);
    }
}

퀵 소트는 pivot(기준) 선택에 따라 속도가 달라진다.
퀵 소트의 최악의 경우는 배열이 이미 정렬된 경우 피벗을 최대 혹은 최솟갑으로 선택한 경우이다. 이 경우 i혹은 j가 매번 끝까지 가야 하므로 n번 동안 n-1개와 비교를 해야 한다. 즉 이 경우 시간복잡도는 O(N^2)이 된다.
하지만 평균적으로 Θ(NlogN)의 시간복잡도를 갖게 되고 최악의 경우가 나올 확률은 매우 적다.
병합 정렬의 경우 모든 경우에 시간복잡도가 O(NlogN)이지만 퀵 소트는 평균의 경우 Θ(NlogN), 최악의 경우 Θ(N^2)를 갖는다.