https://www.youtube.com/watch?v=QAyl79dCO_k
참고한 영상
병합 정렬 소스..
using System;
using System.Text;
class HelloWorld {
static void Main() {
StringBuilder stringBuilder = new StringBuilder();
int count = int.Parse(Console.ReadLine());
int[] arr = new int[count];
for(int i = 0; i < count; i++) {
arr[i] = int.Parse(Console.ReadLine());
}
int[] tmp = new int[arr.Length];
MergeSort(arr,tmp,0,arr.Length-1);
for(int i = 0; i < arr.Length; i++)
{
stringBuilder.Append(arr[i] + "\n");
}
Console.Write(stringBuilder);
}
static void Merge(int[] arr,int[] tmp, int start, int mid, int end) {
for(int i = start; i <= end; i++) {
tmp[i] = arr[i];
}
int pointStart = start;
int pointMid = mid + 1;
int index = start;
while(pointStart <= mid && pointMid <= end) {
if(tmp[pointStart] <= tmp[pointMid]) {
arr[index] = tmp[pointStart];
pointStart++;
} else {
arr[index] = tmp[pointMid];
pointMid++;
}
index++;
}
for(int i = 0; i <= mid - pointStart; i++) {
arr[index + i] = tmp[pointStart + i];
}
}
static void MergeSort(int[] arr,int[] tmp, int start, int end) {
if(start < end) {
int mid = (start + end) / 2;
MergeSort(arr,tmp,start,mid);
MergeSort(arr,tmp,mid + 1, end);
Merge(arr,tmp,start,mid,end);
}
}
}
디버깅 결과
Original Array:
6 8 7 1 5 9 4 3 2 10
LEFT
6
RIGHT
8
Merge
6 8
LEFT
6 8
RIGHT
7
Merge
6 7 8
-------------------------------------
LEFT
1
RIGHT
5
Merge
1 5
LEFT
6 7 8
RIGHT
1 5
Merge
1 5 6 7 8
-------------------------------------
LEFT
9
RIGHT
4
Merge
4 9
LEFT
4 9
RIGHT
3
Merge
3 4 9
-------------------------------------
LEFT
2
RIGHT
10
Merge
2 10
LEFT
3 4 9
RIGHT
2 10
Merge
2 3 4 9 10
-------------------------------------
LEFT
1 5 6 7 8
RIGHT
2 3 4 9 10
Merge
1 2 3 4 5 6 7 8 9 10
-------------------------------------
Sorted Array:
1 2 3 4 5 6 7 8 9 10
이런식으로 합쳐지는건 이해했지만 결과적으론, 아직 50퍼밖에 이해 못한거같다.
또 다른 정렬 방식들을 접하면 조금씩 이해 될듯.... 알고리즘은 어렵당..
'백준 C#' 카테고리의 다른 글
백준#2587 2023-10-24 (2) | 2023.10.24 |
---|---|
백준#2750 2023-10-23 (0) | 2023.10.23 |