Quicksort java

Let us learn 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 – merge sort 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.

Also read – insertion sort java

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.


Java program for quicksort

Let’s see java program to implement quick sort,

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
      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:

quicksort java


What is complexity of quicksort?

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

Worst case : O(n²)