Press "Enter" to skip to content

How to Implement QuickSort in Java

Ajk 1

Today, I wanted to take a look at a pretty common sorting technique. Indeed anyone with a Bachelor in CS is expected to know how to implement QuickSort in java or another basic programming language, such as C or C++. The basics of this sorting techniques are very easy to understand. You get a random element (which for simplicity I’ve chosen to be in the middle of the array), and then you go through the array, while swapping the current element if in the wrong sorting position (i.e. if it’s positioned ahead of a bigger number). By the end of this run we should have the final position of our random element (commonly called “pivot”). What we end up is two sub-arrays, left one with items less than our pivot and right one with items bigger than our pivot. We repeat the same technique on them recursively until we are done!! Easy no?

I quickly wrote my code where I implement QuickSort in java about 10 mins ago.

How to implement quicksort in Java

As you can see, implementing quicksort is fun and easy, so next time, you shouldn’t be afraid to implement it yourself, rather than using an already implemented routine.

QuickSort is widely used, since it’s average-case performance is O(nlogn) and worst-case space performances is O(logn), which is the space needed to keep the pointers. The only caveat in QuickSort, is the worst-case run time performance, it’s O(n2), which happens when we always choose the biggest or smallest element(not creating a division in the array and therefore defeating the whole “divide and conquer” method which quicksort is based on.). This is the reason, why sometimes other methods such as MergeSort or HeapSort might be used instead of QuickSort.

Well great, by now you should revised how to implement QuickSort in Java. For more info, you can check the QuickSort wiki
Hope you guys enjoyed it… and I’ll see you guys next time!

The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂
  1. Ankit Ankit

    Why int pivot = -1 * (-1 *(start + end)) / 2; ? I mean why -1s ?

Leave a Reply

Your email address will not be published. Required fields are marked *