Feeds:
Posts
Comments

Posts Tagged ‘algorithm’

Heap Sort

Very very ridiculously ,  I some days ago threw an ariticle about an “enhenced version of heap sort”, which after a scrupulous review betrayed a silly implementation of sorting that can’t be farther from the truth of heap sort, due to damn unawareness of my mistake until scrutinizing some source code interspersed throughout  the web.   Any way, I could’nt hold my own overreached improvement , but rewrite it in the classical manner.  As though failing in an innovaton ,  I still insist on pubishing my rectified code.   

It is an introspection.

 Against my original thougt of stupor ,  heap sort is not so awlful that each time the part to be adjusted shall be adjusted from node of last node’s parent to the top node sequentially!  Since we should use such method to initial the whole target array as a strict heap,  after this only adjustment of root note is required ,  if neccessary ( that’s why in classical algorithm  use a max heap as the ADT to support an ascending order of array , which amazed me at first !  ) .      

/*
using strategy of “filtering through the direction from up to down” to adjust a heap starting at heapStart position
*/

void filterDown(  int *heap ,   int start  ,  int heapEnd )

 int  leftChild , rightChild , leftChildVal , rightChildVal , current , startVal , targetChild ;
  // value of the “start” position , which should be compared down its branch nodes
    startVal = *( heap + start );
    current = start;

    /* firstly test current’s children state.
    if current node’s left child ‘s index exceeds the heap’s upper bound,
    which means that it has no child ,
    then there is no need to filter down from current node   */
    for(  leftChild = current * 2 + 1;
       leftChild <= heapEnd;
     *( heap + current ) = * ( heap + targetChild ),
     current = targetChild,
     leftChild = current * 2 + 1  )
    {
  
     // judge who is the winner to compare with the target start value
     // if left child doesn’t meat the end
     if( leftChild < heapEnd )  
     {
       
        rightChild = leftChild + 1;
     leftChildVal =  * ( heap + leftChild );
     rightChildVal = * ( heap + rightChild );
     targetChild = leftChildVal >= rightChildVal ? leftChild : rightChild;  
  
     }
     else
      targetChild = leftChild;
   if( startVal >= * ( heap + targetChild )  )
    break;

    }

    /*  when startValue meets its “just” position, note that all nodes alongside this   critical  comparation path have  leveled up by one step, so current blank position is expected to fill “startValue”   */
    *( heap + current ) = startVal;
}

void Swap( int *a , int *b )
{
 int temp = *a;
 *a = *b;
 *b = temp;
}

// main funtion
void heap_sort( int *arr , int length )
{
 // current array length for each iteration
 int i ,
  curHeapEnd = length-1 ,
  from = ( length – 1 ) / 2;
 // build the whole array as a heap
 for ( i=from;i>=0;i– )
  filterDown( arr , i ,  curHeapEnd );
    for( i=curHeapEnd;i>0;i– )
 {   
  Swap( arr , arr + curHeapEnd );
  filterDown( arr, 0 , –curHeapEnd );
 }
 
}

Read Full Post »