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

Given an array of items we want to sort them in an ascending order and that’s what quicksort does. 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.

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.

#### Java program for quicksort

Let me take you through java program to implement quicksort algorithm,

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

**What is complexity of quicksort?**

The worst case for the quicksort algorithm is big O of N squared, that is, O(n^{2}) 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 (n^{2}).