# 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;
}

}``````