# Hoare’s vs Lomuto partition scheme in QuickSort

We have discussed implementation of QuickSort using Lomuto partition scheme. Lomuto’s partition scheme is easy to implement as compare to Hoare scheme.

Lomuto’s Partition Scheme

```partition(arr[], lo, hi)
pivot = arr[hi]
i = lo     // place for swapping
for j := lo to hi – 1 do
if arr[j] <= pivot then
swap arr[i] with arr[j]
i = i + 1
swap arr[i] with arr[hi]
return i
```

Refer QuickSort for details of this partitioning scheme.
Below are implementations of this approach:-

## C++

 `/* C++ implementation QuickSort using Lomuto's partition ` `   ``Scheme.*/` `#include ` `using` `namespace` `std; ` ` `  `/* This function takes last element as pivot, places ` `   ``the pivot element at its correct position in sorted ` `    ``array, and places all smaller (smaller than pivot) ` `   ``to left of pivot and all greater elements to right ` `   ``of pivot */` `int` `partition(``int` `arr[], ``int` `low, ``int` `high) ` `{ ` `    ``int` `pivot = arr[high];    ``// pivot ` `    ``int` `i = (low - 1);  ``// Index of smaller element ` ` `  `    ``for` `(``int` `j = low; j <= high- 1; j++) ` `    ``{ ` `        ``// If current element is smaller than or ` `        ``// equal to pivot ` `        ``if` `(arr[j] <= pivot) ` `        ``{ ` `            ``i++;    ``// increment index of smaller element ` `            ``swap(arr[i], arr[j]); ` `        ``} ` `    ``} ` `    ``swap(arr[i + 1], arr[high]); ` `    ``return` `(i + 1); ` `} ` ` `  `/* The main function that implements QuickSort ` ` ``arr[] --> Array to be sorted, ` `  ``low  --> Starting index, ` `  ``high  --> Ending index */` `void` `quickSort(``int` `arr[], ``int` `low, ``int` `high) ` `{ ` `    ``if` `(low < high) ` `    ``{ ` `        ``/* pi is partitioning index, arr[p] is now ` `           ``at right place */` `        ``int` `pi = partition(arr, low, high); ` ` `  `        ``// Separately sort elements before ` `        ``// partition and after partition ` `        ``quickSort(arr, low, pi - 1); ` `        ``quickSort(arr, pi + 1, high); ` `    ``} ` `} ` ` `  `/* Function to print an array */` `void` `printArray(``int` `arr[], ``int` `size) ` `{ ` `    ``int` `i; ` `    ``for` `(i=0; i < size; i++) ` `        ``printf``(``"%d "``, arr[i]); ` `    ``printf``(````" "````); ` `} ` ` `  `// Driver program to test above functions ` `int` `main() ` `{ ` `    ``int` `arr[] = {10, 7, 8, 9, 1, 5}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr); ` `    ``quickSort(arr, 0, n-1); ` `    ``printf``(````"Sorted array: "````); ` `    ``printArray(arr, n); ` `    ``return` `0; ` `} `

## Java

 `// Java implementation QuickSort  ` `// using Lomuto's partition Scheme ` `import` `java.io.*; ` ` `  `class` `GFG ` `{ ` `static` `void` `Swap(``int``[] array,  ` `                 ``int` `position1,  ` `                 ``int` `position2) ` `{ ` `    ``// Swaps elements in an array ` `     `  `    ``// Copy the first position's element ` `    ``int` `temp = array[position1];  ` `     `  `    ``// Assign to the second element ` `    ``array[position1] = array[position2];  ` `     `  `    ``// Assign to the first element ` `    ``array[position2] = temp;  ` `} ` ` `  `/* This function takes last element as  ` `pivot, places the pivot element at its  ` `correct position in sorted array, and ` `places all smaller (smaller than pivot) ` `to left of pivot and all greater elements  ` `to right of pivot */` `static` `int` `partition(``int` `[]arr, ``int` `low, ` `                                ``int` `high) ` `{ ` `    ``int` `pivot = arr[high]; ` `     `  `    ``// Index of smaller element ` `    ``int` `i = (low - ``1``); ` ` `  `    ``for` `(``int` `j = low; j <= high- ``1``; j++) ` `    ``{ ` `        ``// If current element is smaller ` `        ``// than or equal to pivot ` `        ``if` `(arr[j] <= pivot) ` `        ``{ ` `            ``i++; ``// increment index of ` `                 ``// smaller element ` `            ``Swap(arr, i, j); ` `        ``} ` `    ``} ` `    ``Swap(arr, i + ``1``, high); ` `    ``return` `(i + ``1``); ` `} ` ` `  `/* The main function that  ` `   ``implements QuickSort ` `arr[] --> Array to be sorted, ` `low --> Starting index, ` `high --> Ending index */` `static` `void` `quickSort(``int` `[]arr, ``int` `low,  ` `                                 ``int` `high) ` `{ ` `    ``if` `(low < high) ` `    ``{ ` `        ``/* pi is partitioning index,  ` `        ``arr[p] is now at right place */` `        ``int` `pi = partition(arr, low, high); ` ` `  `        ``// Separately sort elements before ` `        ``// partition and after partition ` `        ``quickSort(arr, low, pi - ``1``); ` `        ``quickSort(arr, pi + ``1``, high); ` `    ``} ` `} ` ` `  `/* Function to print an array */` `static` `void` `printArray(``int` `[]arr, ``int` `size) ` `{ ` `    ``int` `i; ` `    ``for` `(i = ``0``; i < size; i++) ` `    ``System.out.print(``" "` `+ arr[i]); ` `    ``System.out.println(); ` `} ` ` `  `// Driver Code ` `static` `public` `void` `main (String[] args) ` `{ ` `    ``int` `[]arr = {``10``, ``7``, ``8``, ``9``, ``1``, ``5``}; ` `    ``int` `n = arr.length; ` `    ``quickSort(arr, ``0``, n-``1``); ` `    ``System.out.println(``"Sorted array: "``); ` `    ``printArray(arr, n); ` `} ` `} ` ` `  `// This code is contributed by vt_m. `

