How to Implement QuickSort in Java

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

/*
 * @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;
   }
}

* @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²), 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!