알고리즘/기타
[C#] Merge Sort
키베이루
2022. 12. 23. 17:51
합병정렬은 분할 정복(Divide and Conquer)의 알고리즘의 하나이다.
합병정렬의 핵심은 3가지이다.
Divide : 입력된 배열을 절반 씩 계속 나눈다.
void merge_sort(int left, int right, int[] arr) // 나눠!
{
// 왼쪽이 오른쪽보다 작을때만 실행하고
// 왼쪽이 오른쪽과 같아지거나 커질경우 재귀가 풀리면서 merge가 실행된다.
if (left < right)
{
int mid = (left + right) / 2; // 처음과 끝을 반으로 갈라서 (처음 ~ 중간) / (중간 ~ 끝)
merge_sort(left, mid, arr); // 처음부터 중간까지 나눈다
merge_sort(mid + 1, right, arr); // 중간부터 마지막 까지 나눈다.
merge(left, right, mid, arr); // 다시 합친다.
}
}merge_sort가 merge_sort를 다시 계속 호출하면서 left와 right의 값이 계속 작아진다.
그러다가 어느순간 left == right이 되고 이 순간 if문을 들어오지 못하게되면서 재귀가 풀린다.
이렇게 풀린 재귀는 2번째 merge_sort를 들어가서 풀리고
최종적으로 merge에 들어가게된다.
merge에 들어간 데이터는 (0) (1) (2) (3) (4) (5) (6) (7) -> (01) (23) -> (0123) -> (45) (67) -> (4567) -> (01234567) 순으로 들어간다.
Conquer : 부분 배열을 정렬한다.
while (L <= mid && R <= right)
{
// 왼쪽과 오른쪽을 비교하여 왼쪽이 더작으면
// sorted 앞 쪽 인덱스에 작은 값을 넣고 L을 오른쪽으로 한칸 이동시킨다.
if (arr[L] <= arr[R])
{
sorted[index] = arr[L];
L++;
}
else // 오른쪽이 더 크다면 sorted 앞 인덱스에 작은 값(오른쪽 값) 을 넣고 R을 오른쪽으로 한칸.
{
sorted[index] = arr[R];
R++;
}
index++;
}
if (L > mid)// 왼쪽으로 커지다가 mid를 넘어버린 경우
{
for (int i = R; i <= right; i++) // 오른쪽애를 나머지 인덱스다 전부다 집어넣기
{
sorted[index] = arr[i];
index++;
}
}
else // 아닌경우
{
for (int i = L; i <= mid; i++) // 왼쪽애를 나머지 인덱스에 전부다 집어넣기
{
sorted[index] = arr[i];
index++;
}
}
for (int i = left ; i <= right; i++) // sorted에 있는 값들을 arr에 복사 (정렬되어있는 sorted를 arr에 다시 넣어야 arr이 안겹침)
{
arr[i] = sorted[i];
}merge_sort에서 벗어난 재귀는 merge로 들어와 합병을 시작한다.
while (L <= mid && R <= right)
{
// 왼쪽과 오른쪽을 비교하여 왼쪽이 더작으면
// sorted 앞 쪽 인덱스에 작은 값을 넣고 L을 오른쪽으로 한칸 이동시킨다.
if (arr[L] <= arr[R])
{
sorted[index] = arr[L];
L++;
}
else // 오른쪽이 더 크다면 sorted 앞 인덱스에 작은 값(오른쪽 값) 을 넣고 R을 오른쪽으로 한칸.
{
sorted[index] = arr[R];
R++;
}
index++;
}(0) (1) (2) (3) (4) (5) (6) (7)로 나눠진 데이터는
arr[0] vs arr[1]중 작은 것을 sorted[k]에 할당한다.
이후 (01) vs (23)에서는
arr[0] vs arr[2]를 비교하고 만약 arr[0]가 더 작다면 왼쪽을 한칸 증가시켜 arr[1] vs arr[2]로 비교한다 반대로 arr[0] vs arr[2]을 비교해서 arr[2]가 더 작은경우 오른쪽을 한칸 증가시켜 arr[0] vs arr[3]을 비교해 더 작은 값을 sorted[k]에 할당한다.
이러한 과정이 끝나고 while문을 벗어났을 경우
if (L > mid)// 왼쪽으로 커지다가 mid를 넘어버린 경우
{
for (int i = R; i <= right; i++) // 오른쪽애를 나머지 인덱스다 전부다 집어넣기
{
sorted[index] = arr[i];
index++;
}
}
else // 아닌경우
{
for (int i = L; i <= mid; i++) // 왼쪽애를 나머지 인덱스에 전부다 집어넣기
{
sorted[index] = arr[i];
index++;
}
}마저 할당이 되지 않은 부분을 sorted에 할당하기 위해서 오른쪽 부분이 남았을 경우 R부터 시작하여 right까지 남은 부분을 sorted에 할당하고 왼쪽 부분이 남았을 경우 L부터 시작하여 mid까지 남은 부분을 sorted에 할당한다.
for (int i = left ; i <= right; i++) // sorted에 있는 값들을 arr에 복사 (정렬되어있는 sorted를 arr에 다시 넣어야 arr이 안겹침)
{
arr[i] = sorted[i];
}마지막으로 sorted에 할당이 끝났을 경우, arr에 오름차순으로 할당한 sorted를 arr 다시 할당하여 arr을 오름차순으로 바꿔준다.
크기가 8인 배열에 난수를 입력받고 Merge sort로 오름차순으로 정렬하고 최솟값을 찾는 코드
using System;
using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
using System.Linq;
using System.Runtime.InteropServices;
using System.Runtime.Intrinsics.X86;
using System.Security.AccessControl;
using System.Text;
using System.Threading.Tasks;
namespace first
{
internal class home_work_5
{
// 정렬한 데이터를 담기위한 배열
static int[] sorted = new int[8];
// conquer 정복 => 분할이 전부 완료되면 재귀가 풀리면서 merge가 실행이 된다
// 크기 8 기준으로 0 vs 1 / 2 vs 3 / 01 vs 23 / 0123 (왼쪽완성) / 4 vs 5 / 6 vs 7 / 45 vs 67 / 4567(오른쪽 완성) / 01234567(전부완성)
void merge(int left, int right, int mid, int[] arr)
{
int L = left; // 왼쪽부터 시작
int R = mid + 1; //
int index = left;
// 왼쪽에서 부터 와서 중간까지 && 중간 + 1 부터 오른쪽 까지만 반복한다
while (L <= mid && R <= right)
{
// 왼쪽과 오른쪽을 비교하여 왼쪽이 더작으면
// sorted 앞 쪽 인덱스에 작은 값을 넣고 L을 오른쪽으로 한칸 이동시킨다.
if (arr[L] <= arr[R])
{
sorted[index] = arr[L];
L++;
}
else // 오른쪽이 더 크다면 sorted 앞 인덱스에 작은 값(오른쪽 값) 을 넣고 R을 오른쪽으로 한칸.
{
sorted[index] = arr[R];
R++;
}
index++;
}
if (L > mid)// 왼쪽으로 커지다가 mid를 넘어버린 경우
{
for (int i = R; i <= right; i++) // 오른쪽애를 나머지 인덱스다 전부다 집어넣기
{
sorted[index] = arr[i];
index++;
}
}
else // 아닌경우
{
for (int i = L; i <= mid; i++) // 왼쪽애를 나머지 인덱스에 전부다 집어넣기
{
sorted[index] = arr[i];
index++;
}
}
for (int i = left ; i <= right; i++) // sorted에 있는 값들을 arr에 복사 (정렬되어있는 sorted를 arr에 다시 넣어야 arr이 안겹침)
{
arr[i] = sorted[i];
}
}
// 재귀로 함수를 구현하여 크기가 1이 될 때 까지 나눈다. => Divide 분할!
void merge_sort(int left, int right, int[] arr) // 나눠!
{
// 왼쪽이 오른쪽보다 작을때만 실행하고
// 왼쪽이 오른쪽과 같아지거나 커질경우 재귀가 풀리면서 merge가 실행된다.
if (left < right)
{
int mid = (left + right) / 2; // 처음과 끝을 반으로 갈라서 (처음 ~ 중간) / (중간 ~ 끝)
merge_sort(left, mid, arr); // 처음부터 중간까지 나눈다
merge_sort(mid + 1, right, arr); // 중간부터 마지막 까지 나눈다.
merge(left, right, mid, arr); // 다시 합친다.
}
}
static void Main(string[] args)
{
Console.WriteLine("===========합병정렬==========");
// Merge sort 사용 정렬
int[] apple = new int[8];
// 배열의 크기(8)만큼 난수를 할당
for (int i = 0; i < apple.Length; i++)
{
Random random = new Random();
apple[i] = random.Next(1, 10001);
}
Console.Write("정렬 실행 전 = ");
for (int i = 0; i < apple.Length; i++)
{
Console.Write("{0} ", apple[i]);
}
// 함수를 쓰기위해서 할당
Console.WriteLine("");
var mc = new home_work_5();
mc.merge_sort(0, 7, apple);
//정렬된 배열 출력
Console.Write("정렬 실행 후 = ");
for (int i = 0; i < 8; i++)
{
Console.Write("{0} ", sorted[i]);
}
Console.WriteLine("");
Console.WriteLine("제일 적게 먹은 사람 = {0}", sorted[0]);
}
}
}