In this blog I am going to explain Quick Sort and also implement it using Java.

Quick Sort is an efficient sorting algorithm. It is also known as partition-exchange sort. Quick sort shows an average time complexity of O(nlogn). Quick Sort is based on divide and conquer concept in which we divide our range and perform operation on the divided ranges.

In Quick Sort array is divided into two sub arrays on the basis of pivot element. The position of pivot element remains fixed in this process. 

One of the array elements is selected as a pivot value. Values smaller than the pivot value are placed to the left of the pivot, while larger values are placed to the right.

For example

here mid of array is chosen as pivot element with value 3.

now value at index 0 is 4 which is greater then 3 and value at index 4 is 1 which is lower then 3 so we swap the values at their respective indices.

Recursive Implementation for Quick Sort in Java

package com.tech.blog;

public class QuickSort {
	private static int partition(int arr[], int l, int h) {
		
		int x = arr[h]; // initially the last value is chosen as pivot value
		int i = (l - 1);

		for (int j = l; j <= h - 1; j++) {
			if (arr[j] <= x) {
				i++;
				swap(arr, i, j);
			}
		}
		swap(arr, i + 1, h);
		return (i + 1); // here updated pivot value index is returned 
	}

	private static void swap(int[] arr, int a, int b) {
		int tmp = arr[a];
		arr[a] = arr[b];
		arr[b] = tmp;
	}

	private static void quickSort(int A[], int l, int h) {
		if (l < h) {
			/* Partitioning index */
			int p = partition(A, l, h); // finding the pivot element
			quickSort(A, l, p - 1); // quickSort on left subarray
			quickSort(A, p + 1, h); // quickSort on right subarray
		}
	}

	public static void main(String[] args) {
		int[] arr = { 4, 2, 6, 5, 3, 9 };
		
		System.out.print("Elements in array before sort : ");
		for (int a : arr)
			System.out.print(a + " ");
		System.out.println();
		
		quickSort(arr, 0, 5); //quickSort on array arr
		
		System.out.print("Elements in array after sort  : ");
		for (int a : arr)
			System.out.print(a + " ");
		System.out.println();
	}
}

Output of the above code is

Elements in array before sort : 4 2 6 5 3 9 
Elements in array after sort  : 2 3 4 5 6 9