16. 퀵 정렬(Quick Sort)과 병합 정렬(Merge Sort)

정렬을 구현하는데 있어 가장 간편하고 직관적인 알고리즘은 버블 정렬과 선택 정렬일 것입니다. 하지만 O(n^2)의 시간 복잡도를 갖고 있어 빠른 정렬에는 적합하지 않다는 단점을 갖고 있습니다. 자료가 많을 때 빠른 정렬을 하기 위해서는 일반적으로 퀵 정렬이나 병합 정렬을 사용합니다.

퀵 정렬과 병합 정렬은 모두 평균적으로 O(nlogn)의 시간 복잡도를 갖고 있는 정렬 알고리즘입니다. 이러한 시간 복잡도가 가능한 것은 두 알고리즘 모두 재귀적으로 범위를 분할하면서 정렬하기 때문입니다.

퀵 정렬 - 위키백과

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

합병 정렬 - 위키백과

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

먼저 퀵 정렬부터 살펴보겠습니다. 퀵 정렬은 피봇(pivot)이라는 값을 하나 정하고 피봇값을 기준으로 작은 수는 왼쪽으로 큰 수는 우측으로 자리를 교환해가며 수를 정렬합니다. 피봇값은 이론상 범위내 어떠한 수가 되도 상관없는 것으로 되어 있으나 배열의 양끝값 혹은 중간값 등을 고정하여 연산하는 것이 구현하기에도 편리하고 속도도 더 빠르다고 합니다. 이때 배열 좌측 끝과 우측 끝에는 포인터를 하나씩 두고 좌측의 포인터는 우측으로 우측의 포인터는 좌측으로 이동시킵니다. 좌측 포인터는 피봇값보다 작은 값을 만나면 멈추고 우측 포인터는 피봇값보다 큰값을 만나면 포인터를 멈추고 서로 자리를 바꿔줍니다. 이런 식으로 배열 안의 모든 수를 피봇 기준으로 정렬하다보면 포인터들이 서로 만나는 순간이 옵니다. 그 자리가 피봇 값이 위치할 자리입니다. 피봇과 해당 자리의 숫자를 교환해주고 현재 포인터가 멈춘 자리 기준으로 배열을 좌측과 우측으로 분할(partition)하여 앞에 진행한 것과 같은 방식으로 정렬을 진행합니다. 배열을 분할하고 분할해서 더이상 분할할 수 없을 때까지 반복적으로 정렬하면 배열이 모두 정렬되게 됩니다.

퀵 정렬을 실제로 구현한 코드는 아래와 같습니다.

2751번: 수 정렬하기 2 - Baekjoon Online Judge

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

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		quickSort(a, 0, n - 1);
		for (int i = 0; i < n; i++) {
			System.out.println(a[i]);
		}

		sc.close();
	}

	static void quickSort(int[] arr, int l, int r) {
		int i, j, pivot, tmp;

		if (r <= l)
			return;

		i = l;
		j = r;
		pivot = arr[r];
		while (i < j) {
			while (arr[i] < pivot)
				i++;
			while (i < j && arr[j] >= pivot)
				j--;

			tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
		}
		arr[r] = arr[i];
		arr[i] = pivot;

		quickSort(arr, l, i - 1);
		quickSort(arr, i + 1, r);
	}
}

병합 정렬은 재귀적으로 배열을 분할하여 제일 작은 크기, 즉 배열의 크기가 1일 때까지 분할한 후 배열을 다시 합치면서 순서에 맞게 정렬해주는 알고리즘입니다. 이론적으로는 더이상 설명할 부분이 없을만큼 명쾌합니다. 위의 정렬 문제를 병합 정렬로 풀어보겠습니다.

import java.util.Scanner;

public class Main {
	private static int[] sorted;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int[] a = new int[n];
		sorted = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		mergeSort(a, 0, n - 1);
		for (int i = 0; i < n; i++) {
			System.out.println(sorted[i]);
		}

		sc.close();
	}

	static void mergeSort(int[] a, int l, int r) {
		if (l >= r)
			return;

		int m = (l + r) / 2;

		mergeSort(a, l, m);
		mergeSort(a, m + 1, r);

		merge(a, l, m, r);
	}

	private static void merge(int[] a, int l, int m, int r) {
		int lIdx = l;
		int rIdx = m + 1;
		int idx = l;

		while (lIdx <= m && rIdx <= r) {
			if (a[lIdx] <= a[rIdx])
				sorted[idx++] = a[lIdx++];
			else
				sorted[idx++] = a[rIdx++];
		}

		while (lIdx <= m) {
			sorted[idx++] = a[lIdx++];
		}
		while (rIdx <= r) {
			sorted[idx++] = a[rIdx++];
		}
		for (int i = l; i <= r; i++) {
			a[i] = sorted[i];
		}
	}
}