Quicksort Java

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

What is quicksort?

Quicksort Java

By quicksort, all of you know it is one of the fastest sorting quicksort algorithm.

Basically quicksort is a divide and conquer algorithm. At first quicksort algorithm divides the given list into two divisions namely “divide” and “conquer”.

Also Read – Java Merge Sort

The first division is individually sorted and the second division is then combined and conquered.

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

Quicksort Java

So here we have an array of nine items. First we need to know some terminology.

We have a pivot. The pivot is an item that we are going to compare every other item.

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.

Also Read – Selection Sort Java

After we have done that we are going to have a left partition and a right partition.

Finally quicksort recursively sorts the above mentioned two divisions.

Quicksort is a recursive method that calls itself because it continues to call quicksort on a smaller and smaller subset of the items.

It’s also called divide and conquer algorithm and very efficient for very large datasets.


Example: quicksort java

Let me take you through quicksort code implementation,

public class QuickSort 
{
   int partition(int arrNum[], int low, int high)
   {
      int pivot = arrNum[high]; 
      int a = (low - 1); // smaller element index
      for(int b = low; b < high; b++)
      {
         // condition to check current element is smaller than or equal to pivot
         if(arrNum[b] <= pivot)
         {
            a++;
            // swapping arrNum[a] and arrNum[b]
            int temp = arrNum[a];
            arrNum[a] = arrNum[b];
            arrNum[b] = temp;
         }
      }
 
      // swapping arrNum[a + 1] and arrNum[high]
      int temp = arrNum[a + 1];
      arrNum[a + 1] = arrNum[high];
      arrNum[high] = temp;
 
      return a + 1;
   }
 
   void sortNumber(int arr[], int low, int high)
   {
      if(low < high)
      { 
         int part = partition(arr, low, high);
         // Recursive function sort elements before partition and after partition
         sortNumber(arr, low, part - 1);
         sortNumber(arr, part + 1, high);
      }
   }
 
   // printing utility function
   static void printingArray(int arr[])
   {
      int num = arr.length;
      for(int a = 0; a < num; ++a)
         System.out.print(arr[a] + " ");
      System.out.println();
   }
 
   public static void main(String[] args) 
   {
      int arr[] = {33, 36, 63, 34, 45, 78};
      int n = arr.length;
 
      QuickSort qs = new QuickSort();
      qs.sortNumber(arr, 0, n - 1);
 
      System.out.println("Quicksort sorted array : ");
      printingArray(arr);
   }
}

Output:

Quicksort sorted array : 33 34 36 45 63 78


Big Oh Analysis

The worst case for the quicksort algorithm is big O of N squared, that is, O(n2) and the average case is O (n log n).

The performance of the quicksort algorithm depends largely on how you select a pivot.

If you get a well selected pivot you can get Big O (n log n) performance. Very poorly worst case performance pivot is going to result in Big O (n2).


conclusion

So this is all about quicksort algorithm java. I hope you have understood the quick sort algorithm concept in java.

You can subscribe to my blog flower brackets if you haven’t already.

Do share this post if you like.

You May Also Like