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”