Getting a segmentation dump and Thread 1: EXC_BAD_ACCESS (code=2, address=0x7ffeef3ffff8) when trying to perform Quicksort on vector of strings

Question

So, I have a function that reads strings from a file and pushes them into a vector of strings called words. I have a Quicksort function which essentially would sort the whole vector, but when I call the Quicksort function, it gives me this error "Thread 1: EXC_BAD_ACCESS (code=2, address=0x7ffeef3ffff8)" and in the Virtual Box, I am using Debian 9, it gives me a Segmentation Error.

  int main()
  {
    int time[5];
    vector<string> words;
    words=ReadFromFile();
    auto start = std::chrono::system_clock::now();
         quicksort(words, 0, words.size()-1);
         auto end = std::chrono::system_clock::now();
         std::chrono::duration<double> elapsed_seconds = end-start;
         cout<<endl;
         time[2]=elapsed_seconds.count();
         cout<<" Elapsed time: " << elapsed_seconds.count() <<"\n ";
         cout<<endl;
   }

I want to get the time that it takes the function to sort all the words.

 void quicksort(vector<string> words, long int from, long int to) //goes into infinite loop
   {
     if (from > to)
       {
         return;
       } 
     long int p = partition(words, from, to);
     quicksort(words, from, p);
     quicksort(words, p + 1, to);

      }

   long int partition(vector<string> words, long int from, long int to)
   {
      string pivot = words[from];
      long int i = from - 1;
      long int j = to + 1;
      while (i < j)
      {
    i++;while (words[i] > pivot){i++;}
    j--;while (words[j] < pivot){j--;}
    if (i < j){std::swap(words[i],words[j]);}
       }
     return j;
    }

My read from file function is this-

vector<string> ReadFromFile(){
 vector<string> words;
 ifstream read;
 read.open("macbeth.txt");
 if(!read.is_open())
 {
     cout<<"Error Opening file"<<endl;
 }
 else
 {
     while(!read.eof())
     {
         string line;
         getline(read,line);
         stringstream Curstr(line);
         while(Curstr>>line)
         {
             words.push_back(line);
         }
     }
 read.close();
 }
 return words; 
}

So I get a EXE_bad_access, and the recursion runs for about 50,000 times.

@EDIT Using the debugger, I found out that pivot is not getting the value from words[from]. It shows that string pivot = "" instead it should have the value like string pivot = words[from] //MACBETH which is the value of words[from] where from = 0 when the function is called the first time. Now, how do I get the value into pivot so it can divide the vector and perform the sort.

Answer 1

God... Don't do that. You are passing vector by copy while invoking those functions. Try to profile it and check if you don't run out of memory... (you probably do...)

void f(vector<string> words){
  // here only local words are modified, the vector that you passed from caller function is NOT affected
} 

^ the COPY of vector is passed. What you want to do is pass it by reference.

void f(vector<string> &words) {
// here you operate on original words vector
}

Try to fix that first and see if that helps (it should, mac can throw this error on memory limit as I recall properly)

here is an explanation how it works

@EDIT Try to run it with default sort() from stl. Also check if you don't overrun bounds of vector when calculating i/j - add some asserts to i and j : assert(0 <= i && i < words.size()) to check for correctness.

@EDIT2 It's not like stack is a place to debug your code for you... But I did a quick little investigation on some edge cases so listen:

1. use vector<string>& words as function arguments
2. reading files isn't as easy as it seems. Even though yours SOMEHOW works, don't use eof(). Here: .eof() loop not working
3. i++;while (words[i] > pivot){i++;} is essentialy do{i++;}while(words[i] > pivot)
4. ^ and it doesn't work because the condition is never met (first words[i] IS pivot) so i always stays the same
5. it loops infinitely for array of size 1 for example ["a"] (returned pivot is always 0)
6. you probably know the concept of quicksort but your implementation is wrong. Go check https://www.geeksforgeeks.org/quick-sort/ to learn how it should be done.
7. Don't use long unless you know what you are doing. Either you want int or long long.
8. This is... basic debugging / analysing code... Seems like you didn't put ANY effort to analyze the code. Stack is not a place for others to solve your problems because you are too lazy.
9. Go and read some tutorials about C++, because you don't have strong fundamentals yet.