[정렬 연습] 퀵 정렬의 원리 및 구현

Algorithm/Basic

[정렬 연습] 퀵 정렬의 원리 및 구현 - Java

ikjo 2022. 9. 10. 01:13

퀵 정렬이란?

퀵 정렬은 주어진 데이터 상 특정 값(피벗)을 기준으로 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 옮겨 2개의 파티션(Partition)으로 분할(Divide)해 나가는 방식으로 정렬한다.

퀵 정렬에 사용되는 기법을 분할 정복 알고리즘(Divide and conquer algorithm)이라고 하는데, 이는 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 분할 정복 알고리즘은 일반적으로 재귀 함수(Recursive function)를 통해 자연스럽게 구현된다.

퀵 정렬은 주어진 데이터 상 최초 피벗을 몇 번째 데이터로 정하는지에 따라 그리고 데이터 상태에 따라 다른 성능을 보일 수 있는데, 대표적으로 배열의 첫 번째 데이터를 피벗으로 정하는 호어 분할 방식이 있다.

호어 분할 방식

그림으로 호어 분할 방식의 퀵 정렬 이해하기

아래와 같이 최초 정렬되지 않은 크기 10의 정수형 배열이 있다고 가정했을 때, 호어 분할 방식의 퀵 정렬을 통해 오름차순으로 정렬해보자.

최초 배열 첫 번째 데이터인 7을 피벗으로 삼아, 왼쪽부터 피벗 보다 큰 데이터를 찾고, 오른쪽부터 피벗 보다 작은 데이터를 찾는다. 이때 피벗 보다 큰 데이터의 인덱스(이하 'left')가 피벗 보다 작은 데이터의 인덱스(이하 'right') 보다 크지 않다면(엇갈리지 않다면) 그대로 swap을 해준다.

이렇게 피벗을 기준으로 swap을 해주다보면 left가 right 보다 커지는 순간이 발생한다. 이때 right의 데이터 값과 피벗을 swap 해주는데, 이미 피벗을 기준으로 왼쪽에 작은 값들을, 오른쪽에 큰 값들을 위치시켜놨으므로, 피벗의 새로운 위치(right)는 정렬이 되어있다고 생각할 수 있다.

이제 피벗의 새로운 위치를 기준으로 반으로 나누어 앞선 작업을 반복해주도록 한다.

이러한 방식으로 영역을 반으로 분할해나갈 때 해당 영역의 크기가 1인 경우에는 해당 영역은 정렬이 된 것으로 보고 작업을 멈춘다.

자바로 호어 분할 방식의 퀵 정렬 구현하기

앞선 원리를 적용해 호어 분할 방식의 퀵 정렬을 자바로 구현해보면 다음과 같다.

public class HoarePartitionQuickSort {

    public static void quickSort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    private static void quickSort(int[] array, int start, int end) {
        if (start >= end) { // 영역의 크기가 1 이하라면
            return;
        }

        int pivot = start; // 첫 번째 데이터를 피벗으로 사용!
        int left = start + 1;
        int right = end;

        while (left <= right) { // left랑 right가 엇갈리면 반복문 탈출!
            while (left <= end && array[left] <= array[pivot]) { // 피벗 보다 큰 거 선택!
                left++;
            }

            while (right > start && array[right] >= array[pivot]) { // 피벗 보다 작은 거 선택!
                right--;
            }

            if (left > right) { // left랑 right가 엇갈리면 피벗이랑 작은 거랑 swap!
                swap(array, pivot, right);
            } else { // 피벗 보다 큰 거(left)랑 작은 거(right)랑 swap!
                swap(array, left, right);
            }
        }

        quickSort(array, start, right - 1); // 피벗의 새로운 위치 기준 왼쪽 영역
        quickSort(array, right + 1, end); // 피벗의 새로운 위치 기준 오른쪽 영역
    }

