힙정렬(Heap Sort) - topdown, bottomup 두 방식 소스 작성과 비교 등등 해봄

생각보다 코딩 작업이 더디었다. 개념은 이해하기 쉬운 데
막상 코딩을 할려니 이것저것 세밀하게 따져야 하는 부분이 상당수 있어서 그런듯 하다...
시작과 끝 인덱스라든지, 노드 공식, 갯수 파악 등 신경써서 해야하는 부분이 많으므로 시간이 좀 오래 걸렸다.

일부 알고리즘 서적이나 강의에서 계산의 편의로 실제 인덱스에 +1을 하고 작성하는 경우가 있는 데(이재규 알고리즘 참조)
굳이 그렇게 하지 않고 그냥 작성했다. 충분히 직관적으로 쉽게 파악가능하고 어차피 나중에 실제 요소값 바꿀 때는
원래의 인덱스를 취해야 하므로 그렇다.


인트형 무작위 100만개를 입력해 테스트해보았는데
책에서 나오는대로 bottomup방식이 쬐금 더 빨랐다....;;;
퀵소트랑 비교해봣는데 역시 퀵소트한테는 못당한다.... median of three 방식도 아니었는데도
역시 괜히 퀵소트란 이름이 붙은게 아니다.
똑같이 NlogN이지만 퀵소트는 큰것 작은 것 두개만 교환하면 되는데(최상일때 NlogN , 최악일땐 N^2지만...)
힙정렬의 경우에는 아무래도 값비교횟수가 두배로 많고 지정횟수도 퀵정렬에 비해 많다.


복잡도  다큐먼트 매뉴얼를 둘러보니 퀵정렬의 경우 평균 1.38NlogN 비교횟수, 0.69NlogN 지정횟수를 가진다.
(좌우로 이동하면서 빠른 것과 작은 것만 찾으면 된다. 교환 역시 그 두 값과 나중에 피벗만 교환하면 된다.)
힙정렬의 경우는 보통 비교횟수는 2NogN에 좀 못미치는 정도이고 지정횟수는 평균 NlogN 수치를 가진다.
(Extract하고 DownHeap과정에서 부모,  좌측자식, 우측자식 3값을 비교해야 되니 2번 비교해야 되고,
그만큼 값 교환도 일어날 것이다.)


STL에서 non stable 버전 정렬로 인트로 소트를 채택하고 있는데 이 정렬방식이
퀵소트를 기반으로 재귀깊이가 일정이상 깊어지면 힙정렬을 사용하니(참고로 아주 작은 단위가 된 경우는 삽입 정렬 사용)
일단 소스를 작성해 볼 필요가 있다.


//--------------- 힙정렬 소스 ---------------


// 부모노드 공식: 0-無, 1-0, 2-0, 3-1, 4-1 ,,, parent=(child-1)/2 (0만 예외)
// 자식노드 공식: 0-1,2  /  1-3,4  /  2-4,5 ,,, leftchild=2*parent+1, rightchild=2*parent+2
// 외부노드(LeafNode) 시작 인덱스: (총 갯수 n)/2;  1개인 경우 0,,, 2개인 경우 1,,, 3개인 경우  1
template <typename T> void __stdcall HeapSortTopDown(T *arr, int n)
{
 T val;
 int i, cur, leafstart, child;

 if(n<2) return;

 // 가장 큰 값이 root에 위치하는 힙 형태로 만든다. 길이를 하나씩 증가시킨다.
 for(i=1 ; i<n ; i++){
  // 노드 추가 후 UpHeap ,,, 삽입정렬처럼 일괄적으로 땡기고 넣는다. 그때그때 교환은 낭비.
  cur=i;
  val=arr[cur];
  while(val>arr[(cur-1)>>1]){  // 부모노드와 값 비교해서
   arr[cur]=arr[(cur-1)>>1];
   cur=((cur-1)>>1);
   if(!cur) break; // 새로운 노드(부모)가 인덱스 0이면 루프 탈출
  }
  arr[cur] = val;
 }

 // 이제 추출(extract or remove): 루트값 추출후 길이 감소 및 DownHeap 처리
 // DownHeap시 오버헤드를 줄이기 위해 삽입정렬처럼 일괄적으로 땡기고 넣는다.
 while(n>1){
  val=arr[0];  // 마지막 노드와 루트 노드 교환
  arr[0]=arr[n-1];
  arr[n-1]=val;

  --n; // 힙의 길이를 하나 줄인다.
  cur=0; // 현재 비교 인덱스
  leafstart=(n>>1); // 외부노드(Leaf Node)의 첫 인덱스 공식
  val=arr[0];
  while(cur<leafstart){ // 내부노드이면(외부 첫 인덱스보다 작으면)
   child=(cur<<1)+1; // 내부노드이면 필연적으로 left child는 존재한다. 즉 right child와 달리 if문으로 내부 요소인지 파악할 필요 없다.
   if(child+1<n && arr[child+1]>arr[child]) ++child; // 오른쪽 차일드가 있는 경우 비교
   if(val >=arr[child]) break;
   arr[cur]=arr[child]; cur=child; 
  }
  arr[cur]=val;
 }
}

 

