sorting problem

[demroth]

I thought I had posted this earlier but...
I am working on a sorting problem using counting sort but am getting a crash when I run the program. I have fixed some of the problems but I am still missing something. I just need a extra pair of eyes to find the rest.

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


using namespace std;
void countSort(int nums[], int size);

int main()
{
  int i;
  char filename[50];
  int arraysize = 8; //the size of the array with all of its elements;
  int numbers[8]; //the number of elements in the array
  ifstream infile;
  
  
  cout<<"Enter the name of the file you wish to open "<<endl;
  cin>>filename; 
  
  infile.open(filename); //open the input file
  if(!infile.is_open()) //if the input file does not open
  {
    cout<<"Could not open the file "<<filename<<" The program will now close."<<endl;
    exit(EXIT_FAILURE); //exit the program
  }
  
  while(infile.good()) //if the file opens
  {
      for(i = 0; i <= arraysize; i++) //read all of the integers from the file...
          infile >> numbers[i]; //..into the array, numbers
  }
  
  countSort(numbers, arraysize);
 
 for(i = 0; i <= arraysize; i++)
   cout << numbers[i] << endl; //prints out the numbers to the console
   
 infile.close(); //close input file
 system("PAUSE");
 return EXIT_SUCCESS; //exit the program
}
  
void countSort(int numbers[], int size)
{
     int i, counter, j;
     int min = numbers[0];
     int max = min;  
     int a[8], b[8], c[max];
   
   for(i = 0; i <= size; i++)
   { 
     if(numbers[i] < min)
       min = numbers[i];
     else if(numbers[i] > max)
       max = numbers[i];
   }    
     for(i = 0; i <= max; i++)
        c[i] = 0;
     for(j = 0; j <= 8; j++)
       c[a[j]] = c[a[j]] + 1;
     for(i = 0; i <= max; i++)
       c[i] = c[i] + c[i - 1];
     for(j = 0; j <= 8; j--)
     {
       b[c[a[j]]] = a[j];
       c[a[j]] = c[a[j]] -1;
     }
  
}

[Ancient Dragon]

The loop at lines 28-32 could be better written like this:

int i = 0;
while( i < arraysize && infile >> numbers[i] )
{
    i++;
}

line 34: do you know for a fact that the file contains exactly 8 integers? It would be better to pass the value of i from the above code countSort(numbers, i); line 51: >> for(i = 0; i <= size; i++)
You need to use the < operator, not <= because arrays are counted 0 to but not include the number of elements in the array -- 8 in this program. Same thing goes for all the other loops in that function. They all count beyond the legal array bounds.

[demroth]

The program is suppose to read in a single file that will have between 8 to 256 integers. Since I am not yet familiar with vectors and dynamic arrays, I am only creating the program to read only the first file which will have 8 integers. This is just part of the learning curve for me.

[Ancient Dragon]

That's ok but you still can not count from 0 to and including 8. If you do that is 9 numbers, not 8. If you are required to read a max of 256 integers then set the array size fo the max of 256.

and use the const arraysize declared on line 13 to declare the array on line 14.

[demroth]

Ok, I have made the changes but I still get a crash when running the program.

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


using namespace std;
void countSort(int nums[], int size);

int main()
{
 
  char filename[50];
  const int arraysize = 256; //the size of the array with all of its elements;
  int numbers[arraysize]; //the number of elements in the array
  ifstream infile;
  
  
  cout<<"Enter the name of the file you wish to open "<<endl;
  cin>>filename; 
  
  infile.open(filename); //open the input file
  if(!infile.is_open()) //if the input file does not open
  {
    cout<<"Could not open the file "<<filename<<" The program will now close."<<endl;
    exit(EXIT_FAILURE); //exit the program
  }
  
 int i = 0;
 while( i < arraysize && infile >> numbers[i] )
 {
    i++;
 }

  
  countSort(numbers, i);
 
 for(i = 0; i < arraysize; i++)
   cout << numbers[i] << endl; //prints out the numbers to the console
   
 infile.close(); //close input file
 system("PAUSE");
 return EXIT_SUCCESS; //exit the program
}
  
