test prog

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



#ifdef WIN32
#include <Windows.h>
#else
#include <sys/time.h>
#include <ctime>
#endif

/* Returns the amount of milliseconds elapsed since the UNIX epoch. Works on both
 * windows and linux. */

int GetTimeMs64()
{
#ifdef WIN32
 /* Windows */
 FILETIME ft;
 LARGE_INTEGER li;

 /* Get the amount of 100 nano seconds intervals elapsed since January 1, 1601 (UTC) and copy it
  * to a LARGE_INTEGER structure. */
 GetSystemTimeAsFileTime(&ft);
 li.LowPart = ft.dwLowDateTime;
 li.HighPart = ft.dwHighDateTime;

 uint64 ret = li.QuadPart;
 ret -= 116444736000000000LL; /* Convert from file time to UNIX epoch time. */
 ret /= 10000; /* From 100 nano seconds (10^-7) to 1 millisecond (10^-3) intervals */

 return ret;
#else
 /* Linux */
 struct timeval tv;

 gettimeofday(&tv, NULL);

 int ret = tv.tv_usec;
 /* Convert from micro seconds (10^-6) to milliseconds (10^-3) */
 ret /= 1000;

 /* Adds the seconds (10^0) after converting them to milliseconds (10^-3) */
 ret += (tv.tv_sec * 1000);

 return ret;
#endif
}



void radixsort(int array[], int size) {

//Set max equal to the greatest element of the array
int max = 0;
for (int i = 0; i < size; i++) {
   if (array[i] > max)
      max = array[i];
   }

for(int pow10=1; max != 0; max/=10, pow10*=10) {
   int buffer[size], bucket[10] = {0};


      //Calculate the bucket numbers
      for (int i = 0; i < size; i++)
         bucket[(array[i] / pow10) % 10]++;

      //Sum the bucket numbers
      for (int i = 1; i<10; i++)
         bucket[i] += bucket[i - 1];

      //Bucket sort the array into a buffer
      for  (int i = size - 1; i >= 0; i--)
         buffer[--bucket[(array[i] / pow10) % 10]] = array[i];

      //Move the sorted elements back into array
      for (int i = 0; i < size; i++)
         array[i] = buffer[i];
  }
}


void radixsort2(int array[], int size) {

//Set max equal to the greatest element of the array
int max = 0;
for (int i = 0; i < size; i++) {
   if (array[i] > max)
      max = array[i];
   }

for(int pow10=1; max != 0; max/=10, pow10*=10) {
   int buffer[size], blarg[size], bucket[10] = {0};

      //This might improve speed
      for (int i = 0; i < size; i++)
         blarg[i]=(array[i] / pow10) % 10;

      //Calculate the bucket numbers
      for (int i = 0; i < size; i++)
         bucket[blarg[i]]++;

      //Sum the bucket numbers
      for (int i = 1; i<10; i++)
         bucket[i] += bucket[i - 1];

      //Bucket sort the array into a buffer
      for  (int i = size - 1; i >= 0; i--)
         buffer[--bucket[blarg[i]]] = array[i];

      //Move the sorted elements back into array
      for (int i = 0; i < size; i++)
         array[i] = buffer[i];
  }
}

int main() {
const int size =100000;
int array[size];
int start, end;

srand ( time(NULL) );

start = GetTimeMs64();

for (int i=0; i<size; i++)
array[i]=rand();

radixsort(array, size);
end = GetTimeMs64();
cout << "radixsort took " << end-start << "ms" <<endl;

for (int i=0; i<size; i++)
array[i]=rand();

start = GetTimeMs64();
radixsort2(array, size);
end = GetTimeMs64();
cout << "radixsort2 took " << end-start << "ms" <<endl;
}