Quicksort in java

Let’s learn quicksort in java.

Quicksort in java

Basically quicksort is a divide and conquer algorithm. Quicksort is one of the widely used sorting algorithm. Because it is used to sort large datasets or lists.

Quicksort in java implementation

Below are steps on quicksort algorithm java.

Given an array of numbers we want to sort them in an ascending order and that’s what quicksort does. So here we have an array of nine elements.

Then elements are divided into two parts. First we need to know one term, that is, pivot.

Pivot is middle element that we are going to compare with every element. One with element less than pivot and other greater than pivot.

We are going to move items that are less than or equal to the pivot to the left of the pivot and items that are greater than or equal to the pivot to the right of the pivot.

Then we have left partition and a right partition. Finally quicksort recursively sorts the above mentioned two partitions.

Quicksort uses recursive method or recursion in which method calls itself. Because it continues to call quicksort on a smaller and smaller subset of elements.

This algorithm don’t need another array since sorting takes place in the same array. It’s very efficient for very large datasets.

Quicksort (example) java recursive

import java.util.Arrays;
public class QuickSortInJava
{
   int partition(int[] arrNumbers, int low, int high)
   {
      int pivot = arrNumbers[high];
      // smaller element index
      int a = (low - 1);
      for(int b = low; b < high; b++)
      {
         // if current element is smaller than the pivot
         if(arrNumbers[b] < pivot)
         {
            a++;
            // swap arrNumbers[a] and arrNumbers[b]
            int temp = arrNumbers[a];
            arrNumbers[a] = arrNumbers[b];
            arrNumbers[b] = temp;
         }
      }
      // swap arrNumbers[a + 1] and arrNumbers[high] or pivot
      int temp = arrNumbers[a + 1];
      arrNumbers[a + 1] = arrNumbers[high];
      arrNumbers[high] = temp;
      return a + 1;
   }
   void sort(int[] arrNumbers, int low, int high)
   {
      if (low < high)
      {
         int p = partition(arrNumbers, low, high);
         /* recursive sort elements before
         partition and after partition */
         sort(arrNumbers, low, p - 1);
         sort(arrNumbers, p + 1, high);
      }
   }
   static void displayArray(int[] arrNumbers)
   {
      int s = arrNumbers.length;
      for(int a = 0; a < s; ++a)
         System.out.print(arrNumbers[a] + " ");
      System.out.println();
   }
   public static void main(String[] args)
   {
      int[] arrNumbers = {59, 74, 85, 67, 56, 29, 68, 34};
      int s = arrNumbers.length;
      QuickSortInJava obj = new QuickSortInJava();
      obj.sort(arrNumbers, 0, s - 1);
      System.out.println("After sorting array: ");
      displayArray(arrNumbers);
   }
}

Output:

After sorting array:
24 29 34 56 59 67 68 74 85

Quick sort has space complexity of O(log n).

Quicksort has an average O(n log n) of time complexity.

Quicksort has worst case of O(n²).

Quick sort in java user input

Now let’s learn to implement quicksort in java where user enters numbers as input.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Random;
public class QuickSortUserInput
{
   static int partition(int[] arrNumbers, int low, int high)
   {
      int b, temp, a = low + 1;
      Random rand = new Random();
      int r = rand.nextInt(high - low) + low;
      temp = arrNumbers[low];
      arrNumbers[low] = arrNumbers[r];
      arrNumbers[r] = temp;
      for(b = low + 1; b <= high; b++)
      {
         if(arrNumbers[b] <= arrNumbers[low] && b != a)
         {
            temp = arrNumbers[b];
            arrNumbers[b] = arrNumbers[a];
            arrNumbers[a++] = temp;
         }
         else if(arrNumbers[b] <= arrNumbers[low])
         {
            a++;
         }
      }
      temp = arrNumbers[a - 1];
      arrNumbers[a - 1] = arrNumbers[low];
      arrNumbers[low] = temp;
      return a - 1;
   }
   // quick sort function
   static void quickSort(int[] arrNumbers, int low, int high)
   {
      if(low < high)
      {
         int middle = partition(arrNumbers, low, high);
         quickSort(arrNumbers, low, middle - 1);
         quickSort(arrNumbers, middle + 1, high);
      }
   }
   public static void main(String[] args)
   {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int size;
      System.out.println("Please enter size of the array: ");
      try
      {
         size = Integer.parseInt(br.readLine());
      }
      catch(Exception ex)
      {
         System.out.println("Sorry!! Invalid Input");
         return;
      }
      int[] arrNumbers = new int[size];
      System.out.println("Please enter array elements: ");
      for(int a = 0; a < arrNumbers.length; a++)
      {
         try
         {
            arrNumbers[a] = Integer.parseInt(br.readLine());
         }
         catch(Exception ex)
         {
            System.out.println("Error");
         }
      }
      System.out.println("Before sorting array: ");
      System.out.println(Arrays.toString(arrNumbers));
      quickSort(arrNumbers, 0, arrNumbers.length - 1);
      System.out.println("After sorting array: ");
      System.out.println(Arrays.toString(arrNumbers));
   }
}

Output:

Please enter size of the array:
6
Please enter array elements:
55
9
86
18
12
28
Before sorting array:
[55, 9, 86, 18, 12, 28]
After sorting array:
[9, 12, 18, 28, 55, 86]