정렬 - 퀵 정렬

주빈·2022년 2월 25일

algorithm

목록 보기

10/16

오늘은 가장 빠른 정렬 알고리즘 중의 하나로 알려진 퀵 정렬을 알아보자.

📘 퀵 정렬

퀵 정렬(quick sort)은 이 알고리즘의 정렬 속도가 매우 빠른데서 착안해 찰스 앤터니 리처드 호어(C. A. R. Hoare)가 직접 붙인 이름이다.
하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.

✏ 퀵 정렬 원리

퀵 정렬의 원리를 알아보자.

위의 배열에서 두 그룹으로 먼저 나누어 보자.

피벗으로 리스트 안에 있는 한 요소를 선택한다. 우리는 5를 선택해보자.
이렇게 고른 원소를 피벗(pivot) 이라고 한다.

피벗을 pivot, 왼쪽 끝 요소의 인덱스를 pl, 오른쪽 끝 요소의 인덱스를 pr로 해보자.
그룹으로 나누려면 피벗 이하의 요소는 배열 왼쪽으로, 이상의 요소를 배열 오른쪽으로 옮겨야 한다.

다음과 같은 작업을 수행해야 하는 것이다.

1. a[pl] >= pivot이 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔한다.
2. a[pr] <= pivot이 성립하는 요소를 찾을 때까지 pr을 왼쪽으로 스캔한다.

위 과정을 거치면 pl이 위치하는 지점은 피벗 이상의 값이 있는 요소의 지점(5)에 있고, pr은 피벗 이하의 값이 있는 요소(6)에 있게 되며 이 두 수가 서로 교환이 된다.
교환 후에 다시 스캔을 계속하면 두 커서(pl, pr)가 교차하게 된다.

pl과 pr이 교차하면 그룹을 나누는 과정이 끝나고 배열을 아래처럼 두 그룹으로 나누어진다.

피벗 이하의 그룹 : a[0],...,a[pl - 1]
피벗 이상의 그룹 : a[pr + 1],...,a[n - 1]

그룹을 나누는 작업이 끝난 다음 pl > pr + 1인 경우에는 다음과 같은 그룹이 생길 수 있다.

피벗과 일치하는 값을 가지는 그룹 : a[pr + 1],...,a[pl - 1]

✏ 퀵 정렬 코드

주요 메서드를 보며 알아보자.

// 배열 요소 a[idx1]과 a[idx2]의 값을 바꾸는 swap 메서드
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    // 배열을 나누는 partition 메서드
    static void partition(int[] a, int n) {
        int pl = 0;         // 왼쪽 커서
        int pr = n - 1;     // 오른쪽 커서
        int pivot = a[n / 2]; // 피벗(가운데 위치의 값)

        do {
            while (a[pl] < pivot) pl++;
            while (a[pr] > pivot) pr--;
            if (pl <= pr)
                swap(a, pl++, pr--);
        } while (pl <= pr);

        System.out.println("피벗의 값은 " + pivot);

        System.out.println("피벗 이하의 그룹");
        for (int i = 0; i < pl - 1; i++)        // a[0] ~ a[pl - 1]
            System.out.println(a[i] + " ");
        System.out.println();

        if (pl > pr + 1) {
            System.out.println("피벗과 일치하는 그룹");
            for (int i = pr + 1; i <= pl - 1; i++)  // a[pr + 1] ~ a[pl - 1]
                System.out.println(a[i] + " ");
            System.out.println();
        }

        System.out.println("피벗 이상의 그룹");
        for (int i = pr + 1; i < n; i++)        // a[pr + 1] ~ a[n - 1]
            System.out.println(a[i] + " ");
        System.out.println();
    }

앞에서는 배열을 피벗을 기준으로 나누기만 했다. 이 방법을 좀 더 발전시키면 퀵 정렬 알고리즘이 된다.

퀵 정렬의 과정을 그림으로 나타내면 다음과 같다.

그림처럼 그룹을 계속해서 나누지만 요소의 개수가 1개인 그룹은 더 이상 그룹을 나눌 필요가 없는 것처럼 보인다.
이렇게 그룹을 나누는 방법은

1. pr이 a[0]보다 오른쪽에 있으면(lefr < pr) 왼쪽 그룹을 나눈다.
2. pl이 a[8]보다 왼쪽에 있으면(pl < right) 오른쪽 그룹을 나눈다.

==> 위의 두개는 모두 그룹의 개수가 1개인 경우에는 성립하지 않는다. 
	다시 말해 요소 개수가 2개 이상인 그룹만이 나누기 위해 필요한 조건이다.

퀵 정렬은 8퀸 문제와 마찬가지로 분할 정복 알고리즘이므로 재귀 호출을 이용하여 구현할 수 있다.
아래의 코드는 quickSort메서드를 구현해보았다.

	// 퀵 정렬 메서드
    static void quickSort(int[] a, int left, int right) {
        int pl = left;      // 왼쪽 커서
        int pr = right;     // 오른쪽 커서
        int pivot = a[(pl + pr) / 2];   // 피벗

        do {
            while (a[pl] < pivot) pl++;
            while (a[pr] > pivot) pr--;
            if (pl <= pr)
               swap(a, pl++, pr--);
        } while (pl <= pr);
            
        if (left < pr) quickSort(a, left, pr);
        if (pl < right) quickSort(a, pl, right);
    }