C 언어의 병합 정렬 기술 설명

정렬은 요소를 오름차순(또는 내림차순)으로 정렬하는 과정입니다.

정렬 유형

C 언어는 다음과 같은 5가지 정렬 기술을 제공합니다. -

• 버블 정렬(또는) 교환 정렬
• 선택 정렬
• 삽입 정렬(또는) 선형 정렬
• 빠른 정렬(또는) 파티션 교환 정렬
• 병합 정렬(또는) 외부 정렬

병합 정렬

병합 정렬은 분할 정복 방법입니다. 배열을 반으로 나누고 재귀적으로 정복하고 병합(결합)합니다.

아래에 주어진 예를 생각해 봅시다 -

정렬되지 않은 배열을 가져와 병합 정렬 기술을 적용하여 배열을 정렬합니다.

38, 27, 43, 3, 9, 82, 10

이제 아래와 같이 정렬하여 배열을 결합하십시오 -

예시

다음은 병합 정렬 기술을 사용하여 요소를 정렬하는 C 프로그램입니다 -

#include <stdio.h>
#define max 10
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];
void merging(int low, int mid, int high) {
   int l1, l2, i;
   for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
      if(a[l1] <= a[l2])
         b[i] = a[l1++];
      else
         b[i] = a[l2++];
   }
   while(l1 <= mid)
      b[i++] = a[l1++];
   while(l2 <= high)
      b[i++] = a[l2++];
   for(i = low; i <= high; i++)
      a[i] = b[i];
   }
   void sort(int low, int high) {
      int mid;
      if(low < high) {
         mid = (low + high) / 2;
         sort(low, mid);
         sort(mid+1, high);
         merging(low, mid, high);
      } else {
      return;
   }
}
int main() {
   int i;
   printf("List before sorting\n");
   for(i = 0; i <= max; i++)
   printf("%d ", a[i]);
   sort(0, max);
   printf("\nList after sorting\n");
   for(i = 0; i <= max; i++)
   printf("%d ", a[i]);
}

출력

위의 프로그램이 실행되면 다음과 같은 출력을 생성합니다 -

List before sorting
10 14 19 26 27 31 33 35 42 44 0
List after sorting
0 10 14 19 26 27 31 33 35 42 44