All Shorting Techniques

 
Save this code as sort.hpp 

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

#ifndef __J2K__SORT_HPP__
#define __J2K__SORT_HPP__    // To avoid multiple declaration of a class

#include "Const.hpp"
#include "MaxHeap.hpp"

static long POW2[17] = {   1,    2,     4,     8,    16,   
                                32,    64,   128,   256,  
                               512,  1024,  2048,  4096, 
                              8192, 16384, 32768, 65536  };

#define BITS  6

void InsertionSort(  Elem* array, int n  );
void BubbleSort(     Elem* array, int n  );
void SelectionSort(  Elem* array, int n  );
void ShellSort(      Elem* array, int n  );
void InsertionSort(  Elem* array, int n, int incr );

void MergeSort(Elem* array, int Size);
void HeapSort( Elem* array, int Size );
void RadixSort(Elem* array, long Size);

void QuickSort( Elem* array, int Size );
void BrightQSort(  Elem* array, ulong Size );
void OldQuickSort( Elem* array, ulong Size );

void MergeSort(Elem* array, Elem* temp, int left, int right);

struct QEntry {
   long Left;
   long Right;
};

// Swap longents: A[i] <==> A[j]
inline void swap( Elem* A, int i, int j ) 
{
  Elem temp = A[i];
  A[i] = A[j];
  A[j] = temp;
}

#endif

Source Code of the file for sorting

// 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 "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 (int i = 1; i < n; i++)
    for (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 (int i = 0; i < n; i++)
    for (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 (int i = 0; i < n; i++) 
  {
    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 (int i = incr; i < n; i += incr)
    for (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 (int i = n / 2; i > 2; i /= 2)   // For each increment
    for (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) {
  int i, j, k;
  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* H = new MaxHeap( array, Size, Size );   // Build the maxheap

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

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 ];
  long  n = Size;
  int   k = 16 / BITS;
  int   r = POW2[BITS];

  int i = 0;
  int j = 0;
  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;
  }
}