## C#

 `// C# implementation QuickSort  ` `// using Lomuto's partition Scheme ` `using` `System; ` ` `  `class` `GFG ` `{ ` `static` `void` `Swap(``int``[] array,  ` `                 ``int` `position1,  ` `                 ``int` `position2) ` `{ ` `    ``// Swaps elements in an array ` `     `  `    ``// Copy the first position's element ` `    ``int` `temp = array[position1];  ` `     `  `    ``// Assign to the second element ` `    ``array[position1] = array[position2];  ` `     `  `    ``// Assign to the first element ` `    ``array[position2] = temp;  ` `} ` ` `  `/* This function takes last element as  ` `pivot, places the pivot element at its  ` `correct position in sorted array, and ` `places all smaller (smaller than pivot) ` `to left of pivot and all greater elements  ` `to right of pivot */` `static` `int` `partition(``int` `[]arr, ``int` `low, ` `                                ``int` `high) ` `{ ` `    ``int` `pivot = arr[high]; ` `     `  `    ``// Index of smaller element ` `    ``int` `i = (low - 1); ` ` `  `    ``for` `(``int` `j = low; j <= high- 1; j++) ` `    ``{ ` `        ``// If current element is smaller ` `        ``// than or equal to pivot ` `        ``if` `(arr[j] <= pivot) ` `        ``{ ` `            ``i++; ``// increment index of ` `                 ``// smaller element ` `            ``Swap(arr, i, j); ` `        ``} ` `    ``} ` `    ``Swap(arr, i + 1, high); ` `    ``return` `(i + 1); ` `} ` ` `  `/* The main function that  ` `   ``implements QuickSort ` `arr[] --> Array to be sorted, ` `low --> Starting index, ` `high --> Ending index */` `static` `void` `quickSort(``int` `[]arr, ``int` `low,  ` `                                 ``int` `high) ` `{ ` `    ``if` `(low < high) ` `    ``{ ` `        ``/* pi is partitioning index,  ` `        ``arr[p] is now at right place */` `        ``int` `pi = partition(arr, low, high); ` ` `  `        ``// Separately sort elements before ` `        ``// partition and after partition ` `        ``quickSort(arr, low, pi - 1); ` `        ``quickSort(arr, pi + 1, high); ` `    ``} ` `} ` ` `  `/* Function to print an array */` `static` `void` `printArray(``int` `[]arr, ``int` `size) ` `{ ` `    ``int` `i; ` `    ``for` `(i = 0; i < size; i++) ` `    ``Console.Write(``" "` `+ arr[i]); ` `    ``Console.WriteLine(); ` `} ` ` `  `// Driver Code ` `static` `public` `void` `Main() ` `{ ` `    ``int` `[]arr = {10, 7, 8, 9, 1, 5}; ` `    ``int` `n = arr.Length; ` `    ``quickSort(arr, 0, n-1); ` `    ``Console.WriteLine(``"Sorted array: "``); ` `    ``printArray(arr, n); ` `} ` `} ` ` `  `// This code is contributed by vt_m. `

/div>

Output:

```Sorted array:
1 5 7 8 9 10
```

Hoare’s Partition Scheme
Hoare’s Partition Scheme works by initializing two indexes that start at two ends, the two indexes move toward each other until an inversion is (A smaller value on left side and greater value on right side) found. When an inversion is found, two values are swapped and process is repeated.

