I am working on sorting strings of integers with a radix sort. I am confusing myself on the code logic however.
I have a file with integers, one to a line, and padded so 1 would be 001. I want to read those integers as strings so I can later do a sort on the ith digit in each string. For example, if I have 001, 003, 115. I have want to try something like this.

``````//radix part, i<3  to count the 3 numbers in each integer string
for(i = 0; i<3; i++)
call to counting sort``````

First, if each integer string is compose of 3 numbers and I will be counting by each one, does the string need to be a double array? Example...

``intstring[]``

Now the way to get counting sort to work is the problem. I have a working counting sort that I just need to modify but I do not have the logic of the loops down. Any ideas. I will post my code shortly.

## All 4 Replies

When you say "strings of integers", what do you mean exactly?

I think (s)he means something like : `string Number = "001";` at OP: Why not convert every line to integer and then sort them as integers. You wouldn't need char-arrays and your sorting should be easier to code.

Niek

Ok, do not convert the integers to strings..got it. I keep the integers but will need a way to keep the relationship between the original integer and its modulus. How about something like this...

``number[i][mod];``

Where is the original number and [mod] will be where the modulus number is held. I will go ahead an post my code so you can see where I am at.

``````#include <cstdlib>
#include <iostream>
#include <fstream>

using namespace std;
const int arraysize = 8; //size of the array
void countingSort(int numbers[], int size_of_array);

int main()
{
int i;
ifstream in_file; //input file
int numbers[arraysize]; //the number of integers from the input file
char filename;

cout<<"Enter the name of the file you wish to open "<<endl;
cin>> filename;

in_file.open(filename); //open the input file

if(!in_file.is_open()) //if the input file does not open
{
cout<<"Could not open the file.  " << filename <<endl
<<"The program is now closing. \n";
exit(EXIT_FAILURE); //exit the program
}

while(in_file.good()) //if the input file opens
{
for(i = 0; i < arraysize; i++) //read all of the integers from the file..
{
in_file >> numbers[i]; //into the array numbers
}
}

for(i =0; i<arraysize; i++)
{
cout<<numbers[i]<<endl;
}

system("PAUSE");
return EXIT_SUCCESS;
}

void countingSort(int numbers[], int size_of_array)
{
// search for the minimum and maximum values in the input
int i;

//finding the ones place

int min = numbers;
int max = min;
for(i = 0; i < size_of_array; ++i)
{
if (numbers[i] < min)
min = numbers[i];
else if (numbers[i] > max)
max = numbers[i];
}

// create a counting array, counts, with a member for
// each possible discrete value in the input.
// initialize all counts to 0.
int distinct_elements = max - min + 1;

int* counts = new int[distinct_elements];

for(i=0; i<distinct_elements; ++i)
counts[i] = 0;

// accumulate the counts - the result is that counts will hold
// the offset into the sorted array for the value associated with that index
for(i=0; i < size_of_array; ++i)
++counts[numbers[i] - min];

// store the elements in the array
int j=0;
int counter = 0;
int z;
for(i=min; i<=max; i++)
for(z = 0; z<counts[i-min]; z++)
{
numbers[j++] = i;
counter = counter + 1;
}

delete[] counts;
cout<<"The number of times counting sort is run is " <<counter<<endl;
}

{
int p;
int i;
int temp_ones[arraysize], temp_tens[arraysize], temp_hundreds[arraysize];

//finding the ones place
for(int k=0; k < arraysize; k++)
{
temp[i] = n[i]%10;
}

for(int t1; t1 < arraysize; t1++)
{
if(n[t1]%10 == temp[t1])
//what now

int rcounter =0;
for( p=0; p < 3; p++ )
{
rcounter = rcounter + 1;
countingSort(n, A);
}
cout<<"The radix sort calls counting sort "<<rcounter<<" times."<<endl;
}``````

Here is the program with a bit of an update. The whole goal is to do a radix sort on the numbers from the file and then have counting sort do the partial sort based on the ones, tens, and hundreds place. The integers wont be totally/fully sorted until the hundreds place is done.

``````#include <cstdlib>
#include <iostream>
#include <fstream>

using namespace std;
const int arraysize = 8; //size of the array
void countingSort(int numbers[], int size_of_array);

int main()
{
int i;
ifstream in_file; //input file
int numbers[arraysize]; //the number of integers from the input file
char filename;

cout<<"Enter the name of the file you wish to open "<<endl;
cin>> filename;

in_file.open(filename); //open the input file

if(!in_file.is_open()) //if the input file does not open
{
cout<<"Could not open the file.  " << filename <<endl
<<"The program is now closing. \n";
exit(EXIT_FAILURE); //exit the program
}

while(in_file.good()) //if the input file opens
{
for(i = 0; i < arraysize; i++) //read all of the integers from the file..
{
in_file >> numbers[i]; //into the array numbers
}
}

radixSort(numbers, arraysize); //call to function, pass arguements of numbers and arraysize

/* for(i =0; i<arraysize; i++) //not needed yet
{
cout<<numbers[i]<<endl;
}*/

system("PAUSE");
return EXIT_SUCCESS;
}

void countingSort(int numbers[], int size_of_array)
{
// search for the minimum and maximum values in the input

//finding the ones place

int min = numbers; //set min equal to number in place 0,0
int max = min;

//the purpose of this loop is to find the min and max numbers
for(int i = 0; i < arraysize; i++)
for(int j = 0; j < 1; j++)
{
if (numbers[i][j] < min)
min = numbers[i][j];
else if (numbers[i][j] > max)
max = numbers[i][j];
}

// create a counting array, counts, with a member for
// each possible discrete value in the input.
// initialize all counts to 0.
int distinct_elements = max - min + 1;

int* counts = new int[distinct_elements];

for(int i=0; i<distinct_elements; ++i)
counts[i] = 0;

// accumulate the counts - the result is that counts will hold
// the offset into the sorted array for the value associated with that index
for(int i = 0; i < arraysize; i++)
for(int j=0; j < 1; j++)
++counts[numbers[j][i] - min];

// store the elements in the array
int j=0;
int counter = 0;
int z;
for(int i = min; i <= max; i++)
for(z = 0; z<counts[i-min]; z++)
{
numbers[j++][i] = i;
counter = counter + 1;
}

delete[] counts;
cout<<"The number of times counting sort is run is " <<counter<<endl;
}

{
int p;
int i;
int temp_ones[arraysize], temp_tens[arraysize], temp_hundreds[arraysize];

//finding the ones place. Or so I hope
for(int k=0; k < arraysize; k++)
for(int i =0; i < 1; i++)
temp_ones[k][i] = n[i]%10;

int rcounter = rcounter + 1;
countingSort(temp_ones[arraysize], A);
/*for(int t1; t1 < arraysize; t1++)
{
if(n[t1]%10 == temp[t1])
//what now

/* int rcounter =0;
for( p=0; p < 3; p++ )
{
rcounter = rcounter + 1;
countingSort(n, A);
} */
//cout<<"The radix sort calls counting sort "<<rcounter<<" times."<<endl;
}``````

I am getting one error at line 114:
114 C:\radix sort\main.cpp invalid conversion from `int' to `int (*)'
114 C:\radix sort\main.cpp initializing argument 1 of `void countingSort(int (*), int)'

I am not sure what they mean.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.