Quick 정렬, 그림으로 쉽게 이해하기

1. Quick 정렬은 무엇인가?

Pivot(중추)가 되는 값을 하나 선정해서 그 값보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 모은다. 이제 나눠진 두 그룹 내에서 다시 Pivot을 선정하고 이 과정을 반복한다. 값을 더 이상 쪼갤 수 없을 때까지 반복하면 모든 값이 정렬되어 있다.

2. 원리

병합정렬과 마찬가지로 분할 정복을 활용하는 또 다른 예시이다. 병합 정렬에서는 선 분할 후 정복 이었다면, quick 정렬은 선 정복, 후 분할 형식이라 생각하면 되겠다.

정복에는 마주보는 투 포인터가 활용된다. 어떻게 쓰이는지는 밑의 예시에서 자세히 설명하겠다.

 

• (1) Pivot 정하기 (정하는 방식은 때에 맞게 자유)
• (2) Pivot보다 큰 값은 오른쪽으로 몰기, 작거나 같은 값은 왼쪽으로 몰기 (정복 by 투 포인터)
• (3) 나눠진 두 그룹에 대해서 재귀를 활용해 (1),(2)번 다시 진행 - 더 이상 재귀할 수 없을 때까지 (분할 by 재귀)

 

 

(2)번을 좀 더 세세하게 설명하면,

L(왼쪽)포인터, R(오른쪽) 포인터가 있을 때,

 

• (2-1) L 포인터는 pivot보다 작은 값을 만나면 한 칸 전진, 그 외의 경우 그 위치에서 기다림.
• (2-2) R 포인터는 pivot보다 큰 값을 만나면 한 칸 전진, 그외의 그 위치에서 기다림.
• (2-3) 두 포인터 모두 기다림 상태라면 둘의 value를 자리 교체
• (2-4) 교체 후에는 둘 다 한 칸씩 전진!!
• (2-5) 이 행위를 두 포인터가 엇갈릴 때까지 반복

3. 예시

pivot 값을 index = 4인 6으로 정해보자. 중앙의 값으로 정해서 따로 값을 중앙에 위치시킬 필요는 없다.

이제 마주보는 투 포인터를 설정한다.

index = 0의 값은 1로 6보다 작다. 따라서 왼쪽 포인터는 한 칸 전진한다. 반면 오른쪽 포인터가 가르키는 index = 9의 값은 3으로 6보다 작다. 이때 오른쪽 포인터는 Switching 할 값을 만날 때까지 대기해야한다.

왼쪽 포인터가 가르키는 값이 7로 6보다 크다. 따라서 오른쪽 포인터의 3과 값을 switching 해준다.

이런 식으로 두 포인터가 만날 때까지 반복한다.

L 포인터가 가리키는 값은 pivot: 6과 크기가 동일한 값임으로 정지상태, R 포인터가 가리키는 값은 pivot보다 값이 작음으로 기다리는 상태. 서로 기다리는 상태라서 자리교체 (자리 교체 후에는 모두 한 칸 전진!)

두 포인터가 엇갈렸음으로 현 반복문 종료.
이후 분할은 START - R, L - END 두개로 나눠서 한다.

Pivot이 다음 정렬 그룹 안에 포함되어도 괜찮나요? 🤔

위의 예시를 보면 Pivot이 자신보다 큰 값들이 속하는 그룹에 들어가는 것을 볼 수 있다. 이처럼 PIVOT은 왼쪽 그룹에서는 제일 큰 값, 오른쪽 그룹에서는 제일 작은 값으로 다음 정렬에 참여하게 되므로 정렬에 포함되어도 딱히 문제가 되진 않는다.

만약 문제를 풀 때, PIVOT이 정렬에 포함됨에 따라 코드 가독성이 떨어진다고 생각한다면, PIVOT을 최좌단으로 뺴두는 방식을 활용하면 된다. 해당 방식은 다음과 같이 진행된다.

• (1) PIVOT은 선정 후, 항상 최좌단 값과 자리 교체함
• (2) 정렬은 똑같이 진행
• (3) 정렬이 끝난 후, R 포인터가 가르키는 값과 Pivot을 교체 (PIVOT을 정렬된 그룹의 가운데에 위치)
• (4) Pivot 제외하고, 각 그룹에서 재귀를 활용한 정렬 재 진행

해당 방식의 코드 또한 밑에 따로 적어두겠다.

4. 코드

(1) PIVOT 포함 정렬

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {

    static int [] arr = new int [] {1,7,5,4,6,9,8,10,2,3};
    static int [] tmp = new int [10];
    public static void main(String[] args) throws IOException {
        quick_sort(0, 9, 0);

        System.out.println(Arrays.toString(arr));
    }

    public static void quick_sort (int start, int end, int depth) {
        // 0. 기저 조건
        if(start >= end) return;
        // 1. 정복 by 투 포인터
        int pivot_index = start + (end - start)/2;
        int pivot = arr[pivot_index];


        int L = start;
        int R = end;

        while (L <= R){
            while (arr[L] < pivot){
                L++;
            }
            while (arr[R] > pivot){
                R--;
            }

            if(L <= R){ // == 처리 안하면 영원히 두 포인터가 엇갈리지 않는 경우의 수가 생김
                int tmp = arr[L];
                arr[L] = arr[R];
                arr[R] = tmp;
                L++;    R--;
            }
        }

        System.out.println("depth-" + depth  + ": " + Arrays.toString(arr) + " / [[ pivot: " + pivot + " start: "+ start + " end: " + end + "]]");

        // 2. 분할 by 재귀
        quick_sort(start, R, depth+1);
        quick_sort(L, end, depth+1);
    }
}

(2) PIVOT은 정렬에서 제외

  private static void quick_sort (int start, int end) {
       // 0. 기저 조건
        if(end - start == 1){
            swap(start, end);
        }
        if(start >= end) return;
        // 1. 본계산
        int pivot = start + (end - start)/2;
        int pivot_value = arr[pivot];
        swap(pivot, start);                 // pivot을 최좌단으로 몰아서 계산에 영향 안 주기
        int L = start+1; int R = end;
        while (L <= R) {
            while (L <= end && arr[L] < pivot_value) L++;    // 원래는 중간에 pivot이 있어서 L, R 포인터가 극단까지 안 가고 무조건 멈췄지만, 이젠 그런 브레이크가 존재하지 않기에, 범위를 벗어나지 않도록 조치해줘야 함.
            while (R >= 0 && arr[R] > pivot_value) R--;
            if(L <= R) {
                swap(L,R);
                L++; R--;
            }
        }
        swap(start, R);
        // pivot 제외 분할 및 재정복
        quick_sort(start, R-1);
        quick_sort(L, end);
    }

    private static void swap(int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

시간복잡도는 O(\(N^{2}\))이다.
매번 pivot을 최대값 혹은 최소값으로 선정한다고 가정해보면, 한 번의 재귀에서 딱 한 개만 정렬이 가능하다. 재귀 한 번 당 배열 전체를 순회 + 하나만 정렬 됨으로 \(N^{2}\)가 된다.