It is implemented in below manner:

```partition(arr[], lo, hi)
pivot = arr[lo]
i = lo - 1  // Initialize left index
j = hi + 1  // Initialize right index

// Find a value in left side greater
// than pivot
do
i = i + 1
while arr[i]  pivot

if i >= j then
return j

swap arr[i] with arr[j]
```

Below are implementations of this approach:-

## C++

 `/* C++ implementation of QuickSort using Hoare's ` `   ``partition scheme. */` `#include ` `using` `namespace` `std; ` `  `  `/* This function takes last element as pivot, places ` `   ``the pivot element at its correct position in sorted ` `    ``array, and places all smaller (smaller than pivot) ` `   ``to left of pivot and all greater elements to right ` `   ``of pivot */` `int` `partition(``int` `arr[], ``int` `low, ``int` `high) ` `{ ` `    ``int` `pivot = arr[low]; ` `    ``int` `i = low - 1, j = high + 1; ` `  `  `    ``while` `(``true``) ` `    ``{ ` `        ``// Find leftmost element greater than ` `        ``// or equal to pivot ` `        ``do` `        ``{ ` `            ``i++; ` `        ``} ``while` `(arr[i] < pivot); ` `  `  `        ``// Find rightmost element smaller than ` `        ``// or equal to pivot ` `        ``do` `        ``{ ` `            ``j--; ` `        ``} ``while` `(arr[j] > pivot); ` `  `  `        ``// If two pointers met. ` `        ``if` `(i >= j) ` `            ``return` `j; ` `  `  `        ``swap(arr[i], arr[j]); ` `    ``} ` `} ` `  `  `/* The main function that implements QuickSort ` ` ``arr[] --> Array to be sorted, ` `  ``low  --> Starting index, ` `  ``high  --> Ending index */` `void` `quickSort(``int` `arr[], ``int` `low, ``int` `high) ` `{ ` `    ``if` `(low < high) ` `    ``{ ` `        ``/* pi is partitioning index, arr[p] is now ` `           ``at right place */` `        ``int` `pi = partition(arr, low, high); ` `  `  `        ``// Separately sort elements before ` `        ``// partition and after partition ` `        ``quickSort(arr, low, pi); ` `        ``quickSort(arr, pi + 1, high); ` `    ``} ` `} ` `  `  `/* Function to print an array */` `void` `printArray(``int` `arr[], ``int` `n) ` `{ ` `    ``for` `(``int` `i=0; i < n; i++) ` `        ``printf``(``"%d "``, arr[i]); ` `    ``printf``(````" "````); ` `} ` `  `  `// Driver program to test above functions ` `int` `main() ` `{ ` `    ``int` `arr[] = {10, 7, 8, 9, 1, 5}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr); ` `    ``quickSort(arr, 0, n-1); ` `    ``printf``(````"Sorted array: "````); ` `    ``printArray(arr, n); ` `    ``return` `0; ` `}  `

## Java

 `// Java implementation of QuickSort  ` `// using Hoare's partition scheme ` `import` `java.io.*; ` ` `  `class` `GFG ` `{ ` `     `  `/* This function takes last element  ` `as pivot, places the pivot element  ` `at its correct position in sorted  ` `array, and places all smaller  ` `(smaller than pivot) to left of pivot ` `and all greater elements to right ` `of pivot */` `static` `int` `partition(``int` `[]arr, ``int` `low,  ` `                                ``int` `high) ` `{ ` `    ``int` `pivot = arr[low]; ` `    ``int` `i = low - ``1``, j = high + ``1``; ` ` `  `    ``while` `(``true``) ` `    ``{ ` `        ``// Find leftmost element greater ` `        ``// than or equal to pivot ` `        ``do` `        ``{ ` `            ``i++; ` `        ``} ``while` `(arr[i] < pivot); ` ` `  `        ``// Find rightmost element smaller ` `        ``// than or equal to pivot ` `        ``do` `        ``{ ` `            ``j--; ` `        ``} ``while` `(arr[j] > pivot); ` ` `  `        ``// If two pointers met. ` `        ``if` `(i >= j) ` `            ``return` `j; ` `        ``int` `temp = arr[i]; ` `        ``arr[i] = arr[j]; ` `        ``arr[j] = temp; ` `        ``//swap(arr[i], arr[j]); ` `    ``} ` `} ` ` `  `/* The main function that  ` `   ``implements QuickSort ` `arr[] --> Array to be sorted, ` `low --> Starting index, ` `high --> Ending index */` `static` `void` `quickSort(``int` `[]arr, ``int` `low,  ` `                                 ``int` `high) ` `{ ` `    ``if` `(low < high) ` `    ``{ ` `        ``/* pi is partitioning index,  ` `        ``arr[p] is now at right place */` `        ``int` `pi = partition(arr, low, high); ` ` `  `        ``// Separately sort elements before ` `        ``// partition and after partition ` `        ``quickSort(arr, low, pi); ` `        ``quickSort(arr, pi + ``1``, high); ` `    ``} ` `} ` ` `  `/* Function to print an array */` `static` `void` `printArray(``int` `[]arr, ``int` `n) ` `{ ` `    ``for` `(``int` `i=``0``; i < n; i++) ` `    ``System.out.print(``" "` `+ arr[i]); ` `    ``System.out.println(); ` `} ` ` `  `// Driver Code ` `static` `public` `void` `main (String[] args) ` `{ ` `    ``int` `[]arr = {``10``, ``7``, ``8``, ``9``, ``1``, ``5``}; ` `    ``int` `n = arr.length; ` `    ``quickSort(arr, ``0``, n - ``1``); ` `    ``System.out.println(``"Sorted array: "``); ` `    ``printArray(arr, n); ` `} ` `} ` ` `  `// This code is contributed by vt_m. `

