Merge Sort (합병 정렬)

Merge Sort (합병 정렬)

• 분할 정복 알고리즘으로 인덱스를 분할(Devide) 후, 정복(Conquer)과 결합(Combine)하는 정렬

• 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아 원래 문제를 해결하는 방법

• 장점 : 안정적인 정렬 방법. 데이터 분포에 구애받지 않고 정렬되는 시간이 동일하다.

  ​ 레코드를 연결 리스트로 구성하면 링크 인덱스만 변경되어 데이터 이동을 무시할 수 있을 정도로 작아진다.

• 단점 : 레코드를 배열로 구성할 경우, 임시 배열이 필요하다.

• 시간복잡도 : T(n) = n log_2 n

• 동작 순서

  1. 모든 배열을 하나의 배열로 나눌 때까지 배열을 같은 크기의 2개의 부분 배열로 분할한다.
  2. 나눠진 배열들을 역순으로 크기를 비교하며 정렬한다.

• Code

  #include <stdio.h>                                          // 헤더파일 선언
  #define ARRAY_SIZE 10                                       // 정렬할 배열의 크기 선언
  void merge_sort(int array[],int start, int end);            // 분할 함수 선언
  void merge(int array[], int start, int mid, int end);       // 정복 함수 선언
  
  void main()
  {
      int Arr[ARRAY_SIZE] = {3, 2, 7, 9, 5, 0, 4, 1, 8, 6};   // 임의의 정수형 배열 Arr 선언 및 초기화
      merge_sort(Arr, 0, ARRAY_SIZE-1);                       // 분할 함수 호출
      for(int i=0;i<ARRAY_SIZE;i++)                           // 배열의 크기만큼 반복
      {
          printf("%d",Arr[i]);                                // 배열의 각 값 출력
      }
  }
  
  void merge_sort(int array[],int start, int end)             // 분할 함수 선언
  {                                                           // 변수는 배열, 시작 인덱스, 끝 인덱스
      if(start<end)                                           // 끝 인덱스 크기가 시작 인덱스보다 크면
      {
          int mid = start + (end-start)/2;                    // 정수형 변수 mid 선언
          /*(start+end)/2 대신 start+(end-start)/2를 쓴 이유는 start+end 값으로 인한 오버플로우 방지*/
          merge_sort(array, start, mid);                      // 시작 인덱스부터 중간 인덱스까지 분할 함수 재귀
          merge_sort(array, mid+1, end);                      // 중간 인덱스부터 끝 인덱스까지 분할 함수 재귀
          merge(array,start,mid,end);                         // 정복 함수 호출
      }
  }
  
  void merge(int array[], int start, int mid, int end)        // 정복 함수 선언
  {                                                           // 변수는 배열, 시작 인덱스, 중간 인덱스, 끝 인덱스
      int left = start;                                       // 정수형 변수 left 선언 및 시작 인덱스 대입
      int right = mid+1;                                      // 정수형 변수 right 선언 및 중간 인덱스 + 1 대입
      int temp_place = start;                                 // 정수형 변수 time_place 선언 및 시작 인덱스 대입
      int temp[ARRAY_SIZE] = {};                              // 정렬된 배열을 대입할 임의의 정수형 배열 temp 선언
  
      while(left<=mid&&right<=end)                            // 왼쪽 배열, 오른쪽 배열이 모두 정렬에 다 사용되지 않으면 반복
      {
          if(array[left]<array[right])                        // 왼쪽 배열이 더 작으면
          {
              temp[temp_place++] = array[left++];             // temp 배열에 왼쪽 배열 대입 및 각 배열 인덱스 ++
          }
          else                                                // 오른쪽 배열이 더 작으면
          {
              temp[temp_place++] = array[right++];            // temp 배열에 오른쪽 배열 대입 및 각 배열 인덱스 ++
          }
      }
      if(left<=mid)                                           // 왼쪽 배열이 남았으면
      {
          for(left;left<=mid;left++)                          // 남은 배열만큼 반복
          {
              temp[temp_place++] = array[left];               // temp 배열에 남은 왼쪽 배열 대입
          }
      }
      else                                                    // 오른쪽 배열이 남았으면
      {
          for(right;right<=end;right++)                       // 남은 배열만큼 반복
          {
              temp[temp_place++] = array[right];              // temp 배열에 남은 오른쪽 배열 대입
          }
      }
      for(int k=start;k<=end;k++)                             // 시작 인덱스부터 끝 인덱스까지 반복
      {
          array[k] = temp[k];                                 // array에 temp의 정렬된 배열 대입
      }
  }

  Output : 0    1    2    3    4    5    6    7    8    9