퀵정렬 Quick Sort

정의

오름차순으로 정렬하는 기초적인 알고리즘 중 하나

• 가장 중요한 알고리즘.
• 어떤 언어든 가장 중요하고 많이 씀.
• 실무에서 많이 사용.
• 최악의 상황을 줄이는 법은 랜덤으로 위치를 선정.
• 그래도 $O(n^2)$이 절대 있어서는 안된다면, 다른 정렬을 사용해야 함.

구조

부분 정복 Decrease and Conquer

알고리즘 순서

pivot을 기준으로 둘로 나눠서 재귀적으로 순회.

1. pivot값보다 작은 값은 왼쪽 큰 값은 오른쪽으로 분류한다. 단 길이변환을 하지 않기위해 아래 과정을 진행한다
2. 기준점인 pivot을 정한다. 보통 맨 오른쪽 값 혹은 맨 왼쪽값을 잡음(로무토 or 호어 분할법에 따라 다름)
3. 첫번째 값을 선택값라고 정한다.
4. 체크하는 값이 pivot값보다 작으면, 선택값과 체크하는 값을 교환하고 선택값을 오른쪽으로 이동한다
5. 체크하는 값이 pivot값보다 크면, 체크하는 값을 오른쪽으로 이동한다
6. 체크하는 값이 pivot에 도착하면, 선택값과 pivot을 교환한다
7. 2~6번 과정을 재귀적으로 순회한다.

pivot 값을 정하는 법

1. 로무토Lomuto 분할법
   • pivot : 가장 오른쪽 값
   • 선택값(i) 시작점 : 0
   • 비교값(j) 시작점 : 0
2. 호어Hoare 분할법
   • pivot : 가장 왼쪽 값
   • 선택값(i) 시작점 : 1
   • 비교값(j) 시작점 : 가장 오른쪽 값
3. 랜덤으로 선택

자바 코드-로무토 Lomuto 분할법

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

    //로무토Lomuto 분할법을 이용한 quick sort 구현
    public static void quickSortRecur(int[] input, int left, int right) {

        //quick sort 마지막 나가는 조건
        //right >= left로 하면 내림차순으로 정렬됨(9,8,7)
        //현재 오름차순(7,8,9)
        if (left >= right) {
            return;
        }

        // pivot을 중심으로 작은수 큰수 정렬후, pivot 포지션 반환
        int pivotPos = partition(input, left, right);

        //왼족으로 분할된 리스트
        quickSortRecur(input, left, pivotPos - 1);
        //오른족으로 분할된 리스트
        quickSortRecur(input, pivotPos + 1, right);

    }

    public static void swap(int[] input, int a, int b) {
        int temp = input[a];
        input[a] = input[b];
        input[b] = temp;

    }

    public static int partition(int[] input, int left, int right) {
        int pivot = input[right];

        int i = (left - 1);
        for (int j = left; j < right; ++j) {
            if (input[j] < pivot) {
                ++i;
                swap(input, i, j);
            }
        }
        swap(input, (i + 1), right);
        return i + 1;
    }

자바 코드- 호어 Hoare 분할법

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

    //호어Hoare 분할법을 이용한 quick sort 구현
    public static void quickSortRecur(int[] input, int left, int right) {

        //quick sort 마지막 나가는 조건
        if (left >= right) {
            return;
        }

        // pivot을 중심으로 작은수 큰수 정렬후, pivot 포지션 반환
        int pivotPos = partition(input, left, right);


        //왼족으로 분할된 리스트
        quickSortRecur(input, left, pivotPos);
        //오른족으로 분할된 리스트
        quickSortRecur(input, pivotPos + 1, right);

    }

    public static void swap(int[] input, int a, int b) {
        if (a != b) {
            int temp = input[a];
            input[a] = input[b];
            input[b] = temp;
        }

    }

    public static int partition(int[] input, int left, int right) {
        int pivot = input[left];
        int i = left - 1;
        int j = right + 1;

        while (true) {
            do {
                ++i;
            } while (input[i] < pivot);

            do {
                --j;
            } while (input[j] > pivot);

            if (i >= j) {
                return j;
            }

            swap(input, i, j);
        }
    }

평균 시간 복잡도 Avg. time complexity

$O(n;log;n)$

최악 시간 복잡도 Worst time complexity

$O(n^2)$

공간 복잡도 space complexity

$O(log;n)$

안정성 stability

no

계산법

순회 횟수

• 기본적으로 도는 루프: $O(n)$
• 매 단계에서 좌우가 균등하게 나뉘면 : $O(log;n)$
• 매 단계에서 한쪽으로만 몰리는 경우 : $O(n)$

시간 복잡도

• 매 단계에서 좌우가 균등하게 나뉘면 : $ O(n \cdot log;n)=O(n;log;n)$
• 매 단계에서 한쪽으로만 몰리는 경우 : $O(n \cdot n)=O(n^2)$