Feeds:
Posts
Comments

Archive for October, 2007

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 );
 }
 
}

Advertisements

Read Full Post »

In asp.net 2.0’s GridView  web control ,  you can convert  each column’s header part into customable one.  However ,  I find the little technic getting rare  discussion , for  most developers put attention to customization  of normal rows :  changing a BoundField into TemplateField ,  craming  item cell with dropdown list , button , etc by typing code in the blank of ItemTemplate .   The significance of controlling header template and style freely lies in that we can enhence the user experience when they are dealing with matters of sorting.  In most cases it is really tangent to the core business ,   however,  what if your client is a diehard of such case:  when cliking field header ,  he needs not only the perfect sorted result , but certain  obvious symbol to provide details  about current round of sorting: which cloumn is sorted just now and whether it sorts ascendingly or in  the  inverting  direction.   A good approach is adding a small arrow, which denotes current sort direction ,  before the header text of the field to be sorted.    However ,   neither default “HeaderText” property  nor “HeaderImageUrl”  leads to the goal.    We must get the ultimate control of header to make its appearance versatile!

Let’s follow these steps to reach the end:

 1.   Convert a BoundField , or any other kind of dotnet-built-in field into a TemplateField.     Only by using  this step  can  “HeaderTemplate” be accessed thus enabling us to customize the header part.   For example , if we have:

  <asp:BoundField DataField=”Name” HeaderText=”Name” SortExpression=”Name” />     

We convert it to format as shown below :

   <asp:TemplateField>
       <HeaderTemplate>


       </HeaderTemplate>
          <ItemTemplate>
                 <%# Eval(“Name”) %>
               </ItemTemplate>
       </asp:TemplateField>

  Let’s leave HeaderTemplate blank here for a moment.

 2.  Now we add a  LinkButton to simulate the default sorting field’s hyperlink with postback-javascript.   Add the button  strictly following the rules:

  1.   Set its   “CommandName”   as “Sort” 
  2.   Set its   “CommandArgument”   as corresponding value of “SortExpression”
  3.   Set its   “Text”  as  corresponding value of  “HeaderText”

By applying this 3 “golden rules” to the link button we will get a head appearance completely resambling  the auto-generated header for sorting.   Actually ,  the step 1 and 2 are two  necessary steps ,   step 3  is not so important  that you can replace with any equivalvent text.    Still adhering the sample , after “large step 2” we have:

 <asp:TemplateField>
       <HeaderTemplate>
       <asp:LinkButton runat=”server” Text=”Name” CommandName=”Sort” CommandArgument=”Name” ></asp:LinkButton> 
       </HeaderTemplate>
          <ItemTemplate>
                 <%# Eval(“Name”) %>
               </ItemTemplate>
         </asp:TemplateField>

 If we just stop here, the total workload  is meaningless :  amassing work to realize a no-need-to-develop  function   is unacceptable  to  anyone .   So we come to the start point of ornating a novelty : prefix an image control  to link button ,  acting as the holder of vertical  arrow symbol.   Then the page  syntax  becomes:

 <asp:TemplateField>
       <HeaderTemplate>
        <asp:Image id=”Name” Visible=”false”  runat=”server”  /><asp:LinkButton runat=”server” Text=”Name(CustomHeader)” CommandName=”Sort” CommandArgument=”Name” ></asp:LinkButton> 
       </HeaderTemplate>
          <ItemTemplate>
                 <%# Eval(“Name”) %>
               </ItemTemplate>
           </asp:TemplateField>

Note that such image control should be set invisible by default .  Even for each sorting-enabled field ,  there is no need to show any prompt symbol  if the user do not trigger its header link button.  The control’s visibility and  image url  will be manipulated programmably.  

What should do in  .aspx  context has been introduced.  Now we turn to backend code for seaming a  perfect function.   First we should register a method to gridview’s “RowDataBound” event,  then inject code.  Supposing the gridview’s ID is “gridView” ,   the code segment is as follows: 

    protected void gridView_RowDataBound(object sender, GridViewRowEventArgs e)
    {
         /*
        When the gridview is initialized , no sorting behavior happens,
        hence the SortExpression property is empty
        and the manipulation of arrow  should be skipped
        */

        if (e.Row.RowType == DataControlRowType.Header && gridView.SortExpression!=string.Empty )
        {
            /*
            Assign each arrow image control for its corresponding sorting field with
            the value of “sorting field name” , making it convinient to be found!
            */
            Image arrow = (Image) e.Row.FindControl( gridView.SortExpression );
            arrow.Visible = true;

            if (gridView.SortDirection == SortDirection.Ascending)
                arrow.ImageUrl = “arrowUp.gif”;
            else if (gridView.SortDirection == SortDirection.Descending)
                arrow.ImageUrl = “arrowDown.gif”;
        }

    }

Easy to understand ,  especially with my inline comment ……    Since bored with typing  so many words to exposit  such a simple skill  I  give up explaining  anymore about the backend code.    You can see  a  live sample here:

 sorting header with arrow

Read Full Post »