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.

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

Quicksort algorithm implementation in java

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 some terminology, 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 smaller than the pivot to the left of the pivot and items that are greater than 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 that calls itself. Because it continues to call quicksort on a smaller and smaller subset of the 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

Let’s see java program for quick sort. Quicksort in java using recursion,

import java.util.Arrays;

public class QuickSortInJava 
{
   public static void sortMethod(Integer[] num, int low, int high)
   {
      // checking for empty/null array
      if(num == null || num.length == 0)
      {
         return;
      }

      if(low >= high)
      {
         return;
      }

      // getting pivot element from the middle of array
      int middle = low + (high - low) / 2;
      int pivot = num[middle];

      // lead to left < pivot and right > pivot
      int a = low, b = high;
      while(a <= b)
      {
         // checking all values until left side array is lesser than pivot
         while(num[a] < pivot)
         {
            a++;
         }
         // checking all values until left side array is greater than pivot
         while(num[b] > pivot)
         {
            b--;
         }
         // comparing values from both side of array
         // now after swapping move iterator on both list
         if(a <= b)
         {
            swapping(num, a, b);
            a++;
            b--;
         }
      }
      // repeat operation recursively to sort two sub arrays
      if(low < b)
      {
         sortMethod(num, low, b);
      }
      if(high > a)
      {
         sortMethod(num, a, high);
      }
   }

   public static void swapping(Integer[] number, int i, int j)
   {
      int temp = number[i];
      number[i] = number[j];
      number[j] = temp;
   }

   public static void main(String[] args) 
   {
      // unsorted array
      System.out.println("After sorting: ");
      Integer[] arr = new Integer[]{59, 74, 85, 67, 56, 29, 68, 34};
      // sorting using quick sort
      sortMethod(arr, 0, arr.length - 1);
      // checking sorted array
      System.out.println(Arrays.toString(arr));
   }
}



Output:

After sorting:
[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²)

Using scanner

Now let’s learn quicksort in java using scanner,

import java.util.Scanner;

public class QuickSortDemo 
{
   public static int divide(int[] arrNumber, int low, int high)
   { 
      int a = low + 1 , b = high, c = low, temp;
      for(; a <= b ;)
      {
         while(a <= high && arrNumber[a] < arrNumber[c])
             a++;
         while(arrNumber[b] > arrNumber[c] && b > low)
             b--;

         if(a < b)
         {
            temp = arrNumber[a];
            arrNumber[a] = arrNumber[b];
            arrNumber[b] = temp;
         }
         else
         {
            break;
         }
      }
      temp = arrNumber[c];
      arrNumber[c] = arrNumber[b];
      arrNumber[b] = temp;
      return b;
   }

   public static void sortMethod(int[] arrNumber, int low, int high)
   { 
      if(low < high)
      {
         int middle = divide(arrNumber, low, high);
         sortMethod(arrNumber, low, middle - 1);
         sortMethod(arrNumber, middle + 1, high);
      }
   } 

   public static void displayArray(int[] arrNum)
   {
      for(int a = 0; a < arrNum.length; a++)
      {
         System.out.print(arrNum[a] + " ");
      }
   }

   public static void main(String[] args) 
   {
      int numbers;
      Scanner sc = new Scanner(System.in);
      System.out.print("Please enter number of elements in the array: ");
      numbers = sc.nextInt();
      int[] arrInput = new int[numbers];
      System.out.println("Please enter " + numbers + " elements ");
      for(int a = 0; a < numbers; a++)
      {
         arrInput[a] = sc.nextInt();
      }
      System.out.println("Given elements in array: ");
      displayArray(arrInput);
      sortMethod(arrInput, 0, numbers - 1);
      System.out.println("\nElements after sorting: ");
      displayArray(arrInput);
      sc.close();
   }
}



Output:

Please enter number of elements in the array: 6
Please enter 6 elements
55
9
86
18
12
28
Given elements in array:
55 9 86 18 12 28
Elements after sorting:
9 12 18 28 55 86