알고리즘] 퀵 정렬(Quick Sort)에 대한 이해

소개

정렬 알고리즘 중 대표적인 알고리즘인 퀵 정렬을 소개하고자 한다.

 

퀵 정렬을 소개하기에 앞서, 대표적인 알고리즘들의 시간/공간 복잡도 표를 확인하면 다음과 같다.

	평균	최악	메모리
버블 정렬	n^2	n^2	1
선택 정렬	n^2	n^2	1
삽입 정렬	n^2	n^2	1
퀵 정렬	n log n	n^2	n log n
병합 정렬	n log n	n log n	n
힙 정렬	n log n	n log n	1

퀵 정렬은 이름 그대로 '빠른 알고리즘'이라는 의미인데, 실제로 위 알고리즘들 중에서는 일반적으로 가장 빠른 알고리즘이라고 한다.

여기서 약간 의아할 수 있는 부분이 '병합, 힙 정렬이 최악의 경우에 퀵 정렬보다 시간 복잡도가 높은데, 어떻게 가장 빠른 알고리즘이지?'라는 생각이 들 수 있는데, 그 이유는 다음과 같다.

알고리즘을 공부를 여기까지 하는 분들이라면 모두 빅오 표기법을 알고 있을 거라고 생각한다.

그리고 빅오 표기법을 배웠을 당시 '최고차항을 제외한 나머지는 무시한다'라는 개념을 기억하고 있을 것이다.

따라서 같은 O(N)이어도 '300 * N'일 수도 있고, '100 * N'일 수도 있다는 이야기다. 

퀵 정렬은 병합 정렬과 힙 정렬보다 평균적으로 n log n에 곱해지는 수가 적어 결과적으로 평균적인 연산, 즉, 실제 연산 속도가 빠르다고 알려져 있기 때문에 병합 정렬과 퀵 정렬보다 빠르다고 알려져 있는 것이다.

 

 

사전 지식

1. 버블/선택/삽입 정렬에 대한 개념을 이해하고 있으며, 구현 가능하다.

2. 재귀 함수에 대한 이해가 어느 정도 있다.

 

퀵 정렬을 구현하고자 한다면, 위 두 가지 내용은 이해하고 있어야 한다고 생각하며, 로그를 배우기 전에 함수 등의 지식을 배우듯이, 이보다 쉬운 개념인 다른 정렬을 모른다면 다른 정렬을 먼저 공부해야 하고, 아직 재귀 함수를 전혀 모른다면 피보나치 함수 등 기초적인 재귀 함수에 대한 이해를 하고 퀵 정렬을 이해하는 것이 바람직할 것 같다.

 

 

퀵 정렬의 동작

1. 피벗(pivot)의 위치 탐색 및 정렬

(오름차순 기준으로 설명 진행)

퀵 정렬에서 중요한 두 가지 변수가 존재한다. 하나는 pivot 변수이며, 하나는 position 변수이다.

피벗부터 설명을 하자면, 정렬을 하고자 할 때 하나의 기준 위치이자 값이라고 생각하면 되는데, 이 기준 위치는 퀵 정렬을 구현하고자 하는 사람마다 다를 수 있으며, 나 같은 경우에는 가장 우측에 존재하는 값을 피벗 값으로 둔다.

그리고, 피벗 값의 반대에서 시작하는 position 변수가 존재한다. 이 position 변수는 가장 좌측에서 시작한다.

퀵 정렬의 핵심은 피벗 값을 제 위치로 찾아가도록 하는데에 있다. 예를 들어, 지금 피벗 값은 12이므로 배열 내에서 12가 존재해야 하는 값을 찾는 것이 핵심이다.

피벗이 본인의 값을 찾아가기 위한 연산은 다음과 같다.

1. 배열을 반복문을 돌린다.

2. 현재 조회하는 값이 pivot 값보다 작다면, 현재 position 변수 인덱스에 존재하는 값과 교환 후, position +1을 한다.

3. 반복문이 종료된 후 최종 position 변수 인덱스의 값과 pivot 인덱스의 값을 교환하고, 그 값은 pivot의 최종 위치이다.

 

내용만 보고는 이해가 되지 않을 수 있다. 먼저 동작을 살펴보고 결과를 보면서 이해하는 것이 훨씬 좋다고 생각하기 때문에, 바로 이해하려고 하지 말고 그림부터 함께 살펴보자.

 

반복문에 사용되는 변수를 i라고 했을 때, 맨 처음에는 위 그림처럼 될 것이다.

위 내용에 '현재 조회하는 값이 pivot보다 작은가?'를 적용했을 때 12 < 15이니 적용되지 않고, 다음으로 넘어간다

현재 값을 기준으로 다시 조건을 살필 때 '현재 조회하는 값이 pivot보다 작은가?'를 만족한다. 5 < 12이니 말이다.

그렇다면, '현재 position 변수 인덱스에 존재하는 값과 교환 후, position + 1'을 진행한다. 그렇게 되면 다음과 같이 된다.

그다음 다시 반복문에 따라 i를 증가시켜보자.

i가 1 증가했으며, 다시 '현재 조회하는 값이 pivot보다 작은가?' 조건에 부합하는지 확인할 때, 이번에도 조건을 만족한다.

그다음 역시 '현재 position 변수 인덱스에 존재하는 값과 교환 후, position + 1'을 진행한다. 그렇게 되면 다음과 같이 된다.

이와 같은 개념으로 i를 pivot 전까지 돌렸을 때 다음과 같이 동작할 것이다.

