Quick Sort 구현

 quick sort:

 정렬 속도가 아주 빠르다는 데서 착안해 붙여진 직관적인 이름이다.

퀵정렬은 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하여 모든 그룹이 1개의 요소가 될때까지 반복한다.
그룹을 나누는 기준을 피벗(pivot) 이라고 한다.

 

배열을 두 그룹으로 나누기

 피벗 이하의 요소를 배열 왼쪽으로, 피벗 이상의 요소를 배열 오른쪽으로 옮겨야 한다. 아래 배열을 통해 과정을 살펴보자.

int[] arr = [5, 7, 1, 4, 6, 2, 3, 9, 8]
//           pl          x           pr

가운데 인덱스를 피벗 x, 왼쪽 끝 요소를 pl, 오른쪽 끝 요소를 pr 이라 했을 때

1. arr[pl] >= x 가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔한다. (pl++;)

2. arr[pr] <= x 가 성립하는 요소를 찾을 때까지 pr을 왼쪽으로 스캔한다. (pr--;)

3. pl 커서가 값이 7인 인덱스에 멈추고 pr 커서가 값이 3인 인덱스에 멈춘 후 둘을 교환한다.

4. pl과 pr이 교차할때까지 3번 과정은 반복된다.

5. 교차하면 그룹을 나누는 과정이 끝나고 배열은 두 그룹으로 나뉘게 된다.

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

위 과정중에서는 피벗과 같은 값을 갖는 그룹이 생성될 수 있다. 동일한 요소로 발견되도 교환을 시도한다. 동일 요소에 대한 예외처리를 하는것은 오히려 비용을 증가시킨다. 인덱스를 옮겨가며 요소들을 교환할 때 조건을 판별해야 하는데, 이 조건 판별하는 로직에 따른 비용이 더 크다.

 

요소를 교환하는 Method는 아래와 같다.

static void swap(int[] a, int idx1, int idx2) {
    int t = a[idx1];
    a[idx1] = a[idx2];
    a[idx2] = t;
}

 

배열은 아래와 같은 방법으로 나눌 수 있다.

static void partition(int[] a, int n) {
    int pl = 0;        // 왼쪽 커서
    int pr = n - 1;    // 오른쪽 커서
    int x = a[n / 2];  // 피벗 커서
    
    do {
        while (a[pl] < x) pl++;  // 피벗 기준 왼쪽 그룹에서 피벗의 값보다 큰 요소를 찾는다
        while (a[pr] > x) pr--;  // 피벗 기준 오른쪽 그룹에서 피벗의 값보다 작은 요소를 찾는다
        if (pl <= pr)            
            swap(a, pl++, pr--); // 두 요소를 교환, 교환 이후에 커서는 한칸씩 옮겨져있다
    } while (pl <= pr);          // pl 커서가 pr 커서보다 값이 커지면 교환을 마친다
}

위 두 메서드를 모든 그룹의 요소가 1개가 될때까지 반복하는것이 quick sort의 기본 동작 방식이다.

 

이를 재귀적으로 구현하는 방법과 stack을 이용하여 구현하는 방법으로 보겠다.

 

재귀 방법으로 quick sort 구현

public class QuickSort {
	static void swap(int[] a, int idx1, int idx2) {} // 생략, 위 설명에 나와있는 swap 메서드와 동일

    static void quickSort(int[] a, int left, int right) {
        int pl = left;
        int pr = right;
        int x = a[(pl + pr) / 2];

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

        // 위 do while문을 통해 정렬된 배열을 기준으로
        // 왼쪽 그룹과 오른쪽 그룹을 나누어 재귀함수를 호출한다.
        if (left < pr) quickSort(a, left, pr); // 왼쪽 그룹에 대한 정렬 처리
        if (pl < right) quickSort(a, pl, right); // 오른쪽 그룹에 대한 정렬 처리
    }
}

재귀로 구현하면 코드의 양이 확연하게 적어진다.

int[] a = {5, 8, 4, 2, 6, 1, 3, 9, 7};

위와 같은 배열을 정렬하게 된다면 그룹을 아래와 같이 나누게 된다.

 

재귀를 사용하지 않고 Stack을 사용한 방법이다.

public class QuickSort2 {
    public void swap(int[] a, int idx1, int idx2) {} // 생략

    public int[] quickSort(int[] a, int left, int right) {
        // 스택 생성
        IntStack lstack = new IntStack(right - left + 1);
        IntStack rstack = new IntStack(right - left + 1);

        lstack.push(left);
        rstack.push(right);

        while (!lstack.isEmpty()) {
            int pl = left = lstack.pop();
            int pr = right = rstack.pop();
            int x = a[(left + right) / 2];

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

            // 재귀를 사용했던 부분에 대해 stack 을 이용해 커서값을 저장한다.
            // 왼쪽 그룹이 될 부분에 대한 처리다.
            if (left < pr) {
                lstack.push(pr);
                rstack.push(right);
            }

            // 오른쪽 그룹에 대한 처리
            if (right > pl) {
                lstack.push(left);
                rstack.push(pl);
            }
        }

        return a;
    }
}

 

1. 퀵정렬은 피봇을 중심으로 왼쪽 그룹과 오른쪽 그룹을 나눈다.
2. 나뉘어진 그룹에서 정렬(swap)을 진행한다.
3. 정렬 이후에는 커서의 값을 재귀함수에 인자로 넣거나 스택에 저장한다.
4. 위 과정을 반복하여 처리한다.