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[][3]

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.

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);
void radixSort(int n[], int A);

int main()
{
    int i;
    ifstream in_file; //input file
    int numbers[arraysize]; //the number of integers from the input file
    char filename[50];
    
    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);
  
 
 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[0];
  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;
}

void radixSort(int n[], int A)
{ 
   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[][1], int size_of_array);
void radixSort(int n[], int A);

int main()
{
    int i;
    ifstream in_file; //input file
    int numbers[arraysize]; //the number of integers from the input file
    char filename[50];
    
    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[][1], int size_of_array)
{
  // search for the minimum and maximum values in the input
   
  
  
  //finding the ones place
  
  int min = numbers[0][0]; //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;
}

void radixSort(int n[], int A)
{ 
   int p;
   int i; 
   int temp_ones[arraysize][1], temp_tens[arraysize][1], temp_hundreds[arraysize][1];
   
   //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][1], 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 (*)[1]'
114 C:\radix sort\main.cpp initializing argument 1 of `void countingSort(int (*)[1], 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.