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!