radix with strings of integers

Please support our C++ advertiser: Programming Forums - DaniWeb Sister Site
Thread Solved

•
•
Join Date: Feb 2008
Posts: 43
Reputation: demroth is an unknown quantity at this point 
Solved Threads: 0
demroth demroth is offline Offline
Light Poster

radix with strings of integers

 
0
  #1
Apr 3rd, 2008
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.

C++ Syntax (Toggle Plain Text) 
  1. //radix part, i<3  to count the 3 numbers in each integer string
  2. for(i = 0; i<3; i++)
  3.   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...

C++ Syntax (Toggle Plain Text) 
  1. 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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2004
Posts: 7,867
Reputation: Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute 
Solved Threads: 755
Team Colleague
Narue's Avatar
Narue Narue is offline Offline
Senior Bitch

Re: radix with strings of integers

 
0
  #2
Apr 3rd, 2008
When you say "strings of integers", what do you mean exactly?
New members chased away this month: 5
Reply With Quote Quick reply to this message  
•
•
Join Date: Oct 2006
Posts: 2,996
Reputation: niek_e has a reputation beyond repute niek_e has a reputation beyond repute niek_e has a reputation beyond repute niek_e has a reputation beyond repute niek_e has a reputation beyond repute niek_e has a reputation beyond repute niek_e has a reputation beyond repute niek_e has a reputation beyond repute niek_e has a reputation beyond repute niek_e has a reputation beyond repute niek_e has a reputation beyond repute 
Solved Threads: 308
Moderator
Featured Poster
niek_e's Avatar
niek_e niek_e is online now Online
Cenosillicaphobiac

Re: radix with strings of integers

 
0
  #3
Apr 3rd, 2008
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
Last edited by niek_e; Apr 3rd, 2008 at 9:58 am.
Reply With Quote Quick reply to this message  
•
•
Join Date: Feb 2008
Posts: 43
Reputation: demroth is an unknown quantity at this point 
Solved Threads: 0
demroth demroth is offline Offline
Light Poster

Re: radix with strings of integers

 
0
  #4
Apr 3rd, 2008
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...

C++ Syntax (Toggle Plain Text) 
  1. number[i][mod];

Where [i] 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.

