Thread: Quicksort function help

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    3

    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!

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Getting an error with OpenGL: collect2: ld returned 1 exit status
    By Lorgon Jortle in forum C++ Programming
    Replies: 6
    Last Post: 05-08-2009, 08:18 PM
  2. Seg Fault in Compare Function
    By tytelizgal in forum C Programming
    Replies: 1
    Last Post: 10-25-2008, 03:06 PM
  3. In over my head
    By Shelnutt2 in forum C Programming
    Replies: 1
    Last Post: 07-08-2008, 06:54 PM
  4. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 02:28 PM
  5. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 06:39 AM