퀵 정렬 Quick Sort에 대하여

퀵 정렬은 한 개의 pivot 값을 정하여 그 값을 제자리로 보내고, pivot의 왼쪽 부분과 오른쪽 부분을 다시 재귀적으로 수행하여, 부분의 길이가 1 이하일 때를 base condition으로 종료하는 정렬 방법이다.

 

정리해보면,

 

1-1. 만약 부분의 길이가 1 이하이면 종료한다.

1-2. pivot 값을 제자리로 보낸다. (정렬되었을 때의 제자리로 보낸 다는 뜻이다.)

2. pivot의 위치를 기준으로 왼쪽 부분과 오른쪽 부분에 대하여 1번을 수행한다.

 

그렇다면 어떻게 pivot 값을 제자리로 보낼 수 있을까?

 

길이가 n인 배열 arr에서, 첫 번째 요소를 pivot이라고 하자. (사실상 맨 첫 번째 값을 pivot이라 하지 않고 다른 값을 선택한다고 하더라도, 그 값과 맨 첫 번째 값을 교환하면 되기 때문에 차이가 없다.)

 

첫 번째 방법. 배열을 순회하며 작은 값과 큰 값을 저장하여 이어 붙이는 방식

 

1. pivot을 제외한 나머지 n-1을 순회하며 pivot보다 작은 값들들 tmp배열에 추가한다.

2. tmp 배열에 pivot값을 추가한다.

3. 다시 n-1을 순회하며 tmp배열에 큰 값들을 추가한다.

 

이 방식으로는 O(n)으로 구할 수 있고, n만큼의 추가 배열이 필요하다는 단점이 있다.

 

 

두 번째 방법. pivot값을 기준으로 작은 값과 큰 값을 교환해나가는 방식

 

pivot을 제외한 양 끝을 가리키는 인덱스를 l과 r이라고 하자.

1. l이 범위의 끝보다 작고, arr [l] 값이 pivot보다 작은 동안 l 값을 증가시킨다.

2. r이 범위의 시작보다 크고, arr [r] 값이 pivot 보다 큰 동안 r 값을 감소시킨다.

3-1. 만약 l과 r이 교차되어 l 값이 r 값보다 크다면, arr [r] 값과 pivot값을 교환하고 종료한다.

3-2. l <r이라면, arr [l] 값과 arr [r] 값을 교환한다.

 

이 방법으로는 l과 r이 한 번씩 순회하므로 O(n)이고,  추가 배열이 필요하지 않다. (값을 교환할 때, 저장해둘 변수는 필요하다.)

또한, 배열 안에서의 자리바꿈만으로 처리가 되기 때문에 cache hit rate가 높아서 속도가 빠르다.

 

첫 번째 방법으로 퀵 소트를 구현한다면, 추가적인 공간이 필요하지 않은 In-Place Sort인 퀵 소트의 장점이 사라진다.

따라서, 추가적인 공간이 필요하지 않은 두 번째 방법으로 퀵 소트를 구현해야 한다.

 

 

두 번째 방법으로 Quick Sort를 직접 구현하여 보았다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

class Main {

	static int place_pivot(int[] arr, int st, int en) {
		int pivot = arr[st];
		int l = st + 1;
		int r = en - 1;

		while (l <= r) {

			while (l < en && arr[l] < pivot)
				l++;
			while (r > st && arr[r] > pivot)
				r--;

			if (l > r) {
				arr[st] = arr[r];
				arr[r] = pivot;
				return r;
			} else {
				int tmp = arr[l];
				arr[l] = arr[r];
				arr[r] = tmp;
			}
		}
		return r;
	}

	static void quick_sort(int[] arr, int st, int en) {

		if (en - st <= 1) {
			return;
		} else {
			int pi = place_pivot(arr, st, en);
			quick_sort(arr, st, pi);
			quick_sort(arr, pi + 1, en);
		}
	}

	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[] arr = new int[n];

		for (int i = 0; i < n; i++)
			arr[i] = Integer.parseInt(br.readLine());

		quick_sort(arr, 0, arr.length);

		for (int x : arr) {
			System.out.println(x);
		}

		bw.flush();
		br.close();
		bw.close();
	}
}

 

 

그런데 맨 앞자리의 요소를 pivot으로 선택하는 퀵 정렬에는 치명적인 단점이 있다.

