Algorithm Alley
by Steven Pigeon


Listing One
#include <stdlib.h>
#include <stdio.h>
template <typename T> void swap(T & a, T & b) { T t=a; a=b; b=t; }
///////////////////////////////////////
int rank(int i) { return i % 13; }
int suit(int i) { return i / 13; }

///////////////////////////////////////
void SortDeck(int deck[52])
 {
  int rank_stack_ptr[13];
  int suit_stack_ptr[4];
  int rank_stack[13][4];
  int suit_stack[4][13];
  // hash by rank
  for (int r=0; r<13; r++) rank_stack_ptr[r]=0;
  for (int i=0; i<52; i++)
   {
    int r = rank( deck[i] );
    rank_stack[ r ][ rank_stack_ptr[r]++ ] = deck[i];
   }
  // hash by suite
  for (int s=0; s<4; s++) suit_stack_ptr[s]=0;
  for (int i=0; i<13; i++)
   for (int j=0; j<4; j++)
    {
     int s = suit( rank_stack[i][j] );
     suit_stack[ s ] [ suit_stack_ptr[s]++] = rank_stack[i][j];
    }
  // copy cards backs into the deck
  for (int d=0, i=0; i<4; i++)
   for (int j=0; j<13; j++, d++)
    deck[d] = suit_stack[i][j];
  // here, deck is sorted
 }
///////////////////////////////////////
void main()
 {
  int deck[52];
  for (int i=0;i<52;i++) deck[i]=i;
  for (int i=0;i<1000;i++)
   swap(deck[rand() % 52], deck[rand() % 52]);
  SortDeck(deck);
 }


Listing Two
void DistributionSort4(int tas[], int l, int h, int logMax)
 {
  int head[16];
  int *stack = new int[h-l];
  int *pred  = new int[h-l];
  for (int offset=0, i=0; offset < logMax; i++, offset+=4)
   {
    for (int j=0;j<16;j++) head[j]=-1;

    for (int d=0,j=l;j<h;j++,d++)
     {
      int s = (tas[j] >> offset) & 0xf;
      stack[d]=tas[j];
      pred[j]=head[s];
      head[s]=d;
     }
    for (int k=h-1, j=15; j>=0; j--)
     while (head[j]!=-1)
      {
       tas[k]=stack[head[j]];
       head[j]=pred[head[j]];
       k--;
      }
   }
  delete[] stack;
  delete[] pred;
 }





2

