Quicksort java

Let’s learn quicksort java.

Quicksort java

Basically quicksort is a divide and conquer algorithm. First quicksort algorithm divides array into two sub-lists by pivot.

One sub-list have elements less than pivot and second sub-list have elements greater than pivot. Lastly sorted sub-lists are merged to form output.

Also read – merge sort in java

Quicksort algorithm is one of the widely used sorting algorithm. Because it is used to sort large datasets or lists.

quick sort in java explanation

Below are steps for quicksort algorithm.

quicksort java

Given an array of items we want to sort them in an ascending order and that’s what quicksort does.

So here we have an array of nine elements. First we need to know one term, that is, pivot.

Pivot is middle index element that we are going to compare with every other item.

Also read – inheritance in java

Then elements are divided into two parts. 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 (quicksort java recursive) that calls itself.

Because it continues to call quicksort on a smaller and smaller subset of items.

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


quick sort (example) java recursive

Let’s see java program for quick sort. Quicksort in java using 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:
29 34 56 59 67 68 74 85


quick sort space complexity?

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

Worst case: O(n²)


quick sort in java user input

Now let’s learn to implement quicksort in java user 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]