퀵소트는 최악의 경우 O(N^2), 평균적으로 O(NlogN)의 시간복잡도를 가집니다.

또한 퀵소트는 불안정 정렬로 분류됩니다.

퀵소트에는 피벗이라는 개념이 있습니다. 피벗을 선택하는 방법은 첫번째요소, 중간요소, 마지막요소, 랜덤요소를 선택하는 등 여러가지 방식이 있습니다. 그리고 피벗을 어떻게 선택하느냐에 따라 처리속도가 상이할 수 있죠.

원리

1. 피벗을 선택한다
2. start(왼쪽)포인터를 오른쪽으로 이동시키며 피벗보다 큰 수를 찾는다.
3. end(오른쪽)포인터를 왼쪽으로 이동시키며 피벗보다 작은 수를 찾는다.
4. start와 end를 교환한다.
5. 위 과정을 start<end일때 까지 반복한다
6. 이를 재귀적으로 호출한다

장점

• 머지소트와 달리 별도의 추가적인 저장공간이 필요하지 않습니다.
• 캐시효율성을 활용해 왠만한 NlogN정렬 알고리즘 보다 효율적입니다.

단점

• 데이터 분포에 영향을 많이 받습니다.
• 불안정 정렬입니다.

public class QuickSort {
    public static void main(String[] args) {
        int[] arr= {3,2,1,4,5,6,7,-1,-2};
        callQuickSort(arr);
        for(int x : arr){
            System.out.print(x+" ");
        }
        System.out.println();
    }
    public static void callQuickSort(int[] arr){
        quickSort(arr, 0, arr.length-1);
    }
   public static void quickSort(int[] arr,  int start, int end){
        int part2 = Partition(arr, start, end);
        if(start<part2-1){
            quickSort(arr, start, part2-1);
        }
        if(part2<end){
            quickSort(arr,part2,end);
        }
   }
   public static int Partition(int[] arr, int start, int end){
        int pivot = arr[(start+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;
   }
   public static void swap(int[] arr, int a, int b){
        int tmp = arr[a];
        arr[a]=arr[b];
        arr[b]=tmp;
   }

}