**Quicksort algorithm** is one of the most used sorting algorithm, especially to sort large lists/arrays. Quicksort is a **divide and conquer algorithm**, which means original array is divided into two arrays, each of them is sorted individually and then sorted output is merged to produce the sorted array. On the average, **it has O(n log n) complexity**, making quicksort suitable for sorting big data volumes.

In more standard words, quicksort algorithm repeatedly divides an un-sorted section into a lower order sub-section and a higher order sub-section by comparing to a `pivot`

element. At the end of recursion, we get sorted array. Please note that the quicksort can be implemented to sort “in-place”. This means that the sorting takes place in the array and that no additional array need to be created.

## Quicksort algorithm

The basic idea of Quicksort algorithm can be described as these steps:

If the array contains only one element or zero elements then the array is sorted. If the array contains more then one element then:

- Select an element as a pivot element, generally from middle but not necessary.
- Data elements are grouped into two parts: one with elements that are in lower order than the pivot element, one with element that are in higher order than the pivot element.
- Sort the both parts separately by repeating step 1 and 2.

## Quicksort Java Example

Below is sample **quicksort java implementation**.

public class QuickSortExample { public static void main(String[] args) { // This is unsorted array Integer[] array = new Integer[] { 12, 13, 24, 10, 3, 6, 90, 70 }; // Let's sort using quick sort quickSort( array, 0, array.length - 1 ); // Verify sorted array System.out.println(Arrays.toString(array)); } public static void quickSort(Integer[] arr, int low, int high) { //check for empty or null array if (arr == null || arr.length == 0){ return; } if (low >= high){ return; } //Get the pivot element from the middle of the list int middle = low + (high - low) / 2; int pivot = arr[middle]; // make left < pivot and right > pivot int i = low, j = high; while (i <= j) { //Check until all values on left side array are lower than pivot while (arr[i] < pivot) { i++; } //Check until all values on left side array are greater than pivot while (arr[j] > pivot) { j--; } //Now compare values from both side of lists to see if they need swapping //After swapping move the iterator on both lists if (i <= j) { swap (arr, i, j); i++; j--; } } //Do same operation as above recursively to sort two sub arrays if (low < j){ quickSort(arr, low, j); } if (high > i){ quickSort(arr, i, high); } } public static void swap (Integer array[], int x, int y) { int temp = array[x]; array[x] = array[y]; array[y] = temp; } } Output: [3, 6, 10, 12, 13, 24, 70, 90]

In Java, ** Arrays.sort()** method uses quick sort algorithm to sort array of primitives using double pivot elements. Double pivot makes this algorithm even more faster. Check that out.

Happy Learning !!

Ivan A Aranda

Jeliot 3.7.2 appears to not be doing autoboxing and unboxing between int and Integer, I had to use intValue() for the array items and in the swap method switch to Integer rather than int for the temp variable. eclipse Build id: 20200313-1211 works fine.

Val

Quick sort is very good article of discussion. I propose to describe a little bit more that the worst performance cases take n^2 complexity. And why Java SDK choose this implementation.

Lokesh Gupta

your welcome

Val

Little mistake in comment of code:

instead “//Check until all values on left side array are greater than pivot”,

should be “//Check until all values on right side array are greater than pivot”