    private static void swap(int[] array, int i, int minIndex) {
        int temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
}

호어 분할 방식의 퀵 정렬 성능

호어 분할 방식의 퀵 정렬(이하 '퀵 정렬')은 주어진 데이터의 크기가 N이라고 할 때, 평균 시간 복잡도는 O(N * log N)이다.

앞서 그림으로 살펴봤듯이 퀵 정렬은 N개의 주어진 데이터에서 크기가 1이 될 때까지 영역(Partition)을 나누므로 총 N번 나누게 된다. 또한 특정 영역을 반으로 나눌 때 해당 영역의 크기가 '평균적으로' 절반씩 나뉘게 되므로 검색해야하는 데이터가 마치 이진 검색처럼 절반으로 줄어든다.

이처럼 데이터를 반으로 나누는 작업에 대한 시간 복잡도는 N 그리고 각 영역별로 검색하는 작업에 대한 평균적인 시간 복잡도는 log N으로서 직관적으로 평균 시간 복잡도는 O(N * log N)이라고 할 수 있다.

이를 수학적으로 계산하면 다음과 같은 수식으로 평균 시간 복잡도를 구할 수 있다고 한다.

하지만 특정 영역을 반으로 나눌 때 나뉘는 영역의 크가 균형있게 절반씩 나뉘면 다행이겠지만, 불균형하게 나뉠 수도 있다. 대표적으로 기존 데이터가 이미 정렬되어 있는 경우라면, 피벗을 제외한 나머지 데이터가 그대로 다른 영역으로 분할되므로, 최초 N개의 데이터에서 N - 1개, N - 2개, ... 식으로 나뉘게 되는 것이다. 이는 결국 이전에 다루었던 버블 정렬, 선택 정렬과 다를 바가 없으므로, 최악의 경우 시간 복잡도는 O(N^2)이다.

성능 비교를 위해 다음과 같이 3만개의 무작위 정수형 배열로 버블 정렬, 선택 정렬, 삽입 정렬, 호어 분할 방식의 퀵 정렬의 실행 시간을 측정해보았다.

        int[] array2 = new int[30000];
        Random random = new Random(30000);
        for (int i = 0; i < 30000; i++) {
            array2[i] = random.nextInt(1000);
        }

실행 결과 시간 복잡도가 O(N^2)인 버블 정렬, 선택 정렬, 삽입 정렬 대비 월등히 빠른 속도로 정렬이 처리되었다.

이번에는 퀵 정렬의 최악의 경우 성능을 알아보기 위해 다음과 같이 16500개의 정렬된 정수형 배열로 버블 정렬, 선택 정렬, 삽입 정렬, 호어 분할 방식의 퀵 정렬의 실행 시간을 측정해보았다.

        int[] array1 = new int[16500];
        for (int i = 0; i < 16500; i++) {
            array1[i] = i;
        }

실행 결과 퀵 정렬이라는 이름이 무색하게 버블 정렬 보다도 느린 성능을 나타냈다. 이는 검색하고 swap 해야하는 비용은 버블 정렬과 비슷하지만, 퀵 정렬이 분할, 재귀 호출 등 추가적인 비용이 더 발생한데 차이가 있는 것으로 추정된다. 그리고 이전에 다루었던 삽입 정렬은 예상대로 정렬된 데이터를 처리하는데 있어 강점을 보였다.

기존 호어 분할 방식 개선

앞서 살펴봤듯이 기존의 호어 분할 방식의 퀵 정렬은 기존 데이터가 정렬된 상태에서 불리하게 동작하는 문제가 있었다. 이는 영역이 나뉘어질 때 균등하게 나뉘어지지 못하고 한 쪽으로 데이터가 쏠리는데 원인이 있다.

기존에는 배열 상 첫 번째 데이터를 피벗으로 정했었는데, 이로 인해 배열이 정렬되어 있었던 경우에는 항상 불균형하게 영역들이 분할되곤 했다. 그렇다면 배열의 중간에 있는 값을 피벗으로 정해보면 어떨까?

그림으로 개선된 호어 분할 방식의 퀵 정렬 이해하기

앞서 예시에서 들었던 배열과 동일한 최초 정렬되지 않은 크기 10의 정수형 배열이 있다고 가정했을 때, 개선된 호어 분할 방식의 퀵 정렬을 통해 오름차순으로 정렬해보자.

최초 배열 상 인덱스를 기준으로 중간((0 + 9) / 2 = 4)에 있는 데이터 11을 피벗으로 삼아, 마찬가지로 왼쪽부터 피벗 보다 큰 데이터를 찾고, 오른쪽부터 피벗 보다 작은 데이터를 찾는다. 이때 피벗 보다 큰 데이터의 인덱스(이하 'start')가 피벗 보다 작은 데이터의 인덱스(이하 'end') 보다 크지 않다면(엇갈리지 않다면) 그대로 swap을 해준다. (피벗 설정을 제외하면 이전 방식과 동일하다.)

이렇게 피벗을 기준으로 swap을 해주다보면 start가 end 보다 커지는 순간이 발생한다. 이때 앞선 작업들로 인해 start 기준 왼쪽에는 start 값 보다 작은 값들이, start 기준 오른쪽에는 start 값 보다 큰 값들이 존재하게 되므로 현재 start 지점은 영역을 나누는 기준점이 되며, 아울러 정렬이 되어있는 상태라고 볼 수 있다.

이제 이 start 지점을 기준으로 영역을 반으로 나누어 앞선 작업을 반복한다.

이렇게 영역을 반으로 분할해나갈 시 분할된 영역의 크기가 1이라면 해당 영역은 정렬이 된 것으로 보고 작업을 멈춘다.

자바로 개선된 호어 분할 방식의 퀵 정렬 구현하기

앞선 원리를 적용해 개선된 호어 분할 방식의 퀵 정렬을 자바로 구현해보면 다음과 같다.

public class HoarePartitionQuickSort {

