병합 정렬이란?
- 안정 정렬에 속하는 분할 정복 알고리즘의 하나.
- 하나의 리스트를 두 개의 균등한 크기로 분할하고 부분 리스트를 정렬한 후 두 개의 정렬 리스트를 합하여 전체 정렬된 리스트가 되도록 하는 방법
- 평균 및 최악의 경우에 O(n log n) 시간 복잡도를 가지며 공간 복잡도는 추가 배열을 위해 O(n)이다.
병합 정렬의 과정
- Divide(분할) : 정렬할 배열을 두 개의 하위 배열로 나누고 나눌 수 없을 때까지 반복 (1개 또는 0개 요소를 가질 때까지)
- Cinquer(정복) : 각 하위 배열이 정렬될 상태로 만들어질 때까지병합
- Combine(결합) : 두 개의 정렬된 하위 배열을 하나로병합
Java 예제
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] array = {38, 27, 43, 3, 9, 82, 10};
System.out.println("정렬 전: " + Arrays.toString(array));
// 정렬 START
mergeSort(array);
System.out.println("정렬 후: " + Arrays.toString(array));
}
// 병합 정렬 함수
public static void mergeSort(int[] array) {
// 1개 또는 0개 요소를 가질 때까지 반복
if (array.length < 2) {
return;
}
//반으로 나누기 위하여
int mid = array.length / 2;
int[] left = Arrays.copyOfRange(array, 0, mid); //0 ~ 반까지
int[] right = Arrays.copyOfRange(array, mid, array.length); //반 ~ 끝까지
// 재귀적으로 분할
mergeSort(left);
mergeSort(right);
// 분할된 배열을 병합
merge(array, left, right);
}
// 병합 함수: 두 개의 정렬된 하위 배열을 하나로 합친다.
public static void merge(int[] array, int[] left, int[] right) {
int i = 0 //left 배열
, j = 0 //right 배열
, k = 0; //결과, array 배열
// left, right 비교하여 해당 배열의 인덱스 증가(i,j)
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
array[k++] = left[i++];
} else {
array[k++] = right[j++];
}
}
// 왼쪽 배열에 남은 요소를 복사 (그대로 넣기만)
while (i < left.length) {
array[k++] = left[i++];
}
// 오른쪽 배열에 남은 요소를 복사 (그대로 넣기만)
while (j < right.length) {
array[k++] = right[j++];
}
}
}
백준 24060번 문제
오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자.
크기가 N인 배열에 대한 병합 정렬 의사 코드는 다음과 같다.
merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다.
if (p < r) then {
q <- ⌊(p + r) / 2⌋; # q는 p, r의 중간 지점
merge_sort(A, p, q); # 전반부 정렬
merge_sort(A, q + 1, r); # 후반부 정렬
merge(A, p, q, r); # 병합
}
}
# A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
# A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
merge(A[], p, q, r) {
i <- p; j <- q + 1; t <- 1;
while (i ≤ q and j ≤ r) {
if (A[i] ≤ A[j])
then tmp[t++] <- A[i++]; # tmp[t] <- A[i]; t++; i++;
else tmp[t++] <- A[j++]; # tmp[t] <- A[j]; t++; j++;
}
while (i ≤ q) # 왼쪽 배열 부분이 남은 경우
tmp[t++] <- A[i++];
while (j ≤ r) # 오른쪽 배열 부분이 남은 경우
tmp[t++] <- A[j++];
i <- p; t <- 1;
while (i ≤ r) # 결과를 A[p..r]에 저장
A[i++] <- tmp[t++];
}
입력
첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 10⁸ )가 주어진다.
다음 줄에 서로 다른 배열 A의 원소 A₁, A₂, ..., AN 이 주어진다. (1 ≤ Ai ≤ 10⁹)
출력
배열 A에 K 번째 저장 되는 수를 출력한다. 저장 횟수가 K 보다 작으면 -1을 출력한다.
예제 입력 1
5 7
4 5 1 3 2예제 출력 1
3
예제 입력 2
5 13
4 5 1 3 2예제 출력 2
-1
문제를 요약하자면,
병합 정렬 알고리즘을 구현하고, 정렬 과정 중 K 번째 배열에 저장되는 수를 출력한다.
K번째가 없다면 -1을 출력하면 된다.
이 문제에서는 K번째가 위치를 추적하는 것이 핵심이다.
import java.util.Scanner;
public class Main {
static int count = 0; // 현재까지 몇 번째 저장인지 추적
static int k; // 문제에서 요구하는 k번째 위치
static int result = -1; // k번째 값을 저장할 변수
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
//배열 크기(N)와 위치(K)를 입력 받음
int n = scanner.nextInt();
k = scanner.nextInt(); // k번째 저장되는 위치
//n만큼 배열 선언
int[] array = new int[n];
//원소 입력
for (int i = 0; i < n; i++) {
array[i] = scanner.nextInt();
}
// 정렬 START
mergeSort(array);
System.out.println(result);
}
// 병합 정렬 함수
public static void mergeSort(int[] array) {
// 1개 또는 0개 요소를 가질 때까지 반복
if (array.length < 2) {
return;
}
// 반으로 나누기 위하여
int mid = array.length / 2;
int[] left = new int[mid]; // 0 ~ 반까지
int[] right = new int[array.length - mid]; // 반 ~ 끝까지
// 원본 배열의 앞부분을 left 배열로 복사
for (int i = 0; i < mid; i++) {
left[i] = array[i];
}
// 원본 배열의 뒷부분을 right 배열로 복사
for (int i = mid; i < array.length; i++) {
right[i - mid] = array[i];
}
// 재귀적으로 분할
mergeSort(left);
mergeSort(right);
// 정렬된 두 배열을 병합
merge(array, left, right);
}
// 병합 함수: 두 개의 정렬된 하위 배열을 하나로 합친다.
public static void merge(int[] array, int[] left, int[] right) {
int i = 0 // left 인덱스
, j = 0 // right 인덱스
, t = 0; // 병합된 배열의 인덱스
// left, right 비교하며 병합
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
array[t++] = left[i++]; // left 요소를 결과에 추가
} else {
array[t++] = right[j++]; // right 요소를 결과에 추가
}
count++; // 배열 저장 시 카운트 증가
if (count == k) { // k 번째 저장인지 확인하여 맞다면 result에 저장하며 종료
result = array[t - 1];
return;
}
}
// left 배열에 남은 요소들 추가
while (i < left.length) {
array[t++] = left[i++];
count++;
if (count == k) {
result = array[t - 1];
return;
}
}
// right 배열에 남은 요소들 추가
while (j < right.length) {
array[t++] = right[j++];
count++;
if (count == k) {
result = array[t - 1];
return;
}
}
}
}'CS 공부 > 알고리즘' 카테고리의 다른 글
| [CS-알고리즘] 삽입 정렬에 대해서 (0) | 2024.08.12 |
|---|---|
| [CS 알고리즘] 거품 정렬에 대해서 (0) | 2024.08.03 |