#include <iostream>
#include <time.h>
#include <fstream>
#define MAXSIZE  400000
#include <cstring>

using namespace std;

class Students
{
   public:
      string firstName;
      string lastName;
      string social;
      double gpa;

   Students()
   {
      firstName = "Adam";
      lastName = "Wilson";
      social = "000-00-0000";
      gpa = 0.00;
   }

   Students(string newSocial, string newFirst, string newLast, double newGPA)
   {
      firstName = newFirst;
      lastName = newLast;
      social = newSocial;
      gpa = newGPA;
   }
};

bool binarySearch( Students *X[], int l, int r, string sv, int &pos);
void shellSort(Students *X[], int n);
void mergeSort(Students *X[], int l, int r);
void merge(Students *X[], int l, int m, int r);

int main(void)
{
   
   ifstream infile;
   ofstream outfile;

   infile.open("bigfile");
   
   if(infile.fail()) 
   {
      cerr<<"bigfile has an problem"<<endl;
      exit(1);
   }
   
   outfile.open("output");
   
   if(outfile.fail()) 
   {
       cerr<<"results has an problem"<<endl;
       exit(1);
   }

   clock_t start_msec,stop_msec;   //TIME
   clock_t start_sort,stop_sort;   //TIME

   start_msec = clock();   //TIME
   
   string input;         
   Students * allInfo[400000] = {new Students()};
   int n = 0;
   
   string social;
   string firstName;
   string lastName;
   double gpa;
   int position;

   
   infile >> social >> firstName >> lastName >> gpa;

   Students * currentStudent;

   while (!infile.eof())
   {
      currentStudent = new Students(social, firstName, lastName, gpa);
      allInfo[n] = currentStudent;
      n++;
      infile >> social >> firstName >> lastName >> gpa;
   }
   
   infile.close();
   infile.open("file");
   exit(1);      
   mergeSort(allInfo, 0, n);
      
   infile >> input;
   
   while(!infile.eof())
   {
      bool s = binarySearch(allInfo, 0, n - 1, input, position);
      if(s)
      {
         outfile << (*allInfo[position]).social 
         << " " << (*allInfo[position]).firstName << " " 
         << (*allInfo[position]).lastName 
         << " " << (*allInfo[position]).gpa << endl;
      }
      else
         outfile << input << " not found!" << endl;
         infile >> input;
   }
   
   stop_msec = clock();   //TIME

   cerr<<"sort start: "<<start_msec<<endl;;   //TIME
   cerr<<"sort stop: "<<stop_msec<<endl;;   //TIME
   cerr<<(double)(stop_msec-start_msec)/CLOCKS_PER_SEC<<endl;   //TIME
   infile.close();
   outfile.close();

   return 0;
}

void mergeSort(Students *X[], int l, int r)
{
   if ( l < r )
   {
      int m = (l + r) / 2;
      mergeSort(X, l, m);
      mergeSort(X, m + 1, r);
      merge(X, l, m, r);
   }
}

void merge(Students *X[], int l, int m, int r)
{
   int l1 = l, r1 = m, l2 = m+1, r2 = r, t = l;
   
   Students *temp[MAXSIZE];

   while( l1 <= r1 && l2 <= r2)
   {
      if ((*X[l1]).social > (*X[l2]).social)
         temp[t++] = X[l1++];
      else
         temp[t++] = X[l2++];
   }
   while (l1 <= r1)
   {
      temp[t++] = X[l1++];
   }
   while (l2 <= r2)
   {
      temp[t++] = X[l2++];
   }
   for (int i = l; i <= r; i++)
   {
      X[i] = temp[i];
   }
   
}

bool binarySearch( Students *X[], int l, int r, string sv, int &pos)
{
   if ( l <= r )
   {
      int m = ( l + r ) / 2;
      if ( (*X[m]).social == sv )
      {
         pos = m;
         return true;
      }
   else if ((*X[m]).social < sv )
      return binarySearch( X, m +1, r, sv, pos );
   else
      return binarySearch( X, l, m - 1, sv, pos);
   }
   else
      return false;
}

I can't seem to figure out why it is giving me the fault. The program is designed to go through a file and sort it by the social security number but it gives me the fault during the sort routine.????

120-72-2069
238-67-6726
594-98-5434
605-86-4930
257-55-8096
135-84-6947
579-92-9785
239-43-3524
888-66-0333
241-29-7233
624-53-7364
157-80-8573
224-49-4670
215-27-2791
251-86-1103
612-57-2648
240-23-7824
149-44-4266
241-35-8761
583-74-6364

including string is not the problem my compiler takes care of that

well either way i have a different version of this program with bubble sort and it runs perfectly fine with out that file

>>Students * allInfo[400000] = {new Students()};
I get a stack overflow when I attempt to run that program, more than likely due to this line. That needs to be an array of pointers Students * allInfo[40000] = {0}; you don't want to allocate memory for that with new because the loop that reads the input file will do that. It would be a lot better if you used a vector of structs instead of that array, but maybe your instructor won't allow it.

The program is getting stack overflow error when the function merge() is called. I'm looking now to see if I can find out why.

I still got the seg fault i think there is something wrong with the merge because i have another copy of this program with bubble sort that works but it takes about four hours to get the job done

Well I found the problem -- MAXSIZE is too big. Either reduce its size to something more reasonable, such as 400, or use a vector so that the size will auto adjust to the number of items in the input file. Another option is to make allInfo global and not pass it around as a parameter.

At some point the value of X[l2] is NULL in function merge(). The value of l2 at that point is 6 and X[6] is NULL.

You will probably have to start using your compiler's debugger to find the exact cause of that.

what exactly is a vector?

A vector is declared in the header file <vector> and is an array that will auto expand as you add items to it. google for std::vector and you should find lots more info about it.

also don't forget to remove or comment this code

infile.close();
   infile.open("file");
//   exit(1);      
   mergeSort(allInfo, 0, n-1);

change the reading code as well. it doesn't include the last record in the collection does it ?

while (!infile.eof())
   {
      currentStudent = new Students(social, firstName, lastName, gpa);
      allInfo[n] = currentStudent;
      n++;
      infile >> social >> firstName >> lastName >> gpa;
   }

check what happen on last iteration. it reads the data from stream but will not make the student record from data read.

that loop should be written like this:

while (infile >> social >> firstName >> lastName >> gpa)
   {
      currentStudent = new Students(social, firstName, lastName, gpa);
      allInfo[n] = currentStudent;
      n++;
   }
This article has been dead for over six months. Start a new discussion instead.