Search  

---

C:/temp/src/j2k/DataType/Sort/OldQsort.cpp

Go to the documentation of this file.

#ifndef __J2K__Sort__OldQuickSort_CPP__
#define __J2K__Sort__OldQuickSort_CPP__

#include "Sort.hpp"

/* Goto Statement are used as a short and fast way
   to do recursion inside this sort algorithm.

   The difference might not seems to be significant
   in this version of C++, but in some other language or version
   where recursivity is not optimize by the compiler,
   this version show a significant improvement over the standard
   QuickSort by as much as 80x faster in Visual Basic 5.0 !
*/

void OldQuickSort( Elem* array, ulong Size )
{                                 
  struct QEntry QStack[100];        // Use to store variables for recursivity

  long Top = 0;                     // Top & Bottom ptr
  long Bottom = 0;

  long a = 0;                       // Inner Left & Right working ptr
  long b = Size-1;                       
 
  Elem z;                           // Temp location for swapping stuff
 
  QStack[0].Left  = a;              // Define the absolute left ptr 
  QStack[0].Right = b;              // Define the absolute right ptr

  long x = 1;                       // Normal Middle ptr

  while ( x > 0 )
  {
    x--;
    a = QStack[x].Left;             // Store Left and Right Stack value
    b = QStack[x].Right;

    z = array[a];                   // Give me some z value
   
    Top    = a;                     // Fix Top and Bottom range
    Bottom = b + 1;

QSBottom: // Address #1  -- Let's play with Bottom !

    Bottom--;

    if ( Bottom == Top ) goto QSz;  // If there is no middle than fix z

    if ( z <= array[Bottom] )       // If z is smaller than bottom-- and retry
    {    
      goto QSBottom;
    } 
    else 
    { 
      array[Top] = array[Bottom];
    }

QSTop:  // Address #2  -- Let's play with Top !

    Top++;

    if ( Bottom == Top) goto QSz;    // If there is no middle than fix z

    if ( z >= array[ Top ] )         // If z is bigger than top++ and retry
    {       
      goto QSTop;
    } 
    else 
    {
      array[ Bottom ] = array[ Top ];
      goto QSBottom;
    }

QSz:  // Address #3  -- Let's fix z and continue.
 
    array[Top] = z;

    if ( (b - Top) >= 2 )
    {
      QStack[x].Left  = Top + 1;
      QStack[x].Right = b;
      x++;
    }

    if ( (Bottom - a) >= 2 )
    {
      QStack[x].Left  = a;
      QStack[x].Right = Bottom - 1;
      x++;
    }
  }
}

// Take 20 value equally spread in the array and check for:
// - increasing ordered list, if so use InsertionSort,
// - decreasing ordered list, if so reverse and use InsertionSort,
// - Quite messy non-ordered list, than use OldQuickSort
void BrightQSort( Elem* array, ulong Size )
{
   ULONG* ptr = new ULONG[20];
   int   l = 0;
   int   r = 0;
   register int i = 0;
   ULONG k = 0;

   int   Trigger;

   Elem  T;

   int Test   = 20;
   int Test34 = Test * 3 / 4;     // 75% Ratio to be declare sorted

   int n  = Size / Test;
   int n2 = (int)floor(n / 2);

   for( i = 1; i <= Test; i++ )
   {
      ptr[i] = (ulong)floor( n * i );
   }

   for( i = 2; i <= Test; i++ )
   {
     T = array[ ptr[i] ] - array[ ptr[i - 1] - n2 ];

       if ( T < 0 )
       {
            l++;
       } 
       else 
       {
            r++;
       }

       printf( "[%d, %d, %d]", T, l, r );
   }

   printf( "[%d, %d, %d]", T, l, r );

   Trigger = r - l;

   printf( "%d", Trigger );


   if ( Trigger > Test34 )
   {
     printf( "INC" );
     InsertionSort( array, Size );
     return;
   }


   if ( Trigger < (-1 * Test34) )
   {
      printf("DEC");
  
      // Reverse the array
      for( k = 1; k <= ( Size / 2 + 1 ); k++ )
      {
         swap( array, k, Size - k + 1 );
      }

      for( k = 1; k <= Size; k++ )
      {
         printf("%d", array[k] );
      }

      InsertionSort( array, Size );
      return;
   }


   printf( "RND" );

   OldQuickSort( array, Size );

} // End of BrightQSort()

#endif // End of OldQSort.cpp

---