Quicksort java

Hey guys!! Welcome to flower brackets blog. Let us learn quicksort java.

Quicksort Java

Basically quicksort is a divide and conquer algorithm. First quicksort algorithm divides array into two divisions namely “divide” and “conquer”. Finally combined to produce sorted array.

Also read – java merge sort

Given an array of items we want to sort them in an ascending order and that’s what quicksort does. Quicksort algorithm is one of the widely used sorting algorithm. Because it is used to sort large datasets or lists.

Quicksort algorithm

Below are steps of quicksort algorithm,

Quicksort Java

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 – arrays sort 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.

Also read – selection 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 me take you through java program to implement quicksort algorithm,

import java.util.Arrays;

public class QuickSort 
{
   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:

[29, 34, 56, 59, 67, 68, 74, 85]


What is complexity of quicksort?

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

Related Posts