Quick Sort using Hoare Partition and Lomuto Partition in Java

Quick Sort is based on the divide-and-conquer strategy. It is also called a partition exchange sort. It was developed by Tony Hoare in 1959.

Steps for Quick Sort:

• First step in Quick Sort is to choose an element called as pivot.
• Once the Pivot is selected, we need to reorder the elements so that:
  • all the elements less than the Pivot are placed before Pivot,
  • and elements greater than Pivot are placed after Pivot.
• With above steps, selected Pivot will be in its final position
• But, elements to left and right of Pivot are still not placed correctly
• So, above 2 steps need to be repeated for both left and right elements recursively
• Below we discuss Hoare Partition Scheme and Lomuto Partition Scheme

Hoare Partition Scheme

package com.techstackjournal;

public class HoarePartitionScheme {

	public static void main(String[] args) {

		int arr[] = { 16, 3, 10, 14, 64, 26, 32, 2, 94, 8 };

		System.out.print("Before Sort : ");
		for (int k : arr) {
			System.out.print(k + " ");
		}
		System.out.println();

		quicksort(arr, 0, arr.length - 1);

		System.out.print("After Sort  : ");
		for (int k : arr) {
			System.out.print(k + " ");
		}
	}

	public static void quicksort(int[] arr, int lower, int upper) {
		if (upper > lower) {
			int t = partition(arr, lower, upper);
			quicksort(arr, lower, t);
			quicksort(arr, t + 1, upper);
		}
	}

	private static int partition(int[] arr, int lower, int upper) {
		int pivot, i, j, temp;
		pivot = arr[(int) (upper + lower) / 2];
		i = lower - 1;
		j = upper + 1;

		while (true) {
			do {
				i++;
			} while (arr[i] < pivot);

			do {
				j--;
			} while (arr[j] > pivot);

			if (i >= j) {
				return j;
			}

			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
}

Lomuto Partition Scheme

package com.techstackjournal;

public class LomutoPartitionScheme {

	public static void main(String[] args) {

		int arr[] = { 16, 3, 10, 14, 64, 26, 32, 2, 94, 8 };

		System.out.print("Before Sort : ");
		for (int k : arr) {
			System.out.print(k + " ");
		}
		System.out.println();

		quicksort(arr, 0, arr.length - 1);

		System.out.print("After Sort  : ");
		for (int k : arr) {
			System.out.print(k + " ");
		}
	}

	public static void quicksort(int[] arr, int lower, int upper) {
		if (upper > lower) {
			int t = partition(arr, lower, upper);
			quicksort(arr, lower, t - 1);
			quicksort(arr, t + 1, upper);
		}
	}

	private static int partition(int[] arr, int lower, int upper) {
		int pivot, k;

		k = lower;

		pivot = arr[upper];

		for (int j = lower; j < upper; j++) {
			if (arr[j] < pivot) {
				int temp = arr[k];
				arr[k] = arr[j];
				arr[j] = temp;
				k++;
			}
		}

		int temp = arr[k];
		arr[k] = arr[upper];
		arr[upper] = temp;

		return k;
	}

}