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,

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 sortsortMethod(arr, 0, arr.length - 1); // checking sorted array System.out.println(Arrays.toString(arr)); } }

**Output:**

**What is complexity of quicksort?**

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

Worst case : O(n²)