[Algorithm] Heap Sort

1. Heap Sort

int push(int n) {
   S[ HI++ ] = n;
   for( int k = HI - 1; k > 1; k /= 2 ) {
      if( S[ k/2 ] <= S[ k ] ) break;
      int temp = S[ k/2 ]; S[ k/2 ] = S[ k ]; S[ k ] = temp;
   }
}

int pop() {
   int v = S[ 1 ];
   S[ 1 ] = S[ --HI ];
   for( int k = 1; k*2 < HI; ) {
      int n = k*2;
      if( HI >= k*2 + 1 ) { n = S[ k*2 ] <= S[ k*2 + 1 ] ? k*2 : k*2 + 1; }
      if( S[ k ] <= S[ n ] ) break; 
      int temp = S[ n ]; S[ n ] = S[ k ]; S[ k ] = temp;
      k = n;
   }
   return v;
}

void heap_sort(int bb, int ee) {
   for( int i = bb; i <= ee; i++ ) push( A[ i ] );
   dump_heap();
   for( int i = bb; i <= ee; i++ ) A[ i ] = pop();
}

[Algorithm] Merge Sort (Iteration)

1. Merge Sort (Iteration)

void merge(int bb, int mm, int ee){
   int b = bb, k = bb, m = mm+1;
   while( b <= mm && m <= ee ) {
      if( A[ b ] <= A[ m ] ) S[ k++ ] = A[ b++ ];
      else                   S[ k++ ] = A[ m++ ];
   }
   if( b <= mm ) while( b <= mm ) S[ k++ ] = A[ b++ ];
   else          while( m <= ee ) S[ k++ ] = A[ m++ ];
   for( int i = bb; i <= ee; i++)
      A[ i ] = S[ i ];
}

void merge_sort(int bb, int ee) {
   #define min(a,b) ((a) < (b) ? (a) : (b))
   for( int k = 1; k <= ee; k *= 2 ) {
      for ( int i = bb; i <= ee; i += k*2 ) {
         merge(i, min(i+k-1, ee), min(i+k*2-1, ee));
      }
   }
}

[Algorithm] Merge Sort (Recursion)

1. Merge Sort (Recursion)

void merge(int bb, int mm, int ee){
   int b = bb, k = bb, m = mm+1;
   while( b <= mm && m <= ee ) {
      if( A[ b ] <= A[ m ] ) S[ k++ ] = A[ b++ ];
      else                   S[ k++ ] = A[ m++ ];
   }
   if( b <= mm ) while( b <= mm ) S[ k++ ] = A[ b++ ];
   else          while( m <= ee ) S[ k++ ] = A[ m++ ];
   for( int i = bb; i <= ee; i++)
      A[ i ] = S[ i ];
}

void merge_sort(int bb, int ee){
   if( bb < ee ) {
      int mm = (bb + ee) / 2;
      merge_sort( bb, mm ); 
      merge_sort( mm+1, ee ); 
      merge( bb, mm, ee );
   }
}

[Algorithm] Quick Sort

1. Quick Sort

void quick_sort(int bb, int ee) {
   if( bb < ee ) {
      int b = bb+1, e = ee, m = (bb+ee) / 2;;
      int temp = A[bb]; A[bb] = A[m]; A[m] = temp; 
      while( b <= e ) {
         while( b <= e && A[b] <= A[bb] ) b++;
         while( b <= e && A[bb] <= A[e] ) e--;
         if( b < e ) { temp = A[b]; A[b] = A[e]; A[e] = temp; b++, e--; }
      }
      temp = A[bb]; A[bb] = A[e]; A[e] = temp; 
      quick_sort( bb, e-1 );
      quick_sort( e+1, ee);
   }
}