09. 퀵 정렬 (Quick Sort)

정의

- 정렬 알고리즘의 꽃

- 기준점(Pivot) 을 정해서, 기준점보다 작은 데이터는 왼쪽(left) 큰 데이터는 오른쪽(right)으로 모으는 함수

- 각 왼쪽 (left), 오른쪽 (right) 는 재귀용법을 사용해서 다시 동일함수를 호출하여 위 작업을 반복한다

- 함수는 왼쪽 (left) + 기준점 (pivot) + 오른쪽 (right) 을 리턴한다

- 왼쪽 퀵 정렬 일 때 0번째가 가장 작은 수 일 경우 최악의 성능이 나옴
(빠르긴 하나, 상황에 따라 성능이 차이가 날 수 있기 때문에 안정적이지 않은 편이다. 그 에 비해 같은 분할정복의 정렬 중 병합 정렬은 항상 동일한 성능을 가지고 있어 안정적이고 퀵 정렬보다는 아니지만 그에 준수 한 속도를 가지고 있다)

https://coding-factory.tistory.com/615

분석

- 병합정렬 (Merge Sort) 와 유사, 시간 복잡도는 O(n log n)

- 단, 최악의 경우 맨 처음 pivot 이 가장 크거나, 가장 작으면 모든 데이터를 비교하는 상황이 나온다

O(n²) → 평균적으로는 병합정렬보다 빠름

 

퀵 정렬 (Quick Sort)

public class QuickSort {

    public static void main(String[] args) {

        int[] arr = new Random().ints(10, 0, 100).toArray();;

        leftPivotSort(arr, 0, arr.length - 1);

    }


    private static void leftPivotSort(int[] arr, int lowerIdx, int higherIdx) {

        // 왼쪽 인덱스가 오른쪽 인덱스보다 큰 경우 정렬 종료
        if (lowerIdx >= higherIdx) {
            System.out.println(Arrays.toString(arr));
            return;
        }

        // 파티션 나누기 (왼쪽과 오른쪽)
        int pivotIdx = partition(arr, lowerIdx, higherIdx);
        leftPivotSort(arr, lowerIdx, pivotIdx - 1);
        leftPivotSort(arr, pivotIdx + 1, higherIdx);

    }

    private static int partition(int[] arr, int leftIdx, int rightIdx) {

        int lowerIdx = leftIdx;
        int higherIdx = rightIdx;

        // 피벗의 값은 가장 왼쪽
        int pivotValue = arr[leftIdx];

        // 왼쪽의 인덱스가 더 작을 때 반복한다
        while (lowerIdx < higherIdx) {

            while (arr[higherIdx] > pivotValue && lowerIdx < higherIdx) {
                higherIdx--;
            }

            while (arr[lowerIdx] <= pivotValue && lowerIdx < higherIdx) {
                lowerIdx++;
            }

            // swap
            int temp = arr[lowerIdx];
            arr[lowerIdx] = arr[higherIdx];
            arr[higherIdx] = temp;
        }

        // swap
        int temp = arr[leftIdx];
        arr[leftIdx] = arr[lowerIdx];
        arr[lowerIdx] = temp;

        return lowerIdx;
    }
}