바로 pivot 선택에 따라서 pivot의 선택이 적절하여 왼쪽 부분과 오른쪽 부분이 잘 나뉜다면 O(N)을 logN단계 수행하는 N*logN의 시간 복잡도를 갖지만, 배열이 애초에 정렬되어있거나, 역순으로 정렬하는 경우 O(N)을 N단계 수행하는 N * N인 N^2의 시간 복잡도를 갖게 된다.

 

그런데 C++이나 JAVA 등 대부분의 라이브러리에서 제공하는 정렬 함수는 퀵 정렬을 사용한다고 한다.

어떻게 된 일일까?

그것은 바로 pivot값에 대해 다양한 처리를 해주기 때문이다. pivot값을 랜덤 하게 택하거나, pivot 후보를 3개 정해서 그 3개 중 중앙값을 피벗으로 선택하기도 한다.

최악의 경우에도 NlogN을 보장하기 위하여 일정 깊이 이상 깊어지면 O(N log N)이 보장되는 힙 소트로 정렬하는 Introspective sort를 하기도 한다. 

 

 

그러면 라이브러리에서는 O(N logN)이 보장되는 힙 소트나 머지 소트를 하면 되지, 왜 굳이 이러한 처리를 하면서까지 퀵 정렬을 선택한 것일까?

 

1. 추가적으로 필요한 공간이 O(1)이기 때문에, (l, r 같은 변수를 사용하므로) (Merge Sort는 O(n))

2. 평균적으로 Merge Sort보다 빠르기 때문에, (Cache hit rate가 높다.)

 

 

 

궁금해서 JAVA Arrays.sort()의 함수는 어떤 방식으로 정렬할까? 살펴보았다.

 

DualPivotQuickSort를 하고, 모든 데이터 셋에서 O(n log(n))을 보장한다고 한다.

    /**
     * Sorts the specified array into ascending numerical order.
     *
     * @implNote The sorting algorithm is a Dual-Pivot Quicksort
     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
     * offers O(n log(n)) performance on all data sets, and is typically
     * faster than traditional (one-pivot) Quicksort implementations.
     *
     * @param a the array to be sorted
     */
    public static void sort(int[] a) {
        DualPivotQuicksort.sort(a, 0, 0, a.length);
    }

 

DualPivotQuicksort를 들어갔더니, 

    /**
     * Sorts the specified range of the array using parallel merge
     * sort and/or Dual-Pivot Quicksort.
     *
     * To balance the faster splitting and parallelism of merge sort
     * with the faster element partitioning of Quicksort, ranges are
     * subdivided in tiers such that, if there is enough parallelism,
     * the four-way parallel merge is started, still ensuring enough
     * parallelism to process the partitions.
     *
     * @param a the array to be sorted
     * @param parallelism the parallelism level
     * @param low the index of the first element, inclusive, to be sorted
     * @param high the index of the last element, exclusive, to be sorted
     */
    static void sort(int[] a, int parallelism, int low, int high) {
        int size = high - low;

        if (parallelism > 1 && size > MIN_PARALLEL_SORT_SIZE) {
            int depth = getDepth(parallelism, size >> 12);
            int[] b = depth == 0 ? null : new int[size];
            new Sorter(null, a, b, low, size, low, depth).invoke();
        } else {
            sort(null, a, 0, low, high);
        }
    }

4-way 병합정렬..?

 

하여간 저 내부의 sort함수를 읽어보니, MAX_RECURSION_DEPTH가 설정되어있었고, 깊이가 그 이상으로 깊어지면 heapsort로 스위칭한다.

 

DualPivot이라는 것도, 5개의 요소를 구해서 

if문으로 직접 정렬을 한 뒤에, (주석이 너무너무 친절해서 이해할 수 있었다.)

 

pivot1, pivot2를 설정하고, 

pivot을 두 개 설정하여, 이런 식으로 구간을 3 분할하여 정렬하는 것 같았다. 사실 라이브러리를 구경하는 게 거의 처음인데 자세하고 친절한 주석들과 주석으로 그림을 그려둔 것을 보고 깜짝 놀랐다.

 

 

 

 

 

하여간 결론은

라이브러리의 정렬은 퀵 소트를 사용하지만, 최악의 경우를 방지하기 위한 다양한 처리를 하고 있다.

따라서, 직접 정렬을 구현하여 사용하는 경우에는,

절대 절대 절대 절대 퀵 소트를 구현하여 사용하지말자. 

 

 

 

 

 

참고 : 바킹독님의 실전 알고리즘 강의 영상 https://youtu.be/59fZkZO0Bo4