codecamp

Background

As we may already by the name, quicksort is a very efficient method of sorting. However, there’s still some room for improvement to best avoid the worse case, such as a sorted array. The first solution we can use is to use a random privot instead of the start, mid or end position of the array. Further than that, we can use a hybrid sort rather than a pure recursive quicksort. The reason is that when we deal with a small array or data, sometimes it is faster to use an n^2 method than calling a function recursively.

Now, let me explain what do randomized quicksort and hybrid sort really mean in detail.

Randomized Quick Sort

• It sorts the sublist of the original list (from a low index to a high index)
• At each pass, it picks three random elements of the sublist, chooses the median of these three elements and uses it as a pivot. The median is the element in the middle (for example, if the three elements are 12, 7, 24, the median is 12). Such algorithm is called a randomized quicksort. The expected running time of a randomized quicksort is O(n log n).

Hybrid Sort

For large lists, quick sort tends to be the fastest general-purpose (comparison) sorting algorithm in practice. However, it runs slower than some of the Θ(n^2) algorithms on small lists. Since it’s a recursive divide and conquer algorithm, it needs to sort many small sublists. A hybrid sorting algorithm combines quick sort with insertion sort to make quick sort faster. Run quick sort as usual until the sublists become small (say, when a number of elements in a sublist are less than a certain threshold), and then use insertion sort to sort the small lists.

Code in Java

Randomized Quicksort

Hybrid Sort

 

Test Cases

In order to compare the actual running time of these two sorting methods, I created a couple of test cases:

1. A large array with 10000 integer elements
   1. Sorted array
   2. Reversely sorted array
   3. Random array
2. A small array with 10 integer elements
   1. Sorted array
   2. Reversely sorted array
   3. Random array

Test Result

I ran 10 times of the test in a row, and recorded the winner of each test as the result. Because the result here already showed a obvious conclusion at this point, I didn’t go further to do more test.

So, for each test case, the winning status are listed below, where R stands for randomized quick sort and H stands for hybrid sort:

       10000 elements                 10 elements
  Sorted  Reversed  Random   |  Sorted  Reversed  Random

1.    H        H        H     |    H        H        H
   

2.    H        H        R     |    H        H        H
   

3.    R        H        H     |    H        H        H
   

4.    H        H        H     |    H        H        H
   

5.    H        H        H     |    H        H        H
   

6.    H        H        H     |    H        H        H
   

7.    H        R        H     |    H        H        H
   

8.    R        H        H     |    H        H        H
   

9.    H        H        H     |    H        H        H
   

10.    H        H        H     |    H        H        H
    

Conclusion

According to the test result, we know that it’s obvious that hybrid sort has a dominant advantage over the randomized quicksort, no matter in a large or small array.

To be more specific, comparing hybrid sort(hybrid) and randomized quicksort(randomized), in a large sorted array, hybrid wins 8 times and randomized wins 2 times; in a large reversely sorted array, hybrid wins 9 times and randomized wins 1 time; in a large random array, hybrid wins 9 times and randomized wins 1 time. We know that hybrid can run faster than randomized in most cases, but randomized could be faster sometimes.

For a small array, we know that randomized will never win based on the tests I ran.

In conclusion, hybrid sort works well for us to improve the efficiency of our randomized quicksort method.