C++로 짠 합병정렬 소스 (설명은 주석으로 대체) C++

합병정렬은 정렬되지 않은 수의 리스트 공간을 이분할 하여서 부분적으로 정렬하여 나중에 합치는 방식으로 정렬한다.
최소 비교 가능 크기 2 (비교시 피연산자 2개가 필요하니깐)가 될 때까지 계속 분할한다. 분할된 리스트 크기가
최소 비교 가능 크기로 도달 하였을 경우 정렬을 한다. 이 때에 리스트를 반반 나누어서 정렬하여 해당 리스트를 갱신하면서
다시 공간을 합병하면서 원래 크기가 될때까지 계속 정렬을 해준다.

이러한 정렬방식으로 인하여서 코드로 표현하였을 경우 재귀적으로 소스코드를 구성하는게 편리하다.
재귀의 종단점은 최소 비교 가능 크기가 되었을 경우로 둔다.

아래 소스는 C++로 표현하였고, 데이터는 배열에 저장되어있다.


#include <iostream>

#define LEN_ARRAY(list) (sizeof(list)/sizeof(int) - 1)


using namespace std;


static int cnt=0;

void print(int *list,int len)
{

 for(int i=0; i<=len; i++)
 {
  cout<<list[i]<<' ';
 }
 cout<<endl;
}

void print(int *list, int low, int high)
{
 for(int i = low; i<= high; i++)
 {
  cout<<list[i]<<' ';
 }
 cout<<endl;
}
int sort(int *list,int low, int high)
{

 int i = low;
 int pos = low;
 
 int mid = (low + high) / 2;
 int j = mid + 1;
 int *tempList = (int *)malloc(sizeof(int) * (high + 1));
 
 //cout<<"sort 진행 low : "<<low<<"mid :"<<mid<<"high :"<<high<<endl;
 while(i <= mid && j <= high)
 {
  if(list[i] > list[j])
  {
   tempList[pos] = list[j];
   j++;
   pos++;
  }
  else
  {
   tempList[pos] = list[i];
   i++;
   pos++;
  }
 }
 // i가 먼저 도달 하였을 경우
 if( i > low)
 {
  //cout<<"좌측 공간이 먼저 정렬 됬음"<<endl;
  while(j <= high)
  {
   tempList[pos] = list[j];
   pos++;
   j++;
  }
 }
 // j가 먼저 도달 하였을 경우
 if( j > high)
 {
  //cout<<"우측 공간이 먼저 정렬 됬음"<<endl;
  while(i <= mid)
  {
   tempList[pos] = list[i];
   pos++;
   i++;
  }
 }
 memcpy(list+low,tempList+low,sizeof(int) * (high - low + 1 ));
 //cout<<"list : ";print(list,low,high);
 free(tempList);
 //cout<<"tempList : ";print(tempList,low,high);
 return 1;
}
//두개로 분할
int mergeSort(int *list, int low, int high)
{
 int mid = (low + high) / 2 ;
 cnt++;
 print(list,low,high);
 if(low < mid)
 {
  //좌측분할
  mergeSort(list,low,mid);
  //우측분할
  mergeSort(list,mid+1,high);
  //정렬하기
  sort(list,low,high);
 }
 //재귀종단점
 else
 {
      //cout<<"재귀 종단점 도달"<<endl;
      //print(list,low,high);
      sort(list,low,high); 
 }
     return 1;
}

//병합


int main()
{

     //int list[]={9,8,1,6,2,1,5,32,-1,950,2323,21,3,4,-50,1,66,7};
     int list[] = {4,3,2,1,5,6,7,-1};
     cout<<"정렬하기전 리스트 출력"<<endl;
     print(list,LEN_ARRAY(list)); 
     cout<<"정렬하고 난 후의 리스트 출력 "<<endl;
     mergeSort(list,0,LEN_ARRAY(list));
     print(list,LEN_ARRAY(list));
     cout<<"분할횟수  : "<<cnt - 1<<endl;
     return 0;
}


덧글

댓글 입력 영역