퀵 정렬(Quick Sort)에 대해 알아보자

이번 포스팅에서는 퀵 정렬에 대해 자세히 알아보자. 퀵 정렬은 실제로 많이 사용하는 정렬 방법이다. 평균 시간복잡도는 O(nlogn)을 가지며 최악의 경우 O(n^2)을 가진다. 실제 알고리즘 문제에서도 자주 나오고 퀵 정렬 자체가 나오기보다는 변형된 정렬을 사용하는 문제가 나온다. 자바의 기본 내장함수도 정렬 방식으로는 퀵 정렬을 사용할 정도로 많이 사용되는 정렬 방법이다.

 

퀵 정렬

퀵 정렬은 숫자들 중에서 기준값을 하나 정해(이 값을 피벗(pivot)이라고 한다) 이 기준값을 이용해 나머지 수를 정렬한 후 이 행동을 반복하는 형태이다. 그림을 보자.

형광팬이 칠해진 곳은 정렬이 완료된 곳이다.

가장 먼저 피벗을 정해야 한다. 보통은 맨 앞, 맨 뒤를 피벗으로 정한다. 그 이유는 그게 코딩하기 가장 쉬우니까... 그리고 피벗으로 선택한 숫자를 제외한 나머지 숫자들의 처음과 끝에서부터 탐색을 시작한다. 이때 투 포인터 방식을 이용한다. 앞에서 출발할 때는 피벗보다 작은 숫자를 만나면 통과하고 피벗과 같거나 큰 숫자를 만나면 멈춘다. 뒤쪽에서 출발하면 피벗보다 큰 수여야만 통과하고 같거나 작은 숫자이면 멈춘다. 그리고 두 포인터가 전부 멈추면 두 개의 수를 swap 한다. 그러면 뒤쪽에 있던 피벗보다 작은 숫자는 앞으로 이동하고 앞쪽에 있던 피벗보다 큰 숫자는 뒤쪽으로 이동하게 된다. 그림에서 보면 처음에 피벗이 5이고 3과 7이 포인터에 걸려 swap 된 것을 볼 수 있다. 이것을 양 끝단에서 출발한 두 포인터가 만날 때까지 반복한다. 그리고 더 이상 swap 할 숫자가 없으면 피벗을 알맞은 숫자의 위치와 바꾼다. 그림에서는 5가 포인터가 만난 지점인 2와 8중에서 8과 swap 된 것을 볼 수 있다. 2와 swap 하려면 피벗을 맨 뒤가 아니라 맨 앞으로 설정해야 한다. 그다음 배열을 보면 5를 중심으로 앞은 5보다 작은 수, 뒤는 5보다 큰 수인 것을 볼 수 있다. 이제 5와 앞과 뒤쪽 배열을 지금과 같이 피벗을 설정하여 정렬한다. 이렇게 점점 배열을 쪼개면서 정렬을 하다 보면 원소가 하나 또는 2개가 남는 순간이 온다. 그러면 피벗 설정 없이 정렬을 완료하고 퀵 정렬이 종료된다.

이 과정을 보면 퀵 정렬에서 가장 중요한 것은 피벗을 설정하는 것이라는 것을 볼 수 있다. 만약 피벗으로 최대값, 또는 최솟값이 계속 설정된다면 선택 정렬과 다를 바가 없어지는 결과가 나오고(모든 숫자가 피벗보다 작거나 클 것이므로 배열의 끝쪽에 피벗이 계속 위치할 것이다) 시간복잡도가 O(n^2)이 된다. 이런 현상을 방지하기 위해 사용할 수 있는 방법들이 몇 가지 있다. 먼저 간단한 방법으로는 피벗을 양 끝단이 아니라 중간 어디선가 추출하는 방법이다. 물론 이것을 예상하고 예제를 만들어둔다면 최악이겠지만 그럴 확률은 높지 않다. 퀵 정렬 문제에는 맨 앞과 맨 끝을 피벗으로 하면 시간초과되도록 하는 테스트케이스가 있는 것이 분명하다. 만약 최악의 경우를 반드시 피하고 싶다면 3개의 숫자를 선택해 비교 후 중간값을 피벗으로 하면 된다. 이러면 피벗보다 작거나 큰 수가 무조건 1개 이상 존재하게 된다.

다음 코드는 3개의 숫자를 비교해 피벗을 설정하는 퀵 소트를 직접 구현해 본 것이다. 구현하다가 엄청나게 많은 인덱스 오류와 마주했지만 결국 성공하였다...백준 문제는 2750번을 이용하였다.

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[] num = new int[N];
        for(int i=0;i<N;i++){
            num[i] = Integer.parseInt(br.readLine());
        }
        if(N==1){
            bw.write(num[0]+"");
            bw.flush();
            bw.close();
            System.exit(0);
        }
        quickSort(num, 0, N-1);
        for(int i=0;i<N;i++){
            bw.write(num[i]+"\n");
        }
        bw.flush();
        bw.close();
    }
    static void quickSort(int[] num, int start, int end){
        if(end-start==1){
            if(num[start]>num[end]) swap(num, start, end);
            return;
        }
        int pivotIndex = middle(num, start, end);
        int pivot = num[pivotIndex];
        swap(num, pivotIndex, start);
        int i = start + 1;
        int j = end;
        while(i<j){
            while(num[i]<pivot) i++;
            while(num[j]>pivot) j--;
            if(i<j) {
                swap(num, i, j);
            }
        }
        swap(num, start, j);
        if(start!=j-1) quickSort(num, start, j-1);
        if(j+1!=end)quickSort(num, j+1, end);
    }
    static void swap(int[] num, int a, int b){
        int c = num[a];
        num[a] = num[b];
        num[b] = c;
    }
    static int middle(int[] num, int start, int end){
        int a = num[start];
        int b = num[start+1];
        int c = num[end];
        if(a>=b){
            if(c>=a) return start;
            else if(c>=b) return end;
            else return start+1;
        }else {
            if(c>=b) return start+1;
            else if(c>=a) return end;
            else return start;
        }
    }
}

배열 자체를 static으로 선언하지 않고 매개변수로 주었는데 딱히 특별한 의미는 없었다. 크게 퀵 정렬 함수, swap함수, 3개의 숫자 중 중간값을 구해주는 middle함수로 구성하였다. middle함수가 전체가짓수를 다 해봐야 해서 은근히 까다로웠다. 지금은 앞의 2개와 맨 끝의 한 개를 비교하는데 중간정도의 값을 비교하는 것도 좋을 것 같다.

 

퀵 정렬은 쓰임새가 다양하므로 꼭 직접 코딩을 해 보도록 하자. 아마 처음 코딩했다면 투 포인터를 다루는 부분에서 혼동이 올 수도 있는데(대표적으로 이상인가 초과인가 하는 등호의 유무) 그럴 때는 직접 숫자를 넣어보며 여러 케이스들에서 내 알고리즘이 어떻게 동작하는지 살펴보자. 이렇게 틀려보고 직접 고쳐보는 것이 더 오래 기억에 남는다.

다음 포스팅에서는 퀵 정렬의 변형인 퀵 선택 정렬에 대해서 알아보겠다.