RadixSort

Radix.cpp

#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;

typedef int DataType;

void intToString( int n, string& s, int length );
void radixSort(string theArray[], int size, int length );
void swap( DataType& x, DataType& y );
void displayArray( const DataType theArray[], int first, int last );

const int N_ITEMS = 10;
const int length = 2;

int main()
{
   DataType a[ N_ITEMS ] = { 10, 5, 21, 5, 99, 8, 16, 4, 72, 25 };
   string s[ N_ITEMS ];

   cout << "Initial array : ";
   displayArray( a, 0, N_ITEMS - 1 );
   cout << endl;

   // Convert each element to string
   for ( int i = 0; i < N_ITEMS; i++ )
   {
      intToString( a[ i ], s[ i ], length );
   }

   radixSort( s, N_ITEMS, length );

   // Convert each elemnt to integer
   for ( int i = 0; i < N_ITEMS; i++ )
   {
      a[ i ] = atoi( s[ i ].c_str() );
   }

   cout << "Sorted array : ";
   displayArray( a, 0, N_ITEMS - 1 );
   cout << endl;

   return 0;
}


void radixSort(string theArray[], int size, int length)
{
   string tempArray[ 10 ][ N_ITEMS ];
   int endPoint[ 10 ];

   for ( int j = length - 1; j >= 0; j-- )
   {
      // Initialize tempArray to empty
      for( int i = 0; i < 10; i++ )
      {
	 for( int j = 0; j < size; j++ )
         {
            tempArray[ i ][ j ] = "";
         }
      }

      // Initialize all end points to 0
      for( int k = 0; k < 10; k++ )
      {
         endPoint[ k ] = 0;
      }


      for ( int index = 0; index < size; index++ )
      {
         // k = j-th digit of theArray[ index ]
         int k = ( theArray[ index ] )[ j ] - '0';

         // Place theArray[ index ] at the end of group k
         tempArray[ k ][ endPoint[ k ] ] = theArray[ index ];

         // Increment the end point of group k by 1
         endPoint[ k ] = endPoint[ k ] + 1;
      }


      // Replace the items in theArray with all the items
      // in group 0, followed by all the items in group 1,
      // and so on
      cout << "Grouped by digit " << j + 1 << "-th : ";

      int index = 0;
      for( int i = 0; i < 10; i++ )
      {
         for( int j = 0; j < endPoint[ i ]; j++ )
         {
            theArray[ index ] = tempArray[ i ][ j ];
            cout << theArray[ index ] << " ";
            index = index + 1;
         }
      }
      cout << endl;
   }

}

void intToString( int n, string& s, int length )
{
   for( int i = length; i > 0; i-- )
   {
      int divisor = 1;
      for ( int j = 1; j < i; j++ )
      {
	 divisor = divisor * 10;
      }
      int digit = n / divisor;
      int subtractPortion = digit * divisor;
      n = n - subtractPortion;
      s = s + static_cast<char>( '0' + digit );
   }
}

void swap(DataType& x, DataType& y)
{
   DataType temp = x;
   x = y;
   y = temp;
   cout << "Swapped " << x << " with " << y << " --->";
}


void displayArray( const DataType theArray[], int first, int last )
{
   for ( int i = first; i <= last; ++i )
   {
      cout << theArray[ i ] << " ";
   } }