Quicksort function help

Hi everyone. I'm new to C++, and am trying to write a quicksort function. I've completed most of it, but there is something not right. It doesn't always sort everything. Running it several times on the same data returns different results. I'm at a loss. Anyone have an idea what might be causing this? Thanks!

Code:

---

//-----------------------------COMPILER DIRECTIVES------------------------------
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cassert>

//-----------------------------FUNCTION PROTOTYPES------------------------------
using namespace std;
void quicksort(vector<string> &v, int start, int end);

//--------------------------------MAIN FUNCTION---------------------------------
int main() {

// Declare variables
        vector<string> input;
        string line;
        int i;

// Get data from standard input
  while(!getline(cin, line).eof())
      input.push_back(line);

// Sort the input data
        quicksort(input, 0, input.size());

// Print sorted data to standard output
        for(i = 0; i < input.size(); i++)
                cout << input[i] << endl;

// Return error free
  return 0;
}

//-----------------------------FUNCTION DEFINITIONS-----------------------------
// sorts from v[start] to v[end - 1]
void quicksort(vector<string> &v, int start, int end) {

// Declare variables       
        int last;
        int i;

// Don't sort if there's only one item in the input
        if(end <= 1)
                return;
 
        srand(time(NULL));
        swap(v[0], v[rand() % end]);  // move pivot element to v[0]
        last = 0;
 
        for (i = 1; i < end; i++)  // partition
                if(v[i] < v[0])
                        swap(v[++last], v[i]);
 
        assert((last >= 0) && (last < end));
        swap(v[0], v[last]);  // restore pivot
 
        quicksort(v, start, last);  // recursively sort each part.
        quicksort(v, start + last + 1, end - last - 1);
}

---

Thanks for your help!

I think you could easily find examples how the partitioning might work. Yours differs a lot from what you usually see: e.g how can you swap something with v[++last] if you don't even know what v[++last] contains? It appears that the whole partitioning step might swap each item with itself but what does that gain?

A user named imalc is the local sorting and algorithms specialist, so you might also find something on his web page.

That's not how to use srand. You should only call srand once in your program. Using it as you have will mean that it returns the same number many many times in a row.

One problem with your quicksort though is with your partitioning step. anon has already picked up on this.
I would recommend using a different partitioning strategy: Move along from the start whilst the items are less than the splitter, then move along from the end whilst the items are not less than the splitter, then swap those two items and continue. If ant any point your iterators have crossed over then you're done partitioning.

Another problem is that you're mixing together two different ways of doing this. I'd guess that you've looked at two or more different implementations in the process of coming up with your code.
One way is to pass the start and end points of the segment to sort, and the start of the container to the function each time, and this is exactly what you're function prototype suggests you intended to do.
The other way is to pass a different point in the container to each recursive call, together with only a count of the number of items to sort. (2 parameters rather than 3)
Your function prototype is written for the first way, as is your first recursive call. However you're checking for end <= 1, as though end were an item count, rather than checking for the range from start to end being of length one. Your second recursive call also isn't right. Your first recursive call goes from start to one past the end of the lower portion, but your second recursive call needs to start at the index after the splitter, and go right up to the end. You appear to be calculating an item count rather than a position again. You need to pick one way and stick with it.

Good to see you making use of asserts.