합병정렬

예전에 네이버 블로그에 올렸던 건데, 이 쪽으로 이사하면서 다시 올려본다.

 

 

 

 

 

이를 c언어 코드로 나타낼려면 다음 코드와 같이 재귀를 사용 하여야 한다.

 

 

 

이곳에 붙여넣는 과정에서 주석의 스페이스가 모두 없어졌습니다. 이점 양해해 주세요.

 

#include

#include

#include

 

#defineCARDSIZE10    // 정수배열의사이즈

 

voidMergeSort(int* array, intsize, intfirst, intend); // 합병정렬을하는함수

voidprintArray(int* card, intsize); // 정수배열을화면에출력하는함수.

 

intmain()

{

           intCard[CARDSIZE];                     // 정수배열선언

           inti;                                  // 반복문에쓰일변수

 

           srand((unsignedint)time(NULL));    // Random Value For Seed Value Set

 

           for(i= 0; i< CARDSIZE; i++)           // 랜덤한수로배열을채워준다.

           {

                     Card[i] = rand() % CARDSIZE;

           }

 

           printf("Random array\t :: ");

           printArray(Card, CARDSIZE);

 

           printf("Sort Complete\t :: ");

 

           MergeSort(Card, CARDSIZE, 0, CARDSIZE- 1);

           printArray(Card, CARDSIZE);

          

           printf("\n");

}

 

// * 인자설명*

// array : 배열의첫번째포인터

// size  : 배열의크기

// first : 배열의첫번재인덱스

// end    : 배열의마지막인덱스

voidMergeSort(int* array, intsize, intfirst, intend)

{

 

           intmid= (end+ first) / 2;  // Middle point 설정

           int*mergeArray;                           // 임시배열을위한포인터선언

                    

           inti, j;                                               // 반복문을위한변수선언

           intindexFirst= first;                      // 첫번째배열을위한인덱스

           intindexSecond= mid+ 1;    // 두번째배열을위한인덱스

           constintendFirst= mid;     // 첫번째배열의마지막인덱스

           constintendSecond= end;    // 두번째배열의마지막인덱스

          

 

           if(first< end)                

           {

                     // Middle Point 를기준으로나누어진첫번째배열과두번째배열의크기와인덱스를

                     // 인자값으로하여재귀호출해준다.

                     MergeSort(array, mid- first+ 1, first, mid);

                     MergeSort(array, end- mid, mid+ 1, end);     

                     // 임시배열의동적공간할당을해준다.

                     mergeArray= malloc(sizeof(int) * size);

 

 

                     for(i= 0; i< size;++i)

                     {

                                // 첫번째배열의값이작다면임시배열에넣어준다.

                                if( (indexFirst<= endFirst) && (array[indexFirst] < array[indexSecond]) )

                                {

                                          mergeArray[i] = array[indexFirst];

                                          ++indexFirst;

                                }

                                // 위에조건이맞지않다면두번째배열값을임시배열에넣어준다.

                                // 또는, 남은값들을복사해주는역활을한다.

                                elseif((indexSecond<= endSecond))

                                {

                                          mergeArray[i] = array[indexSecond];

                                          ++indexSecond;

                                }

                                elseif(indexFirst<= endFirst)

                                {

                                          mergeArray[i] = array[indexFirst];

                                          ++indexFirst;

                                }

                     }

 

                     // 임시배열을정렬하고자하는배열에복사한다.

                     for(i= first, j= 0; j< size; j++, i++)

                     {

                                array[i] = mergeArray[j];

                     }

                     // 임시배열해제

                     free(mergeArray);

           }

}

 

 

// 배열을출력한다.

// int* card : 배열의첫번째포인터

// int  size : 배열의사이즈

voidprintArray(int* card, intsize)

{

           inti;

           for(i= 0; i< size; i++)                   // 출력.

           {

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

           }

           printf("\n");

}