Code:
#include "stdafx.h"
// Based off orginal LabShell.cpp
// Which defined the entry point for the console application.
#define _TCHAR char
#include <fstream>
#include <iostream>
#include <ctime>
#include <vector>
//#include <cassert>
using namespace std;
void genData(int *, int);
int radixSort(int *, int);
long count = 0;
void genData(long *dta, int n)
{// generates social security numbers that do not contain zeroes
#define limit 1000000 // make this number whatever you want - we are just looking at a sample of the data to make sure it is correct
ofstream f;// open a file to write a sample of the output
//srand(time(0));
if(n < limit)
{
f.open("data.txt", ios::out);
if(!f.is_open())
{
cout << "SSN sample file did not open" << endl;
system("pause");
exit(0);
}
}
for(int i=0; i < n; i++)// generate the social security numbers at random
{
dta[i] = rand()%889 + 111 + 1000*(rand()%889 + 111) + 1000000*(rand()%889 + 111);
if(dta[i] > 999999999) dta[i] = dta[i] % 1000000000;
if(n < limit)f << i<< " " << dta[i] << endl;// write them out if in the sample you selected
}
if(f.is_open())f.close();// if the file is open, close it
}
void sort(long*, long*, long);
long* radixSort(long *dta, int n)
{
long* dest = new long[n];
sort(dta, dest, n);
return dest; // this is a dummy routine - you need to write your own that sorts the data and counts the operations
}
void print_data(const char* title, long* data, int count)
{
cout << "--------" << title << "--------" << endl;
for(int i=0; i<count; ++i)
{
cout << data[i] << endl;
}
}
// main program to run the radix sort graphing
int _tmain(int argc, _TCHAR* argv[])
{
long *data;// pointer to where SSNs will be stored
int N=2;// initial size of the SSN data set.
ofstream f;
f.open("output.csv", ios::out);// open the output excel file
if(f.is_open())// if it opened, proceed, else issue error and quit
{
for(int i = 0; i < 15; i++)
{// generate 15 sets of data the first of size 2, the next of size 4, until you get to 32768 (2 ^ 15)
data = new long [N];// allocate memory to hold the data generated by genData
if(data != NULL) // did we get the memory we requested?
{
genData(data, N);// generate the SSNs and out them in the array
print_data("unsorted", data, N);
long* dest = radixSort(data, N); // sort the data and count the operations
print_data("sorted", dest, N);
cout << "------\n";
f << N << "," << N << endl;// write the data pairs to the excel file for later graphing
cout << N << "," << N << endl;// write the data pairs to the screen also
N = 2 * N;// double the data size for the next pass
delete [] data;// free the data array because it will be reallocated next time
}
else
{// did not get the memory we asked for, issue error message and exit
cout << "Out of memory" << endl;
system("pause");// wait for user to see the message
break;
}
}
f.close();// close the file
}
else
{// file did not open, so alert user and exit
cout << "csv output file did not open" << endl;
system("pause");
}
system("pause");
return 0;
}
// the first parameter is the radix which is used to collect the numbers
// the second one is the number of data elements
// in is the array of data
// out is the result
void radix(int byte, long N, long *in, long* out)
{
//create buckets
vector<long> bucket[1000];
/*for(int x =0; x < 999; x++)
{
bucket[x][0] = 0;
for(int y = 0; y < 100; y++)
{
bucket[x][y]=0;
}
//memset (bucket, 0, sizeof (bucket[x]));
}
*/
//loop through the whole input set
for (int i = 0; i < N; i++)
{
if(in[i] < 0)
{
in[i] = in[i] * -1;
}
long temp = 0;
switch(byte)
{
case 0:
temp = in[i] % 1000;
break;
case 1:
temp = in[i] / 1000;
temp = temp % 1000;
break;
case 2:
temp = in[i] / 1000000;
}
//temp is now the index number for the bucket
//we need to find an empty place in the bucket
//int t = 0;
//while(bucket[temp]. != 0)
/*{
t++;
//cout << "temp= " << temp << "in= "<< in[i] << "I= " << i << "Bucket = " << bucket[temp][t] << endl;
}*/
//place number in bucket
bucket[temp].push_back(in[i]);
}
//get numbers from buckets, put in array
//currentI is the position on the out array
int currentI = 0;
for(i = 0; i< 1000; i++)
{
//t is the position in the bucket
int t = 0;
if(bucket[i].size() > 0)
{
for(int x = 0; bucket[i].size() > x ; x++)
{
out[currentI] = bucket[i].at(x);
currentI++;
//assert(currentI > (N + 1));
//cout << currentI;
}
}
}
if(currentI != N) cout << " N = " << N << " CurrentI = " << currentI << endl;
}
void sort(long *in, long *out, long count)
{
long *tmp = out;
out = new long [count];
// collect radices for each byte
radix(0, count, in, out);
in = out;
// create a new output list
out = new long [count];
//pass 2
radix(1, count, in, out);
in = out;
// use output list from calling function
out = tmp;
//pass 3
radix(2, count, in, out);
}
/*int main()
{
return _tmain(0, NULL);
}
*/
