[SORT] Quick Sort (퀵 정렬)

Goal

정렬 알고리즘 중 Quick Sort 에 대해 알기
Quick Sort의 장· 단점
시간 복잡도 이해하기
자바로 구현할 줄 알기

Quick Sort (퀵 정렬) 알고리즘

★분할 정복(divide and conquer) 방법
작은 2개의 문제로 분리하고, 각각을 해결한 후, 결과를 다시 모아 원래의 문제를 해결한다.

설명

• 리스트 안에 한 요소를 선택 - 선택한 요소를 피벗(pivot)이라고 한다.
• pivot을 기준으로 작거나 큰 요소의 위치를 옮긴다.
  • pivot 기준으로 왼쪽 : pivot 보다 작은 요소
  • pivot 기준으로 오른쪽 : pivot 보다 큰 요소
• pivot을 제외한 왼쪽 list와 오른쪽 list를 재 정렬한다.
  • 분할한 부분 리스트(왼쪽, 오른쪽) 에 대해 다시 pivot을 정한다.
  • 2개의 부분 리스트로 나누는 과정을 반복한다.
• 더 이상 분할이 불가능 할때까지 (배열의 크기가 1일 때까지) 반복한다.
• 구체적 용어 설명
  • 분할(Divide) : pivot을 기준으로 2개의 배열로 분할한다.
  • 정복(Conquer) :
    • 부분 배열을 정렬한다.
    • 순환 호출을 이용해서 분할 정복을 반복한다.
  • 결합(Combine) : 정렬된 부분 배열을 합친다.

---

STEP 1 - pivot 선정

• pivot 값 설정 (pivot값 설정 방식에 따라 수행시간의 차이가 난다.)
  • 맨 왼쪽 값
  • 가운데 값 (array size / 2)
  • 맨 오른쪽 값
• 효율적인 pivot 선택 하는 방법 (median of three)
  • 중간 크기의 숫자를 pivot으로 선정하는 것이 가장 효율적이다.
  • 세 값 (처음, 가운데, 끝) 중 중간 값을 pivot으로 선정한다.
  • 나머지는 일반 quick과 같다.
• 맨 왼쪽 값이나 오른쪽값을 pivot으로 선택할 경우
  • 부분리스트를 나눌때 pivot값을 제외하고 나눌 수 있다.
• 그러나 가운데에 위치한 값을 pivot으로 선택한 경우
  • 다양한 변수들로 인해 pivot값을 포함하고 나누게 된다.
  • (이 부분 조사에 있어 시간이 오래걸렸다. 혹시나 틀렸다면, 댓글로 저에게 올바른 지식을 알려주세요.)
• 이 포스트에서는 가운데 값을 pivot 으로 선정해 보려고 한다.
• 예시 array [5, 8, 10, 6, 1, 3]
  • 6(array size) / 2 = 3 -> pivot = 10

STEP 2

• 알아야 할 조건
  • left는 pivot < left 일 때까지 우측으로 이동
  • right는 pivot > right 일 때까지 좌측으로 이동
• 왼쪽(노랑)값이 pivot 값 보다 작은지 확인한다.
  • 작다면 왼쪽에서 오른쪽으로 이동하면서 이를 반복한다.
• 왼쪽(노랑)값이 pivot 값 보다 크다면 오른쪽 값(파랑) 을 본다.
  • 오른쪽(파랑)값이 pivot 값 보다 큰지 확인한다
  • 크다면 오른쪽에서 왼쪽으로 이동하면서 이를 반복한다.
• 오른쪽(파랑)값이 pivot보다 작다면
  • 왼쪽(노랑)값과 오른쪽(파랑)값을 SWAP한다.
• 왼쪽(노랑)과 오른쪽(파랑)이 만날때 까지 반복한다.
• 또는 오른쪽(파랑)이 왼쪽(노랑)을 교차해서 right> left 될 때 까지 반복한다.

아래 예시를 통해 이해를 해보자.

---

Quick Sort (퀵 정렬) 의 장 · 단점

장점 :

• 속도가 가장 빠르다.
• 같은 시간복잡도를 가지는 다른 정렬 알고리즘과 비교해도 가장 빠르다.
• 추가 메모리 공간을 필요로 하지 않는다.

단점 :

• 정렬된 리스트의 경우 분할방식으로 인해 오히려 수행시간이 더 오래걸린다.
• pivot을 무엇으로 선택하냐에 따라 시간복잡도가 다르다. 그래서 median of three 방식이 존재한다.

Quick Sort (퀵 정렬) 의 시간복잡도

pivot을 기준으로 부분리스트로 나눠진다. 절반으로 나눠지는 것이 보장되지 않기 때문에 best와 worst case 가 존재한다.

최선의 경우 (Best)

• 나누어지는 부분 리스트마다 절반씩 분할되는 경우
• O(nlog₂n)

평균 (Avg)

• O(nlog₂n)

최악의 경우 (Worst)

• 나누어지는 부분 리스트마다 1개와 그 나머지 리스트로 분할되는 경우
• 정렬된 리스트를 가지고 퀵 정렬을 실행할 때
• O(n^2)

---

Quick Sort (퀵 정렬) JAVA 구현

public class QuickSort {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.valueOf(br.readLine());
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.valueOf(br.readLine());
        }
        quickSort(arr, 0, n - 1);

        for (int i = 0; i < n; i++) {
            sb.append(arr[i] + "\n");
        }
        System.out.println(sb);

    }

    public static void quickSort(int[] arr, int left, int right) {
        int pivot = arr[(left + right) / 2];
        int l = left;
        int r = right;

        while (l <= r) {
            while (arr[l] < pivot)
                l++;

            while (arr[r] > pivot)
                r--;

            if (l <= r) {
                int temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
                l++;
                r--;
            }
        }

        if (left < l - 1)
            quickSort(arr, left, l - 1);

        if (l < right)
            quickSort(arr, l, right);
    }
}

백준 알고리즘 문제 2751번 - 수 정렬하기 2

윗 예시를 코드를 통해 똑같이 적용.

n = 6, array = [5, 8, 6, 10, 1, 3]