알고리즘
[알고리즘] 버블/선택/삽입/병합/퀵 정렬 그리고 Arrays.sort
쿠마냥
2025. 1. 5. 13:30
백준의 2751번 문제를 여러 정렬로 풀어보았다.
https://www.acmicpc.net/problem/2751
이중 시간초과가 나지 않은 방법은 '병합 정렬'과 Arrays.sort 였는데, 왜 이러한 결과가 나오는지 파헤쳐보자.
1. 버블 정렬
붙어 있는 두 개의 값을 비교한 뒤, 큰 수가 오른쪽으로 가도록 swap을 진행한다. (이 모습이 보글보글해 보여... 버블 정렬이라고 부른단다.)
더 이상 바뀌는 수가 없을 때까지, 즉 정렬이 완료될 때까지 반복한다.
최악의 경우, (n-1) + (n-2) +
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class 수정렬하기2_2751 {
static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
// 버블 정렬
bubbleSort(arr);
for (int i = 0; i < n; i++) {
System.out.println(arr[i]);
}
}
static void bubbleSort(int[] arr) {
boolean swapped;
for (int i = 0; i < arr.length - 1; i++) {
swapped = false;
for (int j = 0; j < arr.length-1; j++) {
if (arr[j] > arr[j + 1]) {
swap(j, j + 1);
swapped = true;
}
}
if (!swapped) {
break;
}
}
}
static void swap(int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
2. 선택 정렬
배열에서 가장 작은 값을 찾아 첫 번째 자리로 이동. 그다음 작은 값을 찾아 두 번째 자리로 이동하는 식으로 반복한다.
시간/공간 복잡도는 버블 정렬과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class 수정렬하기2_2751 {
static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
// 선택정렬
selectionSort(arr);
for (int i = 0; i < n; i++) {
System.out.println(arr[i]);
}
}
static void selectionSort(int[] arr) {
int min;
int minIdx;
for (int i = 0; i < arr.length; i++) {
min = arr[i];
minIdx = i;
for (int j = i+1; j < arr.length; j++) {
if (arr[j] < min) {
min = arr[j];
minIdx = j;
}
}
swap(i, minIdx);
}
}
static void swap(int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
3. 삽입 정렬
배열의 1번 부터 시작, 왼쪽이 정렬되어 있다고 가정한다.
왼쪽과 비교하여 들어가야 할 부분에 값을 삽입한다.
최악의 경우 O(n*n)이지만, 이미 정렬된 경우 O(n)으로 처리가 빠르다.
공간 복잡도는 O(1).
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class 수정렬하기2_2751 {
static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
// 삽입정렬
insertionSort(arr);
for (int i = 0; i < n; i++) {
System.out.println(arr[i]);
}
}
static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int num = arr[i];
int j = i-1;
while(j >= 0 && arr[j] > num) {
arr[j+1] = arr[j]; // 오른쪽으로 한칸 이동
j--;
}
// 만약 arr[j]가 num보다 크지 않으면
// 바로 그 숫자 오른쪽, 즉 arr[j+1]에 num을 삽입
arr[j+1] = num;
}
}
}
4. 병합 정렬
배열을 다 쪼갠 후에, 왼쪽 오른쪽 합치면서(병합하면서) 정렬하는 방법.
temp에서 정렬 후, 이를 원래의 array에 복사하기 때문에 추가 메모리가 필요하다. 따라서 공간 복잡도 O(n).
모든 데이터를 한 번씩 보기 때문에 n번, 데이터를 반씩 나누는 과정은 logN.
즉, 16개의 데이터가 있으면 반씩 쪼개기 + 이를 병합하면서 16번 확인 -> 따라서 시간 복잡도는 O(n log n).
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class 수정렬하기2_2751 {
static int[] arr, temp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
arr = new int[n];
temp = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
// 병합정렬
mergeSort(0, n-1);
for (int i = 0; i < n; i++) {
System.out.println(arr[i]);
}
}
static void mergeSort(int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
mergeSort(left, mid);
mergeSort(mid + 1, right);
merge(left, mid, right);
}
static void merge(int left, int mid, int right) {
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k] = arr[i];
k++;
i++;
} else {
temp[k] = arr[j];
k++;
j++;
}
}
while (i <= mid) {
temp[k] = arr[i];
k++;
i++;
}
while (j <= right) {
temp[k] = arr[j];
k++;
j++;
}
for (int l = 0; l < j; l++) {
arr[l] = temp[l];
}
}
}
5. 퀵 정렬
pivot을 기준으로 왼쪽, 오른쪽 나눠가며 정렬을 반복한다.
pivot은 보통 맨 왼쪽, 맨 오른쪽, 중간으로 잡는데, pivot의 크기에 따라 성능 차이가 많이 난다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class 수정렬하기2_2751 {
static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
// 퀵정렬
quickSort(0, n-1);
for (int i = 0; i < n; i++) {
System.out.println(arr[i]);
}
}
static void quickSort(int left, int right) {
if (left >= right) {
return;
}
int pivot = partition(left, right);
quickSort(left, pivot-1);
quickSort(pivot+1, right);
}
static int partition(int left, int right) {
int pivot = arr[right];
int i = left -1; // 피벗보다 작은 요소를 위한 가상 인덱스?
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
swap(i, j);
}
}
swap(i+1, right);
return i+1;
}
static void swap(int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
퀵 정렬은 빠른 정렬로도 알려져 있는데, 해당 문제에서는 시간 초과가 났다.
pivot을 맨 오른쪽에서 왼쪽으로 옮겨 보았지만 마찬가지였다.
System.out.println을 BufferedWriter로 바꿔보아도 똑같았다.
import java.io.*;
public class 수정렬하기2_2751 {
static int[] arr;
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());
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
// 퀵정렬
quickSort(0, n-1);
for (int i = 0; i < n; i++) {
bw.write(arr[i] + "\n");
}
bw.flush();
bw.close();
}
static void quickSort(int left, int right) {
if (left >= right) {
return;
}
int pivot = partition(left, right);
quickSort(left, pivot-1);
quickSort(pivot+1, right);
}
static int partition(int left, int right) {
int pivot = arr[left];
int i = left;
for (int j = left+1; j <= right; j++) {
if (arr[j] <= pivot) {
i++;
swap(i, j);
}
}
swap(left, i);
return i+1;
}
static void swap(int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
7. Arrays.sort()
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class 수정렬하기2_2751 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
for (int i = 0; i < n; i++) {
System.out.println(arr[i]);
}
}
}
Arrays.sort()가 통과될 것이라 생각하지 못했는데, 잘 되어서 당황했다.
내부가 어떻게 생겼길래 다른 정렬들보다 빠른 성과를 낸 걸까?
Arrays.sort()는 DualPivotQuicksort 알고리즘을 사용한다. 설명을 보면, 모든 데이터을 O(n log(n))의 시간 복잡도를 들여 정렬할 수 있으며, 원래의 퀵 정렬보다 빠르다고 나와 있다.
This algorithm offers O(n log(n)) performance on all data sets, and is typically faster than traditional (one-pivot) Quicksort implementations.
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, 0, a.length);
}
해당 알고리즘을 살펴보자.
설명에 따르면, 1) 병렬 병합 정렬 2) 이중 피벗 퀵 정렬을 and/or 방식으로 사용해서 정렬한다.
'병렬 병합 정렬'은 데이터를 여러 조각으로 쪼갠 후에 '동시에 처리(병렬 처리)' 해서 빠르게 정렬하는 방식이다.
'이중 피벗 퀵 정렬'은 두 개의 기준점(피벗)을 사용하여 데이터를 세 부분으로 나누고, 각 부분을 정렬하는 방식이다.
데이터가 작으면 '이중 피벗 퀵 정렬'을, 데이터가 크면 '병렬 병합 정렬'을 사용한다.
또한 정렬 데이터를 (어떤 내부적인 메커니즘을 통해) 여러 단계로 나누어 처리하여, 각 단계에서 가장 적합한 정렬 방식을 사용한다.
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. Params: a – the array to be sorted parallelism – the parallelism level low – the index of the first element, inclusive, to be sorted 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);
}
}
이때 병합 정렬이 필요한 경우 new Sorter().invoke()로 처리를 하고, 아닌 경우 일반 sort()를 진행한다.
sort()를 살펴보자. 어떤 기준으로 배열을 나누어 각각의 상황에 다른 정렬을 활용하는지 주석으로 달아두었다.
/**
* @param sorter 병렬 처리를 위한 컨텍스트 (병렬 처리가 아닌 경우 null로 진행하며, 현재 살펴볼 코드는 병렬 처리가 아니기 때문에 해당 파라미터는 Null로 입력된다.)
* @param a 정렬할 배열
* @param bits 재귀 깊이와 비트 플래그를 조합한 값
* - 오른쪽 비트가 "0"이면 배열이 가장 왼쪽 부분임을 나타냄
* @param low 정렬할 첫 번째 요소의 인덱스 (포함)
* @param high 정렬할 마지막 요소의 인덱스 (포함하지 않음)
*/
static void sort(Sorter sorter, int[] a, int bits, int low, int high) {
while (true) {
int end = high - 1; // 마지막 인덱스
int size = high - low; // 정렬할 범위의 크기
/*
* MAX_MIXED_INSERTION_SORT_SIZE인 65보다 작고
* 배열이 왼쪽 부분이 아닌 경우 'mixedInsertSort'를 수행.
* 퀵 정렬은 피벗으로 왼쪽, 오른쪽을 나눠서 처리하는데,
* 왼쪽 부분은 퀵 정렬로 처리하는 게 효과적이고(큰 배열일 가능성이 높기 때문에)
* 오른쪽 부분은 mixedInsertSort로 처리하는 게 효과적이다.
* 왜냐하면 퀵 정렬은 왼쪽, 오른쪽 중 항상 왼쪽을 먼저 정렬하는데
* 이는 왼쪽을 아직 나누기 전에 먼저 정렬하므로 크기가 더 큰 배열일 가능성이 높기 때문이다.
*/
if (size < MAX_MIXED_INSERTION_SORT_SIZE + bits && (bits & 1) > 0) {
mixedInsertionSort(a, low, high - 3 * ((size >> 5) << 3), high);
return;
}
/*
* MAX_MIXED_INSERTION_SORT_SIZE인 65보다 작고
* 배열의 왼쪽 부분(배열의 크기가 클 확률이 높으면) 삽입 정렬을 수행한다.
*/
if (size < MAX_INSERTION_SORT_SIZE) {
insertionSort(a, low, high);
return;
}
/*
* bits는 현재의 재귀 깊이이다. bits==0 재귀 깊이가 0이라는 뜻이므로
* 재귀할 필요 없이 병합만 시도하면 된다.
*/
if ((bits == 0 || size > MIN_TRY_MERGE_SIZE && (bits & 1) > 0)
&& tryMergeRuns(sorter, a, low, size)) {
return;
}
/*
* 재귀 깊이가 너무 깊어질 경우 퀵 정렬의 성능이 떨어지기 때문에
* 힙 정렬을 실시한다.
*/
if ((bits += DELTA) > MAX_RECURSION_DEPTH) {
heapSort(a, low, high);
return;
}
/*
* 위의 경우에 해당하지 않으면 '이중 피벗 정렬'을 실시한다.
* 이를 위해서는 두 개의 피벗을 잘 골라야 하는데,
* 효율적인 피벗을 선택하기 위해서 아래의 계산을 실시한다.
* random하게 두 개의 피벗을 고르는 게 아니라 적절히 떨어진 피벗을 고르기 위해 이를 실시한다.
*/
int step = (size >> 3) * 3 + 3;
/*
* 배열에서 5개의 값을 고른다.
*/
int e1 = low + step;
int e5 = end - step;
int e3 = (e1 + e5) >>> 1;
int e2 = (e1 + e3) >>> 1;
int e4 = (e3 + e5) >>> 1;
int a3 = a[e3];
/*
* 5개의 샘플을 작은 순서대로 정렬한다.
* 이를 통해 가장 작은 값과 가장 큰 값을 파악한다.
*/
if (a[e5] < a[e2]) { int t = a[e5]; a[e5] = a[e2]; a[e2] = t; }
if (a[e4] < a[e1]) { int t = a[e4]; a[e4] = a[e1]; a[e1] = t; }
if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t; }
if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
if (a[e4] < a[e2]) { int t = a[e4]; a[e4] = a[e2]; a[e2] = t; }
if (a3 < a[e2]) {
if (a3 < a[e1]) {
a[e3] = a[e2]; a[e2] = a[e1]; a[e1] = a3;
} else {
a[e3] = a[e2]; a[e2] = a3;
}
} else if (a3 > a[e4]) {
if (a3 > a[e5]) {
a[e3] = a[e4]; a[e4] = a[e5]; a[e5] = a3;
} else {
a[e3] = a[e4]; a[e4] = a3;
}
}
/*
* 2개의 피벗을 중심으로 데이터를 3부분으로 나눈다.
* 이후 퀵 정렬을 실시한다.
*/
if (a[e1] < a[e2] && a[e2] < a[e3] && a[e3] < a[e4] && a[e4] < a[e5]) {
int pivot1 = a[e1];
int pivot2 = a[e5];
if (size > MIN_PARALLEL_SORT_SIZE && sorter != null) {
sorter.forkSorter(bits | 1, lower + 1, upper);
sorter.forkSorter(bits | 1, upper + 1, high);
} else {
sort(sorter, a, bits | 1, lower + 1, upper);
sort(sorter, a, bits | 1, upper + 1, high);
}
} else {
int pivot = a[e3];
for (int k = ++upper; --k > lower; ) {
int ak = a[k];
if (ak != pivot) {
a[k] = pivot;
if (ak < pivot) { // 작은 값
while (a[++lower] < pivot);
if (a[lower] > pivot) {
a[--upper] = a[lower];
}
a[lower] = ak;
} else { // 큰 값
a[--upper] = ak;
}
}
}
a[low] = a[lower];
a[lower] = pivot;
}
// 재귀적으로 왼쪽 부분 먼저 정렬, 이후 오른쪽 부분을 정렬하는데
// 이는 위의 'sort(sorter, a, bits | 1, upper + 1, high);' 에서 실행된다.
high = lower;
}
}
코드를 전부 이해하지는 못했지만, sort()가 각 배열의 크기와 효과적인 경우를 찾아 정렬을 수행하고 있음을 알 수 있었다.
이를 통해 같은 일을 수행하더라도, 각각의 경우에 따라 로직을 작성할 때 넓은 범위를 커버하는 코드가 됨을 이해하였다.
더불어, 왜 병합 정렬은 통과하고 퀵 정렬은 2751번 문제를 통과하지 못하는지 궁금해서
퀵 정렬보다 병합 정렬이 빠른 경우를 찾아 보았다.
- 데이터가 거의 정렬된 경우
- 데이터가 크고 메모리가 충분한 경우
- 안정 정렬이 필요한 경우(동일한 값을 가진 요소의 순서를 유지)
- 데이터가 LinkedList로 저장된 경우
- 비효율적인 피벗이 선택된 경우
어떤 테스트 케이스들이 사용되는지 알지 못 해 정확한 원인을 파악하긴 힘들었다.
하지만 2초라는 시간 내에 충분한 메모리를 쓸 수 있으며 + 백만 건의 큰 데이터를 처리해야 하는 해당 문제에서 병합 정렬이 더욱 효율적이었으리라 생각한다.
퀵 정렬은 피벗에 따라 성능이 크게 좌우되기 때문에, 테스트 케이스의 맨 왼쪽/오른쪽 끝에 이를 위한 비효율적인 피벗(가장 작은/큰 값)을 일부러 넣어놓지 않았을까도 생각해 본다.