Search  

---

C:/temp/src/j2k/DataType/Link/dlistsort.cpp

Go to the documentation of this file.

// Contribution to J2K library by David
// Reviewed by Fred P.

#ifndef __J2K__STORAGE__DLIST_SORT_CPP__
#define __J2K__STORAGE__DLIST_SORT_CPP__

#include <j2k/DataType/Link/DList.hpp>

void DList::bubSort()
{
  for(int i=0;i < nbElements;i++)
  {
    curr = head;
    for( register int j = nbElements; j > i; j-- )  // iterate thru list, compare
    {                                                // each adjacent pair of elements
      if( curr->pNext->element < curr->element )    // swap elements if they are not 
        bubSwap(curr->pNext, curr);                 // in the correct relation
      curr = curr->pNext;
    }
  }
}

void DList::bubSwap( DLink* d1, DLink* d2 )
{
  DLink temp;
  temp.element = d1->element;
  d1->element = d2->element;
  d2->element = temp.element;
}

void DList::Sort()                                  // will call quicksort() initially
{
  if ( nbElements <= 1 ) return;
  quickSort(0,nbElements);
}

void DList::quickSort( int left, int right )
{
    register int i, j, a;                             // i,j are indexes to linked list   
    DLink* iLink = head;                              // iLink,jLink correspond i & j index 
    DLink* jLink = head;                              // vLink will determine how sublists 
    DLink* vLink = head;                              // are resized 
    DLink* lLink = head;
    DLink* rLink = head;                              // rLink,lLink refer to "new" head and 
                                                      // tail of sublist  
    if( right-left > 1 )                              // More than 2 elements
    {
        i = ( left + right ) / 2;                     // get pivot value

        // Find first element larger than pivot and last element not larger than pivot
        lLink = head;                                 // start at beginning,use index
        for( a = 0; a < left; a++ )  { lLink = lLink->pNext; }

        iLink = head;
        for( a = 0; a < i; a++ ) { iLink = iLink->pNext; }
      
        if ( iLink->element < lLink->element )        // compare and flip  
        quickSwap( i, left );
      
        rLink = head;
        for( a = 0; a < right; a++ ) { rLink = rLink->pNext; }
              
        if( rLink->element < lLink->element )         // compare and flip
        quickSwap( left, right );
      
        if( rLink->element < iLink->element )
        quickSwap( i, right );
            
        j = right - 1;                                // index of left,j in linked list,
        jLink=head;                                   // indicates first sublist
        for( a = 0; a < right - 1; a++ )  { jLink = jLink->pNext; }
        quickSwap( i, j );

        // index of i,right in linked list, contains second sublist
        i = left;
        iLink = head;
        for( a = 0; a <= left; a++ )
        {
          if ( i != 0 ) { iLink = iLink->pNext; }    // No need to do this for 1st element 
        }
      
        vLink = head;
        for( a = 0; a < j; a++ ) { vLink = vLink->pNext; }

        for(;;)
        {
            // check which sublist vLink->element belongs and adjust sublist
            iLink = iLink->pNext;
            i++;
            while( iLink->element < vLink->element)
            {
              iLink = iLink->pNext;
              i++;  
            }
        
            jLink = jLink->pPrev;
            j--;

            while( vLink->element < jLink->element )
            { 
              jLink = jLink->pPrev;
              j--;
            }
        
            if( j < i ) break;
            quickSwap( i, j );
        }
        quickSwap( i, right - 1 );
        quickSort( left, j );           // recursively sort each sublist
        quickSort( i + 1, right );
    } 
    else 
    {
      for( a = 0; a < left;  a++ ) { lLink = lLink->pNext; } // only 2 elements so check and flip
      for( a = 0; a < right; a++ ) { rLink = rLink->pNext; }
      if ( rLink->element < lLink->element )
      {
        quickSwap( left, right );
      }
    }
}

/////////////////////////////////////////////////////////////////
void DList::quickSwap( int left, int right )
{
  DLink* tempLeft  = head;
  DLink* tempRight = head;

  register int p = 0;
  for( p = 0; p < left; p++ )        // get left variable   
  {
    tempLeft = tempLeft->pNext;
  }

  for( p = 0; p < right; p++ )       // get right variable  
  {
    tempRight = tempRight->pNext;
  }
  
  DLink temp;
  temp.element       = tempRight->element;
  tempRight->element = tempLeft->element;        // flip
  tempLeft->element  = temp.element;
}

#endif

---