Link to home
Start Free TrialLog in
Avatar of NeoMind
NeoMind

asked on

Bubble Sort.

Hi,
   I have  a linked list and I would like to know how we make a bubble sort.

Please help
ASKER CERTIFIED SOLUTION
Avatar of zfact
zfact

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
I wrote this class CSort to make any collection class sortable:


class CSort
{
public:
     CSort() {}
     ~CSort(){}
   
   void      BubbleSort( int nElem );

   virtual BOOL      Is1LowerThan2( int n1, int n2 ) = 0;
   virtual void      Exchange( int i, int j ) = 0;
}

void CSort::BubbleSort( int nN )
{
   for (int nI=0; nI<nN-1; nI++)
   {
      BOOL bOneAtLeast = FALSE;
      for (int nK=0; nK<nN-1-nI; nK++)
      {
         if ( Is1LowerThan2( nK+1, nK ))
         {
            Exchange( nK, nK+1 );
            bOneAtLeast = TRUE;
         }
      }
     
      if( !bOneAtLeast )
         return;
   }
}

You must derive your List class from CSort and then call BubbleSort();

This is an example of a sortable array:

class CSortWordArray :     public CWordArray,
                                        public CSort
{
public:
   virtual BOOL      Is1LowerThan2( int n1, int n2 )               { return GetAt( n1 ) < GetAt( n2 ); }
   virtual void      Exchange( int i, int j )     { WORD w = GetAt(i); SetAt( i, GetAt(j) ); SetAt( j, w ); }
};

...
CSortWordArray array;
array.Add( 10 );
array.Add( 2 );
array.Add( 3 );
array.BubbleSort( array.GetSize() );
...