C++ Syntax (Toggle Plain Text) 
  1. #include <cstdlib>
  2. #include <iostream>
  3. #include <fstream>
  4.  
  5.  
  6. using namespace std;
  7. const int arraysize = 8; //size of the array
  8. void countingSort(int numbers[], int size_of_array);
  9. void radixSort(int n[], int A);
  10.  
  11. int main()
  12. {
  13.     int i;
  14.     ifstream in_file; //input file
  15.     int numbers[arraysize]; //the number of integers from the input file
  16.     char filename[50];
  17.  
  18.     cout<<"Enter the name of the file you wish to open "<<endl;
  19.     cin>> filename;
  20.  
  21.     in_file.open(filename); //open the input file
  22.  
  23.     if(!in_file.is_open()) //if the input file does not open
  24.     {
  25.       cout<<"Could not open the file.  " << filename <<endl
  26.           <<"The program is now closing. \n";
  27.            exit(EXIT_FAILURE); //exit the program
  28.     }
  29.  
  30.     while(in_file.good()) //if the input file opens
  31.     {
  32.       for(i = 0; i < arraysize; i++) //read all of the integers from the file..
  33.       {
  34.         in_file >> numbers[i]; //into the array numbers
  35.       }
  36.     }
  37.  
  38.   radixSort(numbers, arraysize);
  39.  
  40.  
  41.  for(i =0; i<arraysize; i++)
  42.  {
  43.        cout<<numbers[i]<<endl;
  44.  }
  45.  
  46.   system("PAUSE");
  47.   return EXIT_SUCCESS;  
  48. }
  49.  
  50. void countingSort(int numbers[], int size_of_array)
  51. {
  52.   // search for the minimum and maximum values in the input
  53.   int i; 
  54.  
  55.  
  56.   //finding the ones place
  57.  
  58.   int min = numbers[0];
  59.   int max = min;
  60.   for(i = 0; i < size_of_array; ++i)
  61.   {
  62.    if (numbers[i] < min)
  63.       min = numbers[i];
  64.     else if (numbers[i] > max)
  65.         max = numbers[i];
  66.   }
  67.  
  68.   // create a counting array, counts, with a member for 
  69.   // each possible discrete value in the input.  
  70.   // initialize all counts to 0.
  71.   int distinct_elements = max - min + 1;
  72.  
  73.   int* counts = new int[distinct_elements];
  74.  
  75.   for(i=0; i<distinct_elements; ++i)
  76.      counts[i] = 0;
  77.  
  78.   // accumulate the counts - the result is that counts will hold
  79.   // the offset into the sorted array for the value associated with that index
  80.   for(i=0; i < size_of_array; ++i)
  81.      ++counts[numbers[i] - min];
  82.  
  83.   // store the elements in the array
  84.   int j=0;
  85.   int counter = 0;
  86.   int z;
  87.   for(i=min; i<=max; i++)
  88.     for(z = 0; z<counts[i-min]; z++)
  89.      {
  90.       numbers[j++] = i;
  91.       counter = counter + 1;
  92.      }
  93.  
  94.   delete[] counts;
  95.   cout<<"The number of times counting sort is run is " <<counter<<endl;
  96. }
  97.  
  98. void radixSort(int n[], int A)
  99. { 
  100.    int p;
  101.    int i;
  102.    int temp_ones[arraysize], temp_tens[arraysize], temp_hundreds[arraysize];
  103.  
  104.    //finding the ones place
  105.    for(int k=0; k < arraysize; k++)
  106.    {
  107.      temp[i] = n[i]%10;
  108.    }
  109.  
  110.    for(int t1; t1 < arraysize; t1++)
  111.    {
  112.      if(n[t1]%10 == temp[t1])
  113.      //what now
  114.  
  115.  
  116.    int rcounter =0;
  117.    for( p=0; p < 3; p++ )
  118.    {
  119.       rcounter = rcounter + 1;
  120.       countingSort(n, A);
  121.    }
  122.  cout<<"The radix sort calls counting sort "<<rcounter<<" times."<<endl;
  123. }
Reply With Quote Quick reply to this message  
•
•
Join Date: Feb 2008
Posts: 43
Reputation: demroth is an unknown quantity at this point 
Solved Threads: 0
demroth demroth is offline Offline
Light Poster

Re: radix with strings of integers

 
0
  #5
Apr 3rd, 2008
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.

C++ Syntax (Toggle Plain Text) 
  1. #include <cstdlib>
  2. #include <iostream>
  3. #include <fstream>
  4.  
  5.  
  6. using namespace std;
  7. const int arraysize = 8; //size of the array
  8. void countingSort(int numbers[][1], int size_of_array);
  9. void radixSort(int n[], int A);
  10.  
  11. int main()
  12. {
  13.     int i;
  14.     ifstream in_file; //input file
  15.     int numbers[arraysize]; //the number of integers from the input file
  16.     char filename[50];
  17.  
  18.     cout<<"Enter the name of the file you wish to open "<<endl;
  19.     cin>> filename;
  20.  
  21.     in_file.open(filename); //open the input file
  22.  
  23.     if(!in_file.is_open()) //if the input file does not open
  24.     {
  25.       cout<<"Could not open the file.  " << filename <<endl
  26.           <<"The program is now closing. \n";
  27.            exit(EXIT_FAILURE); //exit the program
  28.     }
  29.  
  30.     while(in_file.good()) //if the input file opens
  31.     {
  32.       for(i = 0; i < arraysize; i++) //read all of the integers from the file..
  33.       {
  34.         in_file >> numbers[i]; //into the array numbers
  35.       }
  36.     }
  37.  
  38.   radixSort(numbers, arraysize); //call to function, pass arguements of numbers and arraysize
  39.  
  40.  
  41. /* for(i =0; i<arraysize; i++) //not needed yet
  42.  {
  43.        cout<<numbers[i]<<endl;
  44.  }*/
  45.  
  46.   system("PAUSE");
  47.   return EXIT_SUCCESS;  
  48. }
  49.  
  50. void countingSort(int numbers[][1], int size_of_array)
  51. {
  52.   // search for the minimum and maximum values in the input
  53.  
  54.  
  55.  
  56.   //finding the ones place
  57.  
  58.   int min = numbers[0][0]; //set min equal to number in place 0,0
  59.   int max = min;
  60.  
  61.   //the purpose of this loop is to find the min and max numbers
  62.   for(int i = 0; i < arraysize; i++)
  63.     for(int j = 0; j < 1; j++)
  64.   {
  65.    if (numbers[i][j] < min)
  66.       min = numbers[i][j];
  67.     else if (numbers[i][j] > max)
  68.         max = numbers[i][j];
  69.   }
  70.  
  71.   // create a counting array, counts, with a member for 
  72.   // each possible discrete value in the input.  
  73.   // initialize all counts to 0.
  74.   int distinct_elements = max - min + 1;
  75.  
  76.   int* counts = new int[distinct_elements];
  77.  
  78.   for(int i=0; i<distinct_elements; ++i)
  79.      counts[i] = 0;
  80.  
  81.   // accumulate the counts - the result is that counts will hold
  82.   // the offset into the sorted array for the value associated with that index
  83.   for(int i = 0; i < arraysize; i++)
  84.      for(int j=0; j < 1; j++)
  85.      ++counts[numbers[j][i] - min];
  86.  
  87.   // store the elements in the array
  88.   int j=0;
  89.   int counter = 0;
  90.   int z;
  91.   for(int i = min; i <= max; i++)
  92.     for(z = 0; z<counts[i-min]; z++)
  93.      {
  94.       numbers[j++][i] = i;
  95.       counter = counter + 1;
  96.      }
  97.  
  98.   delete[] counts;
  99.   cout<<"The number of times counting sort is run is " <<counter<<endl;
  100. }
  101.  
  102. void radixSort(int n[], int A)
  103. { 
  104.    int p;
  105.    int i; 
  106.    int temp_ones[arraysize][1], temp_tens[arraysize][1], temp_hundreds[arraysize][1];
  107.  
  108.    //finding the ones place. Or so I hope
  109.    for(int k=0; k < arraysize; k++)
  110.        for(int i =0; i < 1; i++)
  111.       temp_ones[k][i] = n[i]%10;
  112.  
  113.    int rcounter = rcounter + 1;
  114.    countingSort(temp_ones[arraysize][1], A);
  115.    /*for(int t1; t1 < arraysize; t1++)
  116.    {
  117.      if(n[t1]%10 == temp[t1])
  118.      //what now
  119.      
  120.       
  121.   /* int rcounter =0;
  122.    for( p=0; p < 3; p++ )
  123.    {
  124.       rcounter = rcounter + 1;
  125.       countingSort(n, A);
  126.    } */
  127.  //cout<<"The radix sort calls counting sort "<<rcounter<<" times."<<endl;
  128. }

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.
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread has been marked solved.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Other Threads in the C++ Forum


Views: 770 | Replies: 4
Thread Tools Search this Thread



Tag cloud for C++
6 api application array arrays assignment beginner binary bitmap c++ c/c++ calculator char class classes code coding compile compiler console conversion convert count data database delete developer display dll email encryption error file forms fstream function functions game generator getline givemetehcodez graph homeworkhelper iamthwee ifstream image input int java lazy lib loop looping loops map math matrix memory multidimensional multiple newbie news node number output parameter pointer problem program programming project proxy python random read recursion recursive reference return sort sorting string strings struct template templates text tree url variable vector video visual visualstudio win32 windows winsock word wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC