Quicksort

[Golden Lizard]

Hello, I'm trying to write a quicksort function, but for some reason I get a crash when I try to run it, I think it comes from recursion as it doesn't give a crash if I comment the recursions.

 template<typename data, size_t size> void quick(data (&ar)[size], int const & left, int const & right)
	{
		median(ar);
		int pivot = ar[(sizeof ar / sizeof(ar[0]))/2 -1];
		std::swap(ar[(sizeof ar / sizeof(ar[0])) / 2 - 1], ar[sizeof ar / sizeof(ar[0]) -1]);
		
		int i = left;
		int j = right;


		for (;;)
		{
			while (ar[++i] < pivot)   {};
			while (pivot   < ar[--j]) {};

			if (i < j) std::swap(ar[i], ar[j]);
			else break;
		}

	  std::swap(ar[0],ar[right]);
	  quick(ar, left, j-1);
	  quick(ar, i+1, right);

	};

[helios]

Line 5: The pivot should be inside the range [&ar[left]; &ar[right]].
Line 6: The pivot should be swapped to the end of the same range.
Line 14: If pivot happens to be the unique minimum, this loop is infinite.
Line 20: Why??
Lines 21 and 22: No return statement up to this point and recursion is not surrounded by a decision. Infinite recursion.

[Golden Lizard]

Thanks. Oh damn, I feel like an idiot =p. Is it good now? Or at least better?

template<typename data, size_t size>
 void quick(data(&arr)[size], unsigned const int & low, unsigned const int & high)
	{
        if(low<high)
	{	int left = low;
		int right = high;

		median(arr);
		data pivot = arr[right/2]
                std::swap(arr[right],arr[right/2]);

		while (true)
		{
			while (arr[++ left] <= pivot){};
			while (arr[-- right] > pivot){};
			
			if (left < right) std::swap(arr[left], arr[right]);
			else break;
		}

		quick(arr, low, right-1);
		quick(arr, left+1, high);

	} };

[helios]

Well, it's betterish.

Line 8: What does median() do?
Line 9: Can you guess the problem with this line?
Lines 14 and 15: Now the problem that was previously on line 14 has expanded to both loops.

I'd say just start over and rethink your partitioning algorithm.

[Golden Lizard]

Median sorts first, middle and last element of the array so I can get the median for quicksort, now I modified it to also return the middle element and I think I got it right now, tested it on multiple arrays and it works fine.

template<typename T, size_t size> T partition(T (&A)[size], int left, int right)
{

        T p = median(A, left, right);
	int i = left;
	int j = right;
	std::swap(A[j / 2], A[i]);

	for (;;)
	{
		while (A[++i] < p) if (i >= right) break;
		while (A[--j] > p) if (j <= left) break;
		if (i >= j) break;
		else std::swap(A[i], A[j]);
	}

	if (j == left) return j;
	std::swap(A[left], A[j]);

	return j;

}

template<typename T, size_t size> void quicksort(T (&A)[size], int left, int right)
{
	int q;

	if (right > left)
	{
		q = partition(A, left, right);
		quicksort(A, q + 1, right);
		quicksort(A, left, q - 1);
	} 
}

[helios]

Lines 3 and 4: Did you really intend to call median() twice?
Line 7: What if j / 2 < i?
Lines 11 and 12: There must be better ways to write this.