Search  

---

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

Go to the documentation of this file.

#ifndef __J2K__Sort__CPP__
#define __J2K__Sort__CPP__

// Sort.cpp - Implementation of Slow Sort method algorithm such as:
//            Insertion Sort, Bubble Sort, Selection Sort, Shell Sort
//            Radix Sort, Heap Sort, Merge Sort only.

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

#define MSTHRESHOLD  0            // Declare the ThresHold for MergeSort

// Insertion Sort Algorithm
void InsertionSort( Elem* array, int n )
{
  // Insert i'th record on the top sorted part of the array
  for( register  int i = 1; i < n; i++ ) 
    for( register int j = i; 
          (j > 0) && ( array[j] < array[j-1] ); 
          j--  )
    {
      swap( array, j, j-1 );
    }
}

// Bubble Sort Algorithm
void BubbleSort( Elem* array, int n )
{
  n--;  // n-1 optimization

  // Bubble up i'th record
  for( register   int i = 0; i < n; i++ )
    for( register int j = n; j > i; j-- )
      if ( array[j] < array[j-1] )
      {
        swap( array, j, j-1 );
      }
}

// Selection Sort Algorithm
void SelectionSort( Elem* array, int n )
{
  n--;  // n-1 optimization

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

    swap( array, i, lowindex );
  }
}

// Modified version of Insertion Sort for varying increments
void InsertionSort( Elem* array, int n, int incr ) 
{
  for( register int i = incr; i < n; i += incr )
    for( register int j = i; 
          ( j >= incr ) && ( array[j] < array[j-incr] ); 
          j -= incr )
    {
      swap( array, j, j-incr );
    }
}

// Shell Sort Algorithm
void ShellSort( Elem* array, int n ) 
{
  for(   register int i = n / 2; i > 2; i /= 2 )   // For each increment
    for( register int j = 0;     j < i; j++ )      // Sort each sublist
    {
      InsertionSort( &array[j], n-j, i);
    }

  InsertionSort( array, n );
}

void MergeSort(Elem* array, int Size) 
{
  Elem* temp = new Elem[ Size ];
  MergeSort(array, temp, 0, Size-1);

  if ( temp != NULL ) 
  {
       delete[] temp;
  }
}

void MergeSort(Elem* array, Elem* temp, int left, int right) 
{
  register int i, j, k;
  register int mid = (left+right) / 2;

  if (left == right) return;

  if ( (mid-left) < MSTHRESHOLD ) 
  {
    SelectionSort( &array[left], mid-left);
  } 
  else 
  {
    MergeSort( array, temp, left, mid );   // MergeSort first half
  }

  if ( (right-mid-1) < MSTHRESHOLD ) 
  {
    SelectionSort( &array[mid+1], right-mid-1 );
  } 
  else 
  {
    MergeSort(array, temp, mid+1, right);  // MergeSort second half
  }

  // Do the merge operation.  First, copy 2 halves to temp.

  for( i = mid; i >= left; i--) 
  {
    temp[i] = array[i];
  }

  for( j = 1; j <= right-mid; j++) 
  {
    temp[ right - j + 1 ] = array[ j + mid ];
  }

  // Merge sublists back to array
  for( i = left, j = right, k = left; k <= right; k++) 
  {
     if ( temp[ i ] < temp[ j ] ) 
     {
       array[ k ] = temp[ i++ ];
     } 
     else 
     {
       array[ k ] = temp[ j-- ];
     }
  } 
}

void HeapSort( Elem* array, int Size )
{
  MaxHeap* heap = new MaxHeap( array, Size, Size );   // Build the maxheap

  for(int i = 0; i < Size; i++)     // Now sort by removing 
  {
    heap->removemax();               // The max value placed at end of heap
  }
  
  delete heap;
}

void RadixSort(Elem* array, long Size) 
{
  // Count[i] stores number of records in bin[i]

  Elem* count = new Elem[ Size ];
  Elem* A     = array;
  Elem* B     = new Elem[ Size ];

  register long n    = Size;
  register int  k    = 16 / BITS;
  register int  r    = POW2[ BITS ];

  register int  i    = 0;
  register int  j    = 0;
  register int  rtok = 1;

  for( i = 0, rtok = 1; i < k; i++, rtok *= r)    // For k digits
  {
    for( j = 0; j < r; j++)                       // Initialize count
    {
       count[ j ] = 0;
    }

    // Count the number of records for each bin on this pass
    for( j = 0; j < n; j++ ) 
    {
       count[ ( A[j] / rtok ) % r ]++;
    }

    // Index B: count[j] will be index for last slot of bin j.
    for( j = 1; j < r; j++ ) 
    {
       count[ j ] = count[ j - 1 ] + count[ j ];
    }

    // Put records into bins working from bottom of each bin.
    // Since bins fill from bottom, j counts downwards
    for( j = n-1; j >= 0; j-- ) 
     {
       B[ --count[ ( A[j] / rtok ) % r ] ] = A[j];
    }

    for( j = 0; j < n; j++ )    // Copy B back to A
    {
       A[ j ] = B[ j ];         
    }
  }

  if ( B != NULL ) 
  {
      delete[] B;
  }

  if ( count != NULL ) 
  {
      delete[] count;
  }
}

#endif // End of Sort.cpp

---