Quick sort algorithm implementation in java

Quicksort algorithm implementation in java

As the name, quicksort is the quickest algorithm to sort some numbers. There are some other sorting algorithms like bucket sort, insertion sort, bubble sort, radix sort, etc. Among them, quicksort is very efficient. The efficacy of quicksort in the worst cause is $\theta$ (n2), in the best cause $\theta$ (nLogn), and in the average cause, O(N log N).

Here is the step diagram of quicksort:

Here is the animated simulation of a quick sort algorithm.

If we look closely, the quick sort algorithm selects the last position of the array and assumes it as a pivot. It took two variables and assign the most left and the most right value of the array. Then it compares them with the pivot and swap if the left number is smaller than then the right number.

The algorithm steps will explain the quick sort easily:

Step 1 − First, Choose the highest index value of array has pivot
Step 2 − Take two variables and assign the most left and the most right value of the array excluding pivot
Step 3 − left variable points to the low index of the array
Step 4 − right variable points to the high index of the array
Step 5 − if value at left variable is less than pivot, move right
Step 6 − if value at right variable is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivot.

Let's look at the Quick sort algorithm implementation in java code:

import java.util.Scanner ;
 public class MyQuick {
  private int ar[] ;
  private int length ;
  private static Scanner w ;
  public static void main(String[] args) {
    w = new Scanner(System.in) ;
    int i,n ;
    System.out.println("Numbers of elements : ");
    n = w.nextInt() ;
    int [] a = new int [n] ;
    System.out.println("Elements are : ");
    for(i = 0; i < n; i++)
    {
     a[i] = w.nextInt() ;
         }
    MyQuick quick = new MyQuick () ;
    quick.Sort(a) ;
    System.out.println("After sorting the elements are :");
    for(int q : a)    {
      System.out.println(q);
    }
  }
  public void Sort(int [] a)
  {
   this.ar = a ;
   this.length = a.length ;
   QuickSort(0,length - 1) ;
   if(ar == null || ar.length == 0)
   {
    return ;
   }
  }
  private void QuickSort(int low, int high)  {
   int i = low ;
   int j = high ;   //calculate pivot number , i m talking pivot as middle index number
   int pivot = ar [low + (high - low) / 2] ;   //divide into two arrays
   while(i <= j)
   {
    while(ar[i] < pivot)
    {
     i++ ;
    }
    while(ar[j] > pivot)
    {
     j-- ;
    }
    if(i <= j)
    {
     Exchange(i,j) ;
     //move index to nest position on both sides
     i++ ;
     j-- ;
    }
   }
   //call quicksort method recursively
   if(low < j)
   {
    QuickSort(low,j) ;
   }
   if(i < high)
   {
    QuickSort(i,high) ;
   }
  }
  private void Exchange(int i, int j)
  {
   int temp = ar[i];
   ar[i] = ar[j] ;
   ar[j] = temp ;
  }
     }

Happy Coding...

Quick sort algorithm implementation in java