In this tutorial, we are going to learn about quick sort in detail and its algorithmic implementation.

Quick Sort

• In-place algorithm.
• O(n log n) - base 2. we are repeatedly partitioning the array into two halves.
• Divide and Conquer algorithm.
• Recursive in structure.
• Uses a pivot element to partition the array into two parts.
• Elements < pivot to its left, elements > pivot to its right.
• Pivot will then be in its correct sorted position.
• Process is now repeated for the left array and right array.
• Eventually, every element has been the pivot. So every element will be in its correct sorted position.
• As with merge sort, we’ll end up partitioning the array into a series of 1- element arrays.
• Unstable algorithm.

Quick Sort Algorithm

Quick Sort ( A, BEG, END ):
Description: Here A is an unsorted array having N elements. BEG is the lower bound and END is the upper bound.

1. If ( BEG < END ) then
2. Find the element that divides the array into two parts using subfunction Partition( ).
3. Quick Sort ( Left Half )
4. Quick Sort ( Right Half ).
   [ End of If ]
5. Exit

Partition ( ):

1. Set LEFT = BEG, RIGHT = END and LOC = BEG
2. Beginning with the element pointed by RIGHT, scan the array from right to left, comparing each element with the element pointed by LOC until:
   a. Element smaller than the element pointed by LOC is found.
   b. Interchange elements pointed by LOC and RIGHT.
   c. If RIGHT becomes equal to LOC, terminate the subfunction Partition ( ).
3. Beginning with the element pointed by LEFT, scan the array from left to right, comparing each element with the element pointed by LOC until:
   a. Element greater than the element pointed by LOC is found.
   b. Interchange elements pointed by LOC and LEFT.
   c. If LEFT becomes equal to LOC, terminate the subfunction Partition ( ).
4. Exit

Quick Sort Programmatic Implementation in Java

public class QuickSort {
	public static void main(String[] args) {
		int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };

		quickSort(intArray, 0, intArray.length);

		for (int i = 0; i < intArray.length; i++) {
			System.out.print(intArray[i]+ " ");
		}
	}
	public static void quickSort(int[] input, int start, int end) {
		if (end - start < 2) {
			return;
		}
		int pivotIndex = partition(input, start, end);
		quickSort(input, start, pivotIndex);
		for (int i = 0; i < input.length; i++) {
			//System.out.println(input[i]);
		}
		quickSort(input, pivotIndex + 1, end);
	}
	public static int partition(int[] input, int start, int end) {
		// This is using the first element as the pivot
		int pivot = input[start];
		int i = start;
		int j = end;
		while (i < j) {
			// NOTE: empty loop body
			while (i < j && input[--j] >= pivot);
			if (i < j) {
				input[i] = input[j];
			}
			// NOTE: empty loop body
			while (i < j && input[++i] <= pivot);
			if (i < j) {
				input[j] = input[i];
			}
		}
		input[j] = pivot;
		return j;
	}
}

Output:

-22 -15 1 7 20 35 55