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.

Quicksort takes three arguements, and ur only passing two in main.

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.

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);
   }
}