This is a Java implementation of an earlier post named QuickSort in which I used Python. This version uses lists rather than arrays so it can be used to sort a list of any object that implements the Comparable interface.

First the method which does the sorting:

Followed by the main method:

As per the previous post, the output is:

[1, 2, 3, 5, 7, 11, 18, 21, 44]

Time to fiddle 🙂 Let’s see how this performs vs the Selection Sort using similar data.

// milliseconds per x items

1000: 1
5000: 9
10000: 15
50000: 50
100000: 87
500000: 302
1000000: 844
1500000: 956
10000000: 5843

That is blindingly fast! 1.5 million items in under a second. Here is the updated main code:

Let’s try slow it down with some string comparisons:

1000: 3
5000: 7
10000: 11
50000: 71
100000: 124
500000: 540
1000000: 1125
1500000: 1721
10000000: 11973

Again, that is fast! Just over a second for 1 million items. Here is the main code for this test:

The quicksort uses divide and conquer, and recursion, to accomplish its goal. I know what it is doing, but I go giddy when I think about what it is doing 🙂

For more information on how quick sort works, please see my previous post.