Search  

---

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

Go to the documentation of this file.

#ifndef __J2K__Sort__QSort4_CPP__
#define __J2K__Sort__QSort4_CPP__

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

// Quicksort sort
           
#define QSTHRESHOLD  8                 // Suggested by MicroSoft !

void QuickSort( Elem* array, int Size ) 
{
  int i = 0;
  int j = Size - 1;
  int listsize = Size;

  struct QEntry Stack[100];

  int top = 0;
  int pivot;
  int pivotindex, l, r;

  Stack[top].Left  = i;
  Stack[top].Right = j;

  while ( top >= 0 ) 
  {
    // Pop Stack
    i = Stack[top].Left;
    j = Stack[top--].Right;

    // Findpivot
    pivotindex = (i+j)/2;
    pivot = array[pivotindex];         
    swap( array, pivotindex, j );      // Stick pivot at end

    // Partition
    l = i-1;
    r = j;

    do {
      while (       array[++l] < pivot );
      while (r  &&  array[--r] > pivot );

      swap(array, l, r);

    } while (l < r);

    swap(array, l, r);                 // Undo final swap
    swap(array, l, j);                 // Put pivot value in place

    // Load up Stack
    if ( (l-i) > QSTHRESHOLD )         // Left partition
    {
      Stack[++top].Left   = i;
      Stack[  top].Right  = l-1;
    }

    if ( (j-l) > QSTHRESHOLD )         // Right partition
    {
      Stack[++top].Left   = l+1;
      Stack[  top].Right  = j;
    }
  }

  InsertionSort( array, listsize );    // Final Insertion Sort
}

#endif // End of Qsort4.cpp

---