void countSort(int numbers[], int size)
{
     int i, counter, j;
     int min = numbers[0];
     int max = min;  
     int a[8], b[8], c[max];
   
   for(i = 0; i < size; i++)
   { 
     if(numbers[i] < min)
       min = numbers[i];
     else if(numbers[i] > max)
       max = numbers[i];
   }    
     for(i = 0; i < max; i++)
        c[i] = 0;
     for(j = 0; j < 8; j++)
       c[a[j]] = c[a[j]] + 1;
     for(i = 0; i < max; i++)
       c[i] = c[i] + c[i - 1];
     for(j = 0; j < 8; j--)
     {
       b[c[a[j]]] = a[j];
       c[a[j]] = c[a[j]] -1;
     }
  
}

[Ancient Dragon]

>>Ok, I have made the changes but I still get a crash when running the program.

I'm not supprised because there are compile errors you have to fix.
line 50: you can't allocate an array using an int that is not a const. The way to allocate c is using the new operator int* c = new int[max]; lines 59-69: you are still using the hard-coded value of 8 where you should be using size.

line 62: using unitialized array a, which is the reason your program crashes.

[Jacky1]

I think it's still crashing

0x08048fbb in countSort (numbers=0xbfea2af0, size=5) at sorting.cpp:69
69 b[c[a[j]]-1] = a[j];

