C#을 사용하여 병합 정렬을 수행하는 방법은 무엇입니까?

병합 정렬은 분할 정복 방법을 사용하는 정렬 알고리즘입니다. 배열을 두 부분으로 나눈 다음 이 두 부분 각각에 대해 자신을 호출합니다. 이 과정은 배열이 정렬될 때까지 계속됩니다.

C#에서 병합 정렬을 보여주는 프로그램은 다음과 같습니다. -

예

using System;
namespace QuickSortDemo {
   class Example {
      static public void merge(int[] arr, int p, int q, int r) {
         int i, j, k;
         int n1 = q - p + 1;
         int n2 = r - q;
         int[] L = new int[n1];
         int[] R = new int[n2];
         for (i = 0; i < n1; i++) {
            L[i] = arr[p + i];
         }
         for (j = 0; j < n2; j++) {
            R[j] = arr[q + 1 + j];
         }
         i = 0;
         j = 0;
         k = p;
         while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
               arr[k] = L[i];
               i++;
            } else {
               arr[k] = R[j];
               j++;
            }
            k++;
         }
         while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
         }
         while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
         }
      }
      static public void mergeSort(int[] arr, int p, int r) {
         if (p < r) {
            int q = (p + r) / 2;
            mergeSort(arr, p, q);
            mergeSort(arr, q + 1, r);
            merge(arr, p, q, r);
         }
      }
      static void Main(string[] args) {
         int[] arr = {76, 89, 23, 1, 55, 78, 99, 12, 65, 100};
         int n = 10, i;
         Console.WriteLine("Merge Sort");
         Console.Write("Initial array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
         mergeSort(arr, 0, n-1);
         Console.Write("\nSorted Array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
      }
   }
}

출력

위 프로그램의 출력은 다음과 같습니다.

Merge Sort
Initial array is: 76 89 23 1 55 78 99 12 65 100
Sorted Array is: 1 12 23 55 65 76 78 89 99 100

이제 위의 프로그램을 이해합시다.

main() 함수에서 먼저 초기 배열이 표시됩니다. 그런 다음 mergeSort() 함수를 호출하여 배열에 대한 병합 정렬을 수행합니다. 이에 대한 코드 스니펫은 다음과 같습니다.

int[] arr = {76, 89, 23, 1, 55, 78, 99, 12, 65, 100};
int n = 10, i;
Console.WriteLine("Merge Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
   Console.Write(arr[i] + " ");
}
mergeSort(arr, 0, n-1);

mergeSort() 함수에서 q는 배열의 중간점으로 계산됩니다. 그런 다음 생성된 두 하위 배열에 대해 mergeSort()가 호출됩니다. 마지막으로 이러한 하위 배열을 병합하는 merge()가 호출됩니다. 이에 대한 코드 스니펫은 다음과 같습니다.

if (p < r) {
   int q = (p + r) / 2;
   mergeSort(arr, p, q);
   mergeSort(arr, q + 1, r);
   merge(arr, p, q, r);
}

merge() 함수에서 두 개의 정렬된 하위 배열이 제공됩니다. 이 함수는 기본적으로 결과 배열도 정렬되는 방식으로 이러한 하위 배열을 단일 배열로 병합합니다. 이에 대한 코드 스니펫은 다음과 같습니다.

int i, j, k;
int n1 = q - p + 1;
int n2 = r - q;
int[] L = new int[n1];
int[] R = new int[n2];
for (i = 0; i < n1; i++) {
   L[i] = arr[p + i];
}
for (j = 0; j < n2; j++) {
   R[j] = arr[q + 1 + j];
}
i = 0;
j = 0;
k = p;
while (i < n1 && j < n2) {
   if (L[i] <= R[j]) {
      arr[k] = L[i];
      i++;
   } else {
      arr[k] = R[j];
      j++;
   }
   k++;
}
while (i < n1) {
   arr[k] = L[i];
   i++;
   k++;
}
while (j < n2) {
   arr[k] = R[j];
   j++;
   k++;
}
while (j < n2) {
   arr[k] = R[j];
   j++;
   k++;
}