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}\)가 된다.