[C] 병합 정렬

// mergeSort.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//

mergeSort.cpp

#include "stdafx.h"

// A[]  [IN] 데이터가 저장되어 있는 배열
// p  [IN] 병합을 수행할 첫번째 인덱스
// r  [IN] 병합을 수행할 오른쪽 블록의 첫번째 인덱스
// q  [IN] 병합을 수행할 마지막 인덱스

void merge(int A[], int p, int r, int q)
{

 int i, j; // i : 왼쪽 블록, j : 오른쪽 블록
 i = p;
 j = r;

 // 병합하기 위해서 새로운 배열 생성

 int k = 0; // 병합된 결과 배열의 인덱스
 int B[100]; // 병합된 결과 배열

 while( i < r && j <= q )
 {

  if( A[i] < A[j] )

   B[k++] = A[i++];

  else

   B[k++] = A[j++];

 }

 // 여기서는 남아있는 블록 데이터를 결과 배열에 저장한다.

 while( i < r)

  B[k++] = A[i++];

 while( j <= q )

  B[k++] = A[j++];

 // 결과 배열 내용을 A[] 배열에 저장한다.
 k = 0;
 while( p <= q )

  A[p++] = B[k++];

}

// A[]  [IN] 데이터가 저장되어 있는 배열
// p  [IN] 정렬을 수행할 첫번째 인덱스
// q  [IN] 정렬을 수행할 마지막 인덱스

void mergeSort(int A[], int p, int q)
{

 if( q <= p )

  return;

 int r = (p+q+1)/2;

 mergeSort(A, p, r-1);
 mergeSort(A, r, q);
 merge(A, p, r, q);

}

void Display(int A[], int n)
{

 for( int i = 0; i < n; i++)

  printf("%d ", A[i]);

 printf("\n");

}

int _tmain(int argc, _TCHAR* argv[])
{

 int A[] = { 3, 7, 2, 4, 1, 8, 5, 6, 10, 9 };

 Display(A, 10);
 mergeSort(A, 0, 9);
 Display(A, 10);

 return 0;

}

실행 결과..

그래픽 요소 추가..

#include "stdafx.h"
#include <stdlib.h>
#include <windows.h>

void Display(int A[], int n);

// A[]  [IN] 데이터가 저장되어 있는 배열
// p  [IN] 병합을 수행할 첫번째 인덱스
// r  [IN] 병합을 수행할 오른쪽 블록의 첫번째 인덱스
// q  [IN] 병합을 수행할 마지막 인덱스

void merge(int A[], int p, int r, int q)
{

 int i, j; // i : 왼쪽 블록, j : 오른쪽 블록
 i = p;
 j = r;

 // 병합하기 위해서 새로운 배열 생성

 int k = 0; // 병합된 결과 배열의 인덱스
 int B[100]; // 병합된 결과 배열

 while( i < r && j <= q )
 {

  if( A[i] < A[j] )

   B[k++] = A[i++];

  else

   B[k++] = A[j++];

 }

 // 여기서는 남아있는 블록 데이터를 결과 배열에 저장한다.

 while( i < r)

  B[k++] = A[i++];

 while( j <= q )

  B[k++] = A[j++];

 // 결과 배열 내용을 A[] 배열에 저장한다.

 k = 0;

 while( p <= q )

  A[p++] = B[k++];

}

// A[]  [IN] 데이터가 저장되어 있는 배열
// p  [IN] 정렬을 수행할 첫번째 인덱스
// q  [IN] 정렬을 수행할 마지막 인덱스

void mergeSort(int A[], int p, int q)
{

 if( q <= p )

  return;

 int r = (p+q+1)/2;   // (p+q)/2;

 mergeSort(A, p, r-1);  // (A, p, r);
 mergeSort(A, r, q);   // (A, r+1, q);
 merge(A, p, r, q);   // (A, p, r+1, q);

 Display(A, 20);

}

void Display(int A[], int n)
{

 const char *s = "##########################################";
 system("cls");
 for( int i = 0; i < n; i++)

  printf("%3d : %.*s\n", A[i], A[i], s);

 Sleep(500);

}

int _tmain(int argc, _TCHAR* argv[])
{

 int A[20];

 for(int i = 0; i < 20; i++)

  A[i] = rand()%30+1;

 Display(A, 20);
 mergeSort(A, 0, 19);
 Display(A, 20);

 return 0;

}

실행 결과..

두개의 배열이 정렬되고 병합되어 정렬된다..