    public static void quickSort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    private static void quickSort(int[] array, int start, int end) {
        int rightPartition = getPartition(array, start, end);
        if (start < rightPartition - 1) {
            quickSort(array, start, rightPartition - 1);
        }

        if (rightPartition < end) {
            quickSort(array, rightPartition, end);
        }
    }

    private static int getPartition(int[] array, int start, int end) {
        int pivot = array[(start + end) / 2];
        while (start <= end) {
            while (array[start] < pivot) { // 피벗 보다 큰 거 선택!
                start++;
            }

            while (array[end] > pivot) { // 피벗 보다 작은 거 선택!
                end--;
            }

            if (start <= end) {
                swap(array, start, end);
                start++;
                end--;
            }
        }

        return start;
    }

    private static void swap(int[] array, int i, int minIndex) {
        int temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
}

개선된 호어 분할 방식의 퀵 정렬 성능

이제 개선된 호어 분할 방식의 퀵 정렬의 성능을 비교해보자.

앞서 기존 호어 분할 방식의 퀵 정렬이 최악의 성능을 보였던 정렬된 데이터를 정렬 시의 실행 시간을 측정하기 위해 이전과 동일하게 16500개의 정렬된 정수형 배열을 사용했다.

        int[] array1 = new int[16500];
        for (int i = 0; i < 16500; i++) {
            array1[i] = i;
        }

정렬된 데이터를 정렬함에 있어 기존 퀵 정렬 보다 성능이 확실히 개선된 것을 확인할 수 있었다.

이번엔 다음과 같이 3만개의 무작위 정수형 배열로 실행 시간을 측정해보았다.

        int[] array2 = new int[30000];
        Random random = new Random(30000);
        for (int i = 0; i < 30000; i++) {
            array2[i] = random.nextInt(30000); // 정수의 범위를 기존 0 ~ 999에서 0 ~ 29999으로 변경했다.
        }

실행 결과 기존 퀵 정렬과 개선된 퀵 정렬 간 시간 성능적으로 유의미한 차이는 없었다.

지금까지 '개선된' 호어 분할 방식의 퀵 정렬이라고 언급해오긴 했지만, 사실 피벗을 단순히 물리적으로 중간에 위치한 데이터로 설정했다고 '근본적으로' 개선되었다고 하기는 힘들다.

실제 그럴 확률은 매우 적겠지만, 중간에 위치한 데이터를 피벗으로 매번 설정할 때마다, 공교롭게도 그 지점의 값이 해당 데이터 상 가장 작은 값을 가진다면 마찬가지로 시간 복잡도는 O(N^2)이 될 것이다.

이처럼 퀵 정렬은 피벗을 어떻게 설정하냐에 따라 데이터 상태별 다른 시간 성능을 보인다. C++ 같이 퀵 정렬을 기반으로 작성된 정렬 라이브러리를 제공할 때는 최악의 경우에도 시간 복잡도 O(N * long N)이 보장되도록 피벗값을 설정할 때 추가적인 로직을 더해준다고 한다.

참고자료

한빛 미디어 출판 "이것이 취업을 위한 코딩테스트다"
유튜브 엔지니어대한민국
https://ko.wikipedia.org/wiki/퀵_정렬
https://ko.wikipedia.org/wiki/분할_정복_알고리즘

저작자표시 비영리 변경금지

'Algorithm > Basic' 카테고리의 다른 글

[정렬 연습] 병합 정렬의 원리 및 구현 - Java (0)	2022.09.11
[정렬 연습] 삽입 정렬의 원리 및 구현 - Java (0)	2022.09.07
[정렬 연습] 버블 정렬과 선택 정렬의 원리 및 구현 - Java (0)	2022.09.06
이분 탐색, Lower Bound와 Upper Bound - Java (0)	2022.08.18
[배열 연습] 2차원 배열 뱀 채우기 - Java (0)	2022.08.03

현재글[정렬 연습] 퀵 정렬의 원리 및 구현 - Java

꾸준히 합니다.

회고, Weekly I learned, wil, jvm, 마스터즈 코스, ssafy, 코드스쿼드, 자바, Weelky I iearned, 프로그래머스, 애노테이션, Spring, 개발자, 백준, Transaction, java, 접근지시자, 성장, MYSQL, BOJ,

Today :
Yesterday :

일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

Ikjo's Technology blog