quickSort modification with insertionSort

Question

So i had to make a quicksort algorithm using pivot as the middle element of the array. I did that all fine. But now its asking me to modify the quickSort algorithm so that when any of the sublists reduces to less than 20, then i sort the sublist using an insertionSort.

I seemed to have got it working. It compiles and sorts the array perfectly, However I'm not sure if i did it right cuz the difference in CPU time between the modified quicksort and the normal quicksort arent that different. My uncertainty is in the recursive method recQuickSortC where i have the ">= 20" statements. I'm not sure if that's the right way to implement the modifcation, it could be completely wrong, all i know is that it sorts it correctly. Any help would be nice, thanks.

Here's my modified quickSort algorithm:

public void quickSortC(T[] list, int length)
{
    recQuickSortC(list, 0, length - 1);
}//end quickSort

private void recQuickSortC(T[] list, int first, int last)
{
  if (first < last)
  {
      int pivotLocation = partitionA(list, first, last);
      if ((pivotLocation - 1) >= 20)
          recQuickSortC(list, first, pivotLocation - 1);
      else
          insertionSort(list,pivotLocation -1);

      if ((pivotLocation - 1) >= 20)
          recQuickSortC(list, pivotLocation + 1, last);
      else
          insertionSort(list, pivotLocation + 1);
  }
}//end recQuickSort

private int partitionA(T[] list, int first, int last)
{
    T pivot;

    int smallIndex;

    swap(list, first, (first + last) / 2);

    pivot = list[first];
    smallIndex = first;

    for (int index = first + 1; index <= last; index++)
    {
        if (list[index].compareTo(pivot) < 0)
        {
            smallIndex++;
            swap(list, smallIndex, index);
        }
    }

    swap(list, first, smallIndex);

    return smallIndex;
}//end partition


    public void insertionSort(T[] list, int length)
{
    for (int unsortedIndex = 1; unsortedIndex < length;
                                unsortedIndex++)
    {
        Comparable<T> compElem =
                  (Comparable<T>) list[unsortedIndex];

        if (compElem.compareTo(list[unsortedIndex - 1]) < 0)
        {
            T temp = list[unsortedIndex];

            int location = unsortedIndex;

            do
            {
                list[location] = list[location - 1];
                location--;
            }
            while (location > 0 &&
                   temp.compareTo(list[location - 1]) < 0);

            list[location] = (T) temp;
        }
    }
}//end insertionSort

If you noticed theres a bunch of A's,B's, and C's next to the methods becuase i have to do alot of different quicksort algorithms. I put in all the code that is used within the algorithm. Let me know if u need more of it thanks.

score 2 · Accepted Answer · answered Apr 12 '12 at 23:03

2

This looks perfectly fine to me, although instead of testing whether the pivot distance is at most 20, I would just rewrite the quicksort method to say if (last - first <= 20) { do insertion sort} else { do normal quicksort}. That way you only have to write the check once, as opposed to once for each "side" of the recursion.

That said, it's likely that your benchmark isn't actually giving you good time estimates -- that is, your code is probably actually faster than you think it is -- just because getting accurate benchmarks in Java is not trivial or obvious.

answered Apr 12 '12 at 23:03

Louis Wasserman

191,574
25
345
413

Addition: Mandatory link about correct java micro benchmarking [here](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) – Voo Apr 12 '12 at 23:04
The _simplest_ way to get an accurate Java benchmark is to use [Caliper](http://caliper.googlecode.com), which just takes care of all the "hard parts" for you. – Louis Wasserman Apr 12 '12 at 23:05
A great tool to take care of lots of problems, but there are still lots of things that aren't (and imho can't) automated there so you still have to understand what the JVM actually does. – Voo Apr 12 '12 at 23:07
Perfect! thanks man, yea i think the problem is i'm using System.currentTimeMillis (which is what i'm suppose to use for the assignment) before and after the sort to get the CPU time, and its not giving me an accurate time. – user1210259 Apr 12 '12 at 23:48
It's not (just) a problem with `System.currentTimeMillis`, but the way the JVM optimizes code means that your method will take significantly longer than it ought to the first ten thousand times it's called. – Louis Wasserman Apr 13 '12 at 02:13

quickSort modification with insertionSort

1 Answers1