Quicksort not working

Question

This is all my code for my quicksort method, it works on a set of 21 numbers, but not on my real data set, which is about 100000. I have no idea what is wrong, I've been fiddling for two hours and it is due soon! Any help would be very welcome

public static void hybridQuicksort( int[] a, int start, int end )
{
 final int MIN = 13;
 if ( end - start >= MIN )
 {
  int pivot = findPivot( a, start, end );
  pivot = partition ( a, start, end, pivot );
  hybridQuicksort( a, start, pivot - 1 );
  hybridQuicksort( a, pivot + 1, end);
 }
 else
 {
  insertionSort( a, start, end );
 }
}

//partitions the array based on the pivot
public static int partition( int[] a, int start, int end, int pivot )
{
 int up = start + 1;
 int down = end;

 while ( up <= down )
 {

  while ( a[up] <= pivot)
   up++;

  while ( a[down] > pivot)
   down--;

  if ( up <= down )
   swap( a, up, down );
 }

 swap( a, start, down );

 return up;
}

//finds the first, middle, middle of first and middle, middle of middle and last
//and last numbers and sets their median as the pivot
public static int findPivot( int[] a, int start, int end )
{
 //swap the 4 numbers to the start of the array, leaving the first as is
 swap( a, start + 1, end - 1 );
 swap( a, start + 2, (start + end) / 2);
 swap( a, start + 3, end / 4);
 swap( a, start + 4, (end / 2) + (end / 4) );

 //sort the 5 numbers
 insertionSort( a, 0, 5 );

 //swap the median to the front, that's the pivot
 swap( a, start, start + 2 );
 //return the pivot
 return a[start];
}

Answer 1

Assumption:

• a holds 10'000 samples,
• start is 500

• end is 1000

  //swap the 4 numbers to the start of the array, leaving the first as is
  swap( a, start + 1, end - 1 );
  swap( a, start + 2, end / 2);
  swap( a, start + 3, end / 4);
  swap( a, start + 4, (end / 2) + (end / 4) );
  

end/4 is 250

.. you are swapping values from outside your sorting-subset.

Answer 2

This doesn't look like a homework problem. Were it a homework problem, the author would have written about seven to ten lines of code, with a proof of effectiveness, and turned it in. This guy is trying to be fancy, and it's biting him in the backside. You can tell by the way he drops to insertion-sort for so-called "small" intervals. (Clue: the threshold interval size is more than half the test data size. Give your algorithm some room to recurse if you want to test it well.) Second, there is the extra work he's doing to find an ideal pivot. This kind of complexity comes at a cost.

This is a hobbyist at work. What he needs is not just an answer. He needs an approach to solving hard problems. Quicksort is just the vehicle for that education.

Here's my approach.

The trick is to write Quicksort as Quicksort, get it working, and then worry about fancy special tricks. Kill off the noise about insertion sorting small intervals. Just assume that any interval of size zero or one is already sorted (which is your base case) and then work on making your partitioning code work using the left end of the interval as the pivot (as in classical original Quicksort), and you might consider printing the results of your data after one partitioning pass as a way to show yourself that it works. You'll develop testing skills that way. Anyway, once you have a working quicksort, then you can do things like separate pivot selection into a function and play with the implementation.

Good luck, and enjoy your project. Don't forget, though: We want timings, and especially time comparisons with the sort routine in the standard library!