merge sort

알고리즘 문제를 풀때 (라이브러리 사용에 제약 이 있을 경우), 간단하게 quick sort로 해서 풀어 왔는데, 아래 막대기 문제는 quick sort 때문에 time out이 발생했다. quick sort는 Data Set에 따라서, 피벗 위치를 어디로 잡느냐에 따라서 최악의 경우가 발생할 수 있다. 그래서 이런 경우를 감안하면 merge sort를 활용해야 할듯 하다. Test Set 을 모르는 상태로, Time out을 당하지 않아야 하기 때문이다. merge sort는 아래 코드 처럼 data를 무조건 절반 분할하여 비교하기 때문에, Test Set의 종류에 무관하게 걸리는 시간은 똑같다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1897&sca=30a0

void msort(int s, int e)
{
 if (s >= e)return;
 int i,j, k, m;
 i = k = s;
 m = (s + e) / 2;
 j = m + 1;
 msort(s, m); //분할부터 한다.
 msort(j, e);

 /////////////분할이 완료 된 후 병합한다.//////////
 while (i <= m ||j <= e)
 {
  if (i > m || (j <= e && arr[j] > arr[i]))//sort조건
  {
   temp[k++] = arr[j++];
  }
  else
  {
   temp[k++] = arr[i++];
  }
 }
 
 ////////////임시 배열에 저장된 값을 복사한다//////////////////
 for (int i = s; i <= e; i++)
  arr[i] = temp[i];
}

알고리즘 문제를 풀때 템플릿 까지 쓸 일이 있을까 싶은데..위에 문제는 자료형 두개에 대해, 각각의 비교 함수로 sorting 해서 문제를 풀었다. 그래서 template으로 바꾸었다.

bool cmppoll(int i, int j) //막대기 비교
{
 if (arrPoll[i].t > arrPoll[j].t)
 {
  return true;
 }
 else if (arrPoll[i].t == arrPoll[j].t)
 {
  if (arrPoll[i].d > arrPoll[j].d)
  {
   return true;
  }
 }
 return false;
}
bool cmpmap(int a, int b) //map 비교 
{
 if (map[a] < map[b])
 {
  return false;
 }
 return true;
}

template <typename T >
void msort(int s, int e, T *arr, T *tmp, bool(cmp)(int, int))//s,e, 원본 배열, 임시 배열, 비교 함수(비교할 인덱스1,2)
{
 if (s >= e)return;

 int i, k, m, j;
 i = k = s;
 m = (s + e) / 2; 
 j = m + 1;
 msort(i, m, arr, tmp, cmp);
 msort(j, e, arr, tmp, cmp);

 while (i <= m || j <= e)
 {
  if (i > m || (j <= e && cmp(i, j)))
  {
   tmp[k++] = arr[j++];
  }
  else
  {
   tmp[k++] = arr[i++];
  }
 }

 for (int i = s; i <= e; i++)
  arr[i] = tmp[i];
}