C언어 병합 정렬(Merge Sort)로 배열 정렬하는 방법

배열(Array)은 공통의 이름을 공유하는 관련 데이터 항목들의 집합입니다. 배열에서 특정 값은 인덱스 번호(index number)를 통해 식별할 수 있습니다.

배열 선언하기

배열을 선언하는 기본 문법은 다음과 같습니다.

datatype array_name [size];

예시:

float marks [50]

위 코드는 실수형(float) 요소 50개를 담는 'marks' 배열을 선언합니다.

int number[10]

이 코드는 최대 10개의 정수를 저장할 수 있는 'number' 배열을 선언합니다.

배열의 각 요소는 배열 인덱스(array index)로 식별되며, 이 인덱스를 사용하면 원하는 요소에 손쉽게 접근할 수 있습니다.

병합 정렬의 동작 원리

병합 정렬은 분할 정복(Divide and Conquer) 기법을 활용한 정렬 알고리즘입니다. 배열을 반으로 나누어 각각 재귀적으로 정렬한 뒤, 두 부분을 하나로 병합하는 방식으로 작동합니다.

병합 정렬에 사용되는 핵심 로직은 다음과 같습니다.

void MergeSort(int *array, int left, int right){
   int middle = (left+right)/2;
   if(left<right){
      //왼쪽 부분 정렬
      MergeSort(array, left, middle);
      //오른쪽 부분 정렬
      MergeSort(array, middle + 1, right);
      //두 부분 병합
      Merge(array, left, middle, right);
   }
}

분할된 두 부분의 모든 요소를 하나로 병합하는 로직은 다음과 같습니다.

void Merge(int *array, int left, int middle, int right){
   int tmp[right - left + 1];
   int pos = 0, leftposition = left, rightposition = middle + 1;
   while (leftposition <= middle && rightposition <= right){
      if (array[leftposition] < array[rightposition]){
         tmp[pos++] = array[leftposition++];
      }else{
         tmp[pos++] = array[rightposition++];
      }
   }
   while (leftposition <= middle)
      tmp[pos++] = array[leftposition++];
   while (rightposition <= right)
      tmp[pos++] = array[rightposition++];
   int i;
   for (i = 0; i < pos; i++){
      array[i + left] = tmp[i];
   }
   return;
}

C 프로그램 전체 코드

다음은 병합 정렬을 구현한 완전한 C 프로그램입니다.

#include <stdio.h>
void Merge(int * , int , int , int );
void MergeSort(int *array, int left, int right){
   int middle = (left+right)/2;
   if(left<right){
      //왼쪽 부분 정렬
      MergeSort(array, left, middle);
      //오른쪽 부분 정렬
      MergeSort(array, middle + 1, right);
      //두 부분 병합
      Merge(array, left, middle, right);
   }
}
void Merge(int *array, int left, int middle, int right){
   int tmp[right - left + 1];
   int pos = 0, leftposition = left, rightposition = middle + 1;
   while (leftposition <= middle && rightposition <= right){
      if (array[leftposition] < array[rightposition]){
         tmp[pos++] = array[leftposition++];
      }
      else{
         tmp[pos++] = array[rightposition++];
      }
   }
   while (leftposition <= middle)
      tmp[pos++] = array[leftposition++];
   while (rightposition <= right)
      tmp[pos++] = array[rightposition++];
   int i;
   for (i = 0; i < pos; i++){
      array[i + left] = tmp[i];
   }
   return;
}
int main(){
   int size;
   printf("\n enter size of array:");
   scanf("%d", &size);
   int array[size];
   int i, j, k;
   printf("\n enter the elements in an array:");
   for (i = 0; i < size; i++){
      scanf("%d", &array[i]);
   }
   MergeSort(array, 0, size - 1);//정렬 함수 호출
   for (i = 0; i< size; i++){
      printf("%d ", array[i]);
   }
   printf("\n");
   return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

enter size of array:10
enter the elements in an array:
2
-10
34
-3
45
67
-89
34
23
67
-89 -10 -3 2 23 34 34 45 67 67

출력 결과를 보면 음수를 포함한 무작위 숫자들이 오름차순으로 올바르게 정렬된 것을 확인할 수 있습니다. 병합 정렬의 시간 복잡도는 O(n log n)으로, 데이터 크기가 클 때도 안정적인 성능을 보장하는 효율적인 정렬 알고리즘입니다.