I wish I can help :(

[Ancient Dragon]

I think it's still crashing

0x08048fbb in countSort (numbers=0xbfea2af0, size=5) at sorting.cpp:69
69 b[c[a[j]]-1] = a[j];

I wish I can help :(

Its because the values in array a are trashed -- it was never initialized to anything.

[demroth]

Here is the modified code. I am still working on the crash.

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


using namespace std;
void countSort(int nums[], int size);

int main()
{
 
  char filename[50];
  const int arraysize = 8; //the size of the array with all of its elements;
  int numbers[arraysize]; //the number of elements in the array
  ifstream infile;
  
  
  cout<<"Enter the name of the file you wish to open "<<endl;
  cin>>filename; 
  
  infile.open(filename); //open the input file
  if(!infile.is_open()) //if the input file does not open
  {
    cout<<"Could not open the file "<<filename<<" The program will now close."<<endl;
    exit(EXIT_FAILURE); //exit the program
  }
  
 int i = 0;
 while( i < arraysize && infile >> numbers[i] )
 {
    i++;
 }

  
  countSort(numbers, i);
 
 for(i = 0; i < arraysize; i++)
   cout << numbers[i] << endl; //prints out the numbers to the console
   
 infile.close(); //close input file
 system("PAUSE");
 return EXIT_SUCCESS; //exit the program
}
  
void countSort(int numbers[], int size)
{
     int i, counter, j;
     int min = numbers[0];
     int max = min;  
     int a[size], b[size];
     int* c = new int[max];
   
   for(i = 0; i < size; i++)
   { 
     if(numbers[i] < min)
       min = numbers[i];
     else if(numbers[i] > max)
       max = numbers[i];
   }    
     for(i = 0; i < max; i++)
        c[i] = 0;
     for(j = 0; j < size; j++)
       c[a[j]] = c[a[j]] + 1;
     for(i = 0; i < max; i++)
       c[i] = c[i] + c[i - 1];
     for(j = 0; j < size; j--)
     {
       b[c[a[j]]] = a[j];
       c[a[j]] = c[a[j]] -1;
     }
 delete[] c; 
}

[Jacky1]

Its because the values in array a are trashed -- it was never initialized to anything.

I tried to initialized by doing :

int a = {0};

and it said

variable-sized object `a' may not be initialized

[Ancient Dragon]

It wouldn't matter because the values in the array would still be wrong. Use a loop to initialize them to 0.

Even then the line b[c[a[j]]] = a[j]; won't work because all values of arrays a and c are 0, so you might as well write that line like this: b[0] = 0;

I'm not sure what you want to put in arrays a and c, but I'm certain it isn't 0.

If you have not see this wiki explaination you should probably read it and the example c program

[Jacky1]

Here is the modified code without crash.

the only thing I changed is j-- to j++ in the last for loop

because if j = 0 and by using j-- you are going to walk out of the edge which makes the sigfault

Also I initialized a and b

you need to check your logic to make sure it sorting correctly

this might help

http://www.codeproject.com/KB/recipes/countsort.aspx

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


using namespace std;
void countSort(int nums[], int size);

int main()
{
 
  char filename[50];
  const int arraysize = 8; //the size of the array with all of its elements;
  int numbers[arraysize]; //the number of elements in the array
  ifstream infile;
  
  
  cout<<"Enter the name of the file you wish to open "<<endl;
  cin>>filename; 
  
  infile.open(filename); //open the input file
  if(!infile.is_open()) //if the input file does not open
  {
    cout<<"Could not open the file "<<filename<<" The program will now close."<<endl;
    exit(EXIT_FAILURE); //exit the program
  }
  
 int i = 0;
 while( i < arraysize && infile >> numbers[i] )
 {
    i++;
 }

  
  countSort(numbers, i);
 
 for(i = 0; i < arraysize; i++)
   cout << numbers[i] << endl; //prints out the numbers to the console
   
 infile.close(); //close input file
 system("PAUSE");
 return EXIT_SUCCESS; //exit the program
}
  
void countSort(int numbers[], int size)
{
     int i, counter, j;
     int min = numbers[0];
     int max = min;  
    // int a[size], b[size];
   
     int * a = new int[size];
     int * b = new int[size];

     int* c = new int[max];
   
   for(i = 0; i < size; i++)
   { 
     if(numbers[i] < min)
       min = numbers[i];
     else if(numbers[i] > max)
       max = numbers[i];
   }    
     for(i = 0; i < max; i++)
        c[i] = 0;
     for(j = 0; j < size; j++)
       c[a[j]] = c[a[j]] + 1;
     for(i = 0; i < max; i++)
       c[i] = c[i] + c[i - 1];
     for(j = 0; j < size; j++)  // it crash because of j--
     {
       b[c[a[j]]] = a[j];
       c[a[j]] = c[a[j]] -1;
     }
 delete[] c; 
}

good LUCK

[demroth]

Here is the modified code without crash.

the only thing I changed is j-- to j++ in the last for loop
because if j = 0 and by using j-- you are going to walk out of the edge which makes the sigfault

Also I initialized a and b
you need to check your logic to make sure it sorting correctly

this might help

Ok I see how you initialized a and b and I totally would not have gotten that one but the change you made in the for loop, changing from j-- to j++ really throws me. I am building this counting sort algorithm from pseudocode in the book Introduction to Algorithms and that line is "for j = length[A] downto 1 do". I guess I got it wrong and should have incremented instead of decremented. I will now do some more checking to see if I got everything correct.

[Jacky1]

Ok I see how you initialized a and b and I totally would not have gotten that one but the change you made in the for loop, changing from j-- to j++ really throws me. I am building this counting sort algorithm from pseudocode in the book Introduction to Algorithms and that line is "for j = length[A] downto 1 do". I guess I got it wrong and should have incremented instead of decremented. I will now do some more checking to see if I got everything correct.

Honestly I don't like any kind of sorting because it just to much logic :(

for the last for loop

try this ( maybe that what you meant )

for(j = size -1 ; j >= 0; j--)
{

b[c[a[j]]] = a[j];

c[a[j]] = c[a[j]] -1;

}

[Ancient Dragon]

Also I initialized a and b

Not in the code you posted you didn't. They are still uninitialized at line 67. So if that code worked for you then it was purely by accident.

[Jacky1]

Not in the code you posted you didn't. They are still uninitialized at line 67. So if that code worked for you then it was purely by accident.

how we'll initialize it then !?

Thanks

[Ancient Dragon]

do it exactly like it was done to initialize c in lines 64 and 65. Also, did you bother to read the link I posted?