## C#

 `// C# implementation of QuickSort  ` `// using Hoare's partition scheme ` `using` `System; ` ` `  `class` `GFG ` `{ ` `     `  `/* This function takes last element  ` `as pivot, places the pivot element  ` `at its correct position in sorted  ` `array, and places all smaller  ` `(smaller than pivot) to left of pivot ` `and all greater elements to right ` `of pivot */` `static` `int` `partition(``int` `[]arr, ``int` `low,  ` `                                ``int` `high) ` `{ ` `    ``int` `pivot = arr[low]; ` `    ``int` `i = low - 1, j = high + 1; ` ` `  `    ``while` `(``true``) ` `    ``{ ` `        ``// Find leftmost element greater ` `        ``// than or equal to pivot ` `        ``do` `        ``{ ` `            ``i++; ` `        ``} ``while` `(arr[i] < pivot); ` ` `  `        ``// Find rightmost element smaller ` `        ``// than or equal to pivot ` `        ``do` `        ``{ ` `            ``j--; ` `        ``} ``while` `(arr[j] > pivot); ` ` `  `        ``// If two pointers met. ` `        ``if` `(i >= j) ` `            ``return` `j; ` `        ``int` `temp = arr[i]; ` `        ``arr[i] = arr[j]; ` `        ``arr[j] = temp; ` `        ``//swap(arr[i], arr[j]); ` `    ``} ` `} ` ` `  `/* The main function that  ` `   ``implements QuickSort ` `arr[] --> Array to be sorted, ` `low --> Starting index, ` `high --> Ending index */` `static` `void` `quickSort(``int` `[]arr, ``int` `low,  ` `                                 ``int` `high) ` `{ ` `    ``if` `(low < high) ` `    ``{ ` `        ``/* pi is partitioning index,  ` `        ``arr[p] is now at right place */` `        ``int` `pi = partition(arr, low, high); ` ` `  `        ``// Separately sort elements before ` `        ``// partition and after partition ` `        ``quickSort(arr, low, pi); ` `        ``quickSort(arr, pi + 1, high); ` `    ``} ` `} ` ` `  `/* Function to print an array */` `static` `void` `printArray(``int` `[]arr, ``int` `n) ` `{ ` `    ``for` `(``int` `i=0; i < n; i++) ` `    ``Console.Write(``" "` `+ arr[i]); ` `    ``Console.WriteLine(); ` `} ` ` `  `// Driver Code ` `static` `public` `void` `Main() ` `{ ` `    ``int` `[]arr = {10, 7, 8, 9, 1, 5}; ` `    ``int` `n = arr.Length; ` `    ``quickSort(arr, 0, n - 1); ` `    ``Console.WriteLine(``"Sorted array: "``); ` `    ``printArray(arr, n); ` `} ` `} ` ` `  `// This code is contributed by vt_m. `

Output:

```Sorted array:
1 5 7 8 9 10
```

Comparison:

1. Hoare’s scheme is more efficient than Lomuto’s partition scheme because it does three times fewer swaps on average, and it creates efficient partitions even when all values are equal.
2. Like Lomuto’s partition scheme, Hoare partitioning also causes Quicksort to degrade to O(n^2) when the input array is already sorted, it also doesn’t produce a stable sort.
3. Note that in this scheme, the pivot’s final location is not necessarily at the index that was returned, and the next two segments that the main algorithm recurs on are (lo..p) and (p+1..hi) as opposed to (lo..p-1) and (p+1..hi) as in Lomuto’s scheme.

## tags:

Sorting Quick Sort Sorting