그러면 반복문이 종료되었으니, 전에 말한 '반복문이 종료된 후 최종 position 변수 인덱스의 값과 pivot 인덱스의 값을 교환하고, 그 값은 pivot의 최종 위치이다..'는 개념을 적용시킨다.

'pivot의 최종 위치'라는 말의 뜻은 '해당 배열을 정렬했을 때 최종적으로 있어야 할 위치'라는 뜻이며, 실제로 지금 배열에 존재하는 값을 나란히 보았을 때 '5, 7, 9, 11, 12, 15'가 되며, 이는 우리가 찾은 위치와 동일하다.

앞에서 position을 0부터 시작해서 pivot보다 작은 값이 존재하면 값을 바꾸고 position +1을 하던 이유가 바로 이거다. position은 최종적으로 현재 피벗 값의 위치를 찾기 위한 변수이며, 위치를 찾기 위한 방법으로 0부터 시작하여 끝-1까지 그보다 작은 수가 몇 개 있고, 그 몇 개만큼 position값을 증가시키는 거다. 이런 방식으로 첫 피벗 값인 12는 제 위치를 찾아갔다.

이를 코드로 표현하면 다음과 같다.

     public static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int position = left;

        for (int i = left; i < right; i++) {
            if (pivot > arr[i]) {
                swap(arr, position, i);
                position++;
            }
        }

        int pivotPos = position;
        swap(arr, pivotPos, right);

        return pivotPos;
    }

    public static void swap(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

 

2. 반복

그러면 나머지 값에 대한 정렬을 어떻게 진행하면 되는가?

답은 간단하다. '앞서 했던 것들을 마지막 피벗 값의 위치를 기준으로 왼쪽, 오른쪽 배열에 적용시킨다.'이다.

그리고 이를 적용시키는 방법이 바로 재귀 함수다.

그 방법은 간단하다. 위 '피벗의 위치 탐색 및 정렬'을 하는 partition 함수에서 피벗의 최종 포지션 값을 pivotPos라는 변수로 받고, 그 값을 기준으로 왼쪽(-1), 오른쪽(+1)에 재귀 함수를 반복한다.'이다.

그 이후에 다시 안에서 어떻게 도는지는 깊게 생각할 필요 없다. 올바른 말은 아니겠지만, 재귀 함수는 어느 정도 '막연한 믿음'이 있어야 한다. 앞서 partition 함수를 잘 짰고, 잘 돌았으니, 재귀 함수를 돌리면 나머지도 당연히 잘 돌겠지. 하는 생각이 있어야 한다. 이에 대한 검증은 맨 처음 재귀 함수를 배울 때 피보나치나 하노이의 탑 등에서 검증을 하면 되는 거고, 자신이 앞서 짠 코드에 확신을 갖고 재귀 함수를 사용하면 된다.

재귀 함수를 코드로 표현하자면 다음과 같다.

public static void quickSortRecursive(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

        int pivotPos = partition(arr, left, right);

        quickSortRecursive(arr, left, pivotPos - 1);
        quickSortRecursive(arr, pivotPos + 1, right);
 }

 

 

코드로 표현했을 때 정말 간결하지 않은가?

내용이 이해가 잘 안 가면 '이게 된다고?' 싶을 수 있지만, 값을 못 찾았을 때의 탈출 조건만 걸고 나머지는 앞서 말한 것과 같이 '피벗 값의 최종 위치를 받고, 왼쪽 오른쪽을 돌린다'가 끝이다.

한 번에 이해하지 못했다고 낙담하지 말고, 차근차근 다시 한번 살펴보기를 바란다.

 

 

최종 코드

public class Sort {
    public static void quickSort(int[] arr) {
        quickSortRecursive(arr, 0, arr.length - 1);
    }

    public static void quickSortRecursive(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

        int pivotPos = partition(arr, left, right);

        quickSortRecursive(arr, left, pivotPos - 1);
        quickSortRecursive(arr, pivotPos + 1, right);
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int position = left;

        for (int i = left; i < right; i++) {
            if (pivot > arr[i]) {
                swap(arr, position, i);
                position++;
            }
        }

        int pivotPos = position;
        swap(arr, pivotPos, right);

        return pivotPos;
    }

    public static void swap(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {15, 5, 9, 11, 7, 12};

        quickSort(arr);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

 

시간 복잡도

1. 피벗의 최종 position 탐색 -> n -> O(N)

2. 첫 피벗 값을 기준으로 좌우측에 재귀 함수 실행 -> 2 * log n -> O(log N)

=> O(N log N)

 

 

마무리

퀵 정렬은 알고리즘을 공부하면서 반드시 익혀야 하는 정렬 중에서도 가장 중요한 개념이며,

기술 면접에서 알고리즘을 묻는다면, 높은 확률로 퀵 정렬에 대한 질문을 할 것이다.

 

피벗 값을 교환하며 정렬하는 독특한 방식과 재귀 함수 때문에 보자마자 학습을 완료하기는 어려움이 있겠지만,

시간을 두고 천천히 복습하는데도 익히지 못할 개념이라고까지는 생각하지 않는다.

 

따라서, 이 글에서 다룬 퀵 정렬의 동작을 보고 익히며 직접 코드로 구현해 보고, 시간이 지나면 까먹으니 며칠이 지나 다시 코드로 작성하여 퀵 정렬을 익혔으면 하는 바람에 글을 작성했으니, 이 글이 도움이 되기를 바란다.