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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
/* * @Author: Ajk Palikuqi * * @Question: How To Implement QuickSort in Java. */ package iqLib.sortLib; public class QuickSort { public static void main(String[] args) { int[] myArr = {4, 2, 3, 5, 99, 20, 31, 4, 2, 11, 13, 15, 78, 8}; Sort(myArr); for (int i = 0; i < myArr.length; ++i) { System.out.println(myArr[i]); } } public static void Sort(int[] numbers) { quickSortHelper(numbers, 0, numbers.length - 1); } private static void quickSortHelper(int[] numbers, int start, int end) { if (start < end) { int index = partition(numbers, start, end); quickSortHelper(numbers, start, index - 1); quickSortHelper(numbers, index, end); } } private static int partition(int[] numbers, int start, int end) { int i = start; int j = end; int pivot = -1 * (-1 *(start + end)) / 2; int pVal = numbers[pivot]; while (i <= j) { while (numbers[i] < pVal) { ++i; } while (numbers[j] > pVal) { --j; } if (i <= j) { swap(numbers, i, j); ++i; --j; } } return i; } private static void swap(int[] numbers, int i, int j) { int temp = numbers[i]; numbers[i] = numbers[j]; numbers[j] = temp; } } |

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(n^{2}), 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!

#### Latest posts by Ajk (see all)

- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017

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