Thread: Quicksort

  1. #1
    Registered User OnionKnight's Avatar
    Join Date
    Jan 2005
    Posts
    555

    Quicksort

    I'm supposed to write a quicksort function but it won't work like it should. It's a recursive function and the problem seems to be that the function gets called so much that the application terminates. Here's the code:
    Code:
    #include <iostream>
    
    using namespace std;
    
    void quicksort (double* array, int slut, int start=0) 
    {
    	double k = array[start];
    	int kpos = 0;
    
    	if (slut - start > 1) {
    		for (int i = start; i < slut; i++) {
    			if (k > array[i]) {
    				for (int ix = i; ix > kpos; ix--) {
    					double temp = array[ix - 1];
    					array[ix - 1] = array[ix];
    					array[ix] = temp;
    				}
    				kpos++;
    			}
    		}
    		quicksort(array, kpos - 1);
    		quicksort(array, slut, kpos + 1);
    	}
    }
    
    int main()
    {
    	double tal[15] = {54.654,
    			-2.135435,
    			54.25,
    			76.345,
    			12.56,
    			54.124,
    			0.0,
    			-1.445,
    			54.455,
    			-234.4,
    			54.8,
    			23.6,
    			-645.5,
    			-3.0,
    			-45.5};
    	quicksort(tal, 15);
    	for (int i = 0; i < 15; i++)
    		cout << tal[i] << " ";
    	return 0;
    }
    No matter how much I look at it there seems to be nothing wrong. And slut = end.

  2. #2
    Registered User
    Join Date
    Apr 2005
    Posts
    41
    Quicksort takes three arguements, and ur only passing two in main.

  3. #3
    Registered User
    Join Date
    Sep 2004
    Posts
    197
    Quote Originally Posted by blindman858
    Quicksort takes three arguements, and ur only passing two in main.
    He has a default for the third, so thats ok.
    If any part of my post is incorrect, please correct me.

    This post is not guarantied to be correct, and is not to be taken as a matter of fact, but of opinion or a guess, unless otherwise noted.

  4. #4
    Registered User
    Join Date
    May 2005
    Location
    Sweden
    Posts
    16
    Your code logic is a slight bit messed up, so it never finishes sorting. It just keeps recursing, which causes a stack overflow and thus a crash.

    Here are some comments:
    Code:
    void quicksort (double* array, int slut, int start=0) 
    {
      double k = array[start];
    
      // Note that we don't wan't to start from the start of the array, but the start of the "chunk" we're currrently sorting
      // This was the error causing all the trouble
      int kpos = start;
    
      if (slut - start > 1)
      {
         // You included the start element here, which would make no sense; that is the one used as a base for comparisons...
         // It only results in one extra comparison, though...
         for (int i = start + 1; i < slut; i++)
         {
             if (k > array[i])
             {
               for (int ix = i; ix > kpos; ix--)
               {
                  double temp = array[ix - 1];
                  array[ix - 1] = array[ix];
                  array[ix] = temp;
               }
               ++kpos;
             }
         }
    
         quicksort(array, kpos-1);
         quicksort(array, slut, kpos+1);
       }
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Scalability problems with Quicksort
    By hbejkosa in forum C++ Programming
    Replies: 3
    Last Post: 12-26-2008, 11:26 PM
  2. Problems with Quicksort and Pointers
    By algatt in forum C Programming
    Replies: 3
    Last Post: 10-10-2007, 04:24 AM
  3. Using quicksort and radix sort for an anagram program
    By RazielX in forum C Programming
    Replies: 2
    Last Post: 05-03-2004, 09:33 AM
  4. quicksort problem
    By spinner in forum C Programming
    Replies: 9
    Last Post: 05-04-2003, 02:02 PM
  5. Quicksort
    By Nutshell in forum C Programming
    Replies: 1
    Last Post: 01-15-2002, 09:42 AM