Search  

---

C:/temp/src/j2k/Test/Sort_Test.cpp

Go to the documentation of this file.

// Main.cpp - main program declaration.

#include <j2k/DataType/Const.hpp>
#include <j2k/DataType/Sort/Random.hpp>
#include <j2k/DataType/Sort/Sort.hpp>

void SelSort2( Elem* array1, Elem* array2, int n );

// If everything run correctly the program return 0
// else the program return the errorcode level 1
// to indicate that the datafile was not found
// in the current directory.

int main( void )
{
   ulong SIZE = (ulong)pow( 2, 15 );
   ulong MAX  = (ulong)pow( 2, 20 );

   int TEST = 150;
   int i = 0;

   printf("SIZE=[%7d]  ", SIZE );
   printf("MAX=[%7d] \n", MAX  );

   Random* r = new Random( SIZE, MAX  );

   char* SortName[9];

   SortName[0] = "InsertSort";
   SortName[1] = "BubbleSort";
   SortName[2] = "SelectionSort";
   SortName[3] = "ShellSort";
   SortName[4] = "Merge Sort";
   SortName[5] = "Heap Sort";
   SortName[6] = "Radix Sort";
   SortName[7] = "Quick Sort";
   SortName[8] = "Old Quick Sort";


   clock_t start, end;
   //  clock_t allstart, allend, alldelay;
   //  double  allsec;

   Elem  elapsed;
   Elem* delay = new Elem[9];
   Elem* Index = new Elem[9];

   for( i = 0; i < 9; i++ ) 
   {
      delay[i] = 0;
      Index[i] = i;
   }

   for( i = 0; i < 4; i++ )  delay[i] = 99999;

   
   for( i = 0; i < TEST; i++ ) 
   {
         allstart = clock();

         r->feed( false );
         // printf( "\nRandom Data:  \n");
         // r->Display();
  
         printf( "InsertSort:  ");

         start = clock();
         InsertionSort( r->getArray(), r->getSize() );
         end   = clock();
         elapsed = end - start;
         delay[0] += elapsed;
         printf( "\t\t%6d  clock ticks\n", elapsed );

         // r->Display();
         r->Restore();

         printf( "BubbleSort:  ");

         start = clock();
         BubbleSort( r->getArray(), r->getSize() );
         end   = clock();
         elapsed = end - start;
         delay[1] += elapsed;
         printf( "\t\t%6d  clock ticks\n", elapsed );

         // r->Display();
            r->Restore();

         printf( "SelectionSort:");

         start = clock();
         SelectionSort( r->getArray(), r->getSize() );
         end   = clock();
         elapsed = end - start;
         delay[2] += elapsed;
         printf( "\t\t%6d  clock ticks\n", elapsed );

       // r->Display();      
            r->Restore();

         printf( "ShellSort:  ");

         start = clock();
         ShellSort( r->getArray(), r->getSize() );
         end   = clock();
         elapsed = end - start;
         delay[3] += elapsed;
         printf( "\t\t%6d  clock ticks\n", elapsed );

         printf( "Merge Sort:  ");

         start = clock();
         MergeSort( r->getArray(), r->getSize() );
         end   = clock();
         elapsed = end - start;
         delay[4] += elapsed;
         printf( "\t\t%6d  clock ticks\n", elapsed );

       // r->Display();      
         r->Restore();
       
         printf( "Heap Sort:  ");

         start = clock();
         HeapSort( r->getArray(), r->getSize() );
         end   = clock();
         elapsed = end - start;
         delay[5] += elapsed;
         printf( "\t\t%6d  clock ticks\n", elapsed );


       // r->Display();      
         r->Restore();

         printf( "Radix Sort:  ");

         start = clock();
         RadixSort( r->getArray(), r->getSize() );
         end   = clock();
         elapsed = end - start;
         delay[6] += elapsed;
         printf( "\t\t%6d  clock ticks\n", elapsed );


            // r->Display();      
            r->Restore();

         printf( "Quick Sort:  ");

         start = clock();
         QuickSort( r->getArray(), r->getSize() );
         end   = clock();
         elapsed = end - start;
         delay[7] += elapsed;
         printf( "\t\t%6d  clock ticks\n", elapsed );


       // r->Display();      
            r->Restore();

         printf( "Old Quick Sort:");

         start = clock();
         OldQuickSort( r->getArray(), r->getSize() );
         end   = clock();
         elapsed = end - start;
         delay[8] += elapsed;
         printf( "\t\t%6d  clock ticks\n", elapsed );

       // r->Display();  
       
//     allend = clock();
//     alldelay = allend - allstart;
//     allsec = alldelay / CLOCKS_PER_SEC;
//     printf("\n It takes  %6d  clock ticks ");
//     printf("or %.2f to run it once.\n\n", alldelay, allsec );
   }

   delete r;

   SelSort2( delay, Index, 9 );

   double unit = delay[ 0 ];
   double t = 0;

   if ( unit < 1 ) { unit = 1; }
   
   for( i = 0; i < 9; i++ ) 
   {
     t = (double)delay[ i ] / unit;
     printf( "\nFor %s the average number of ", SortName[ Index[i] ] );
     printf( "clock ticks is \t %6d or %.2f time unit ", (delay[ i ] / TEST), t );
   }

   return 0;
}

// Selection Sort Algorithm
void SelSort2( Elem* array1, Elem* array2, int n )
{
  n--;  // n-1 optimization

  // Select i'th record
  for( register int i = 0; i < n; i++ ) 
  {
    int lowindex = i;                      // Remember its index
    for( register int j = n; j > i; j-- )  // Find the least value
    {
     if ( array1[j] < array1[lowindex] )
      {
         lowindex = j;                 // Put it in place
      }
    }

    swap( array1, i, lowindex );
    swap( array2, i, lowindex );
  }
}

---