// 부모노드 공식: 0-無, 1-0, 2-0, 3-1, 4-1 ,,, parent=(child-1)/2 (0만 예외)
// 자식노드 공식: 0-1,2  /  1-3,4  /  2-4,5 ,,, leftchild=2*parent+1, rightchild=2*parent+2
// 외부노드(LeafNode) 시작 인덱스: (총 갯수 n)/2;  1개인 경우 0,,, 2개인 경우 1,,, 3개인 경우  1
template <typename T> void __stdcall HeapSortBottomUp(T *arr, int n)
{
 T val;
 int i, cur, leafstart, child;

 if(n<2) return;
  

 // 기존의 전체 배열을 힙으로 인식하되 정렬을 해준다.
 // 마지막 내부노드를 찾아서 역순으로 차근차근 다운힙을 통해 정렬한다.
 leafstart=(n>>1);    // 외부노드(Leaf Node)의 첫 인덱스 공식
 for(i=(n>>1)-1 ; i>=0 ; i--){ // 내부노드 가장 끝 인덱스는  n/2-1;
  cur=i;      // 현재 비교 인덱스
  val=arr[cur];
  do {      // 첫 실행은 반드시 내부노드가 있으므로 do~while문으로 구성한다.
   child=(cur<<1)+1;  // 내부노드이면 필연적으로 left child는 존재한다. 즉 right child와 달리 if문으로 내부 요소인지 파악할 필요 없다.
   if(child+1<n && arr[child+1]>arr[child]) ++child; // 오른쪽 차일드가 있는 경우 비교
   if(val>=arr[child]) break;
   arr[cur]=arr[child]; cur=child; 
  } while(cur<leafstart);
  arr[cur]=val;
 }

 // 이제 추출(extract or remove): 루트값 추출후 길이 감소 및 DownHeap 처리
 // DownHeap시 오버헤드를 줄이기 위해 삽입정렬처럼 일괄적으로 땡기고 넣는다.
 while(n>1){
  val=arr[0];  // 마지막 노드와 루트 노드 교환
  arr[0]=arr[n-1];
  arr[n-1]=val;

  --n; // 힙의 길이를 하나 줄인다.
  cur=0; // 현재 비교 인덱스
  leafstart=(n>>1); // 외부노드(Leaf Node)의 첫 인덱스 공식
  val=arr[0];
  while(cur<leafstart){ // 내부노드이면(외부 첫 인덱스보다 작으면)
   child=(cur<<1)+1; // 내부노드이면 필연적으로 left child는 존재한다.
   if(child+1<n && arr[child+1]>arr[child]) ++child; // 오른쪽 차일드가 있는 경우 비교
   if(val>=arr[child]) break;
   arr[cur]=arr[child]; cur=child; 
  }
  arr[cur]=val;
 }
}