# What is Quick Sort - Hoare

The

The Hoare partition algorithm is generally faster than the Lomuto partition algorithm, which is another commonly used partitioning algorithm in quicksort, because it makes fewer swaps.

In Simple terms:

Imagine you have a bunch of numbers that you want to sort in ascending order. The quicksort algorithm is one way to do this. The Hoare partition algorithm is a part of the quicksort algorithm that helps to separate the numbers into two groups: one group with numbers smaller than a chosen "pivot" number, and another group with numbers larger than the pivot.

Here's how it works:

The Hoare partition algorithm is faster than other partitioning algorithms because it makes fewer swaps of the numbers in the list.

**Hoare****partition**algorithm selects a pivot element from the array and rearranges the elements such that all elements less than the pivot are moved to one side of the pivot, and all elements greater than the pivot are moved to the other side. The algorithm works by maintaining two indices, one pointing to the left end of the array and another pointing to the right end of the array. The indices move towards each other until they meet. At each iteration, the algorithm checks whether the elements at the two indices need to be swapped to ensure that the partition condition is met. When the two indices meet, the pivot is placed at the index where they meet, dividing the array into two parts that can be sorted independently.The Hoare partition algorithm is generally faster than the Lomuto partition algorithm, which is another commonly used partitioning algorithm in quicksort, because it makes fewer swaps.

In Simple terms:

Imagine you have a bunch of numbers that you want to sort in ascending order. The quicksort algorithm is one way to do this. The Hoare partition algorithm is a part of the quicksort algorithm that helps to separate the numbers into two groups: one group with numbers smaller than a chosen "pivot" number, and another group with numbers larger than the pivot.

Here's how it works:

- Pick a pivot number from the list of numbers.
- Move all the numbers smaller than the pivot to the left side of the list, and all the numbers larger than the pivot to the right side of the list.
- Repeat steps 1 and 2 for the smaller groups of numbers on either side of the pivot until all the numbers are sorted.

The Hoare partition algorithm is faster than other partitioning algorithms because it makes fewer swaps of the numbers in the list.

## Who invented it?

Hoare partition is a partitioning algorithm used in quicksort, a popular sorting algorithm. It was invented by British computer scientist Sir Charles Antony Richard Hoare in 1960.

## Pseudocode

```
function hoarePartition(array, low, high)
pivot = array[low] // choose first element as pivot
i = low - 1
j = high + 1
while true do
repeat
i = i + 1 // move index i towards the right
until array[i] >= pivot // find first element from left that is >= pivot
repeat
j = j - 1 // move index j towards the left
until array[j] <= pivot // find first element from right that is <= pivot
if i >= j then
return j // return the index where the two pointers meet
// swap elements at indices i and j
temp = array[i]
array[i] = array[j]
array[j] = temp
end while
end function
```

In this pseudo code, array is the array to be sorted, low is the leftmost index of the subarray being partitioned, and high is the rightmost index of the subarray being partitioned. The function returns the index where the two pointers i and j meet.

The algorithm works by selecting the first element of the array as the pivot, and then using two indices i and j to traverse the array from left and right, respectively. The algorithm continues to swap elements at indices i and j until the two indices meet at an index k where all elements to the left of k are less than or equal to the pivot, and all elements to the right of k are greater than or equal to the pivot.

The algorithm works by selecting the first element of the array as the pivot, and then using two indices i and j to traverse the array from left and right, respectively. The algorithm continues to swap elements at indices i and j until the two indices meet at an index k where all elements to the left of k are less than or equal to the pivot, and all elements to the right of k are greater than or equal to the pivot.

## Sample Code

```
// C++ code snippet
int hoarePartition(int arr[], int low, int high) {
int pivot = arr[low];
int i = low - 1;
int j = high + 1;
while (true) {
do {
i++;
} while (arr[i] < pivot);
do {
j--;
} while (arr[j] > pivot);
if (i >= j) {
return j;
}
// swap elements at indices i and j
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
void quicksort(int arr[], int low, int high) {
if (low < high) {
int partitionIndex = hoarePartition(arr, low, high);
quicksort(arr, low, partitionIndex);
quicksort(arr, partitionIndex + 1, high);
}
}
int main() {
int arr[] = { 7, 2, 1, 6, 8, 5, 3, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
quicksort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```

```
# Python code snippet
def hoare_partition(arr, low, high):
pivot = arr[low]
i = low - 1
j = high + 1
while True:
i += 1
while arr[i] < pivot:
i += 1
j -= 1
while arr[j] > pivot:
j -= 1
if i >= j:
return j
arr[i], arr[j] = arr[j], arr[i]
def quicksort(arr, low, high):
if low < high:
partitionIndex = hoare_partition(arr, low, high)
quicksort(arr, low, partitionIndex)
quicksort(arr, partitionIndex + 1, high)
arr = [7, 2, 1, 6, 8, 5, 3, 4]
quicksort(arr, 0, len(arr) - 1)
print(arr)
```

```
public class QuickSort {
public static int hoarePartition(int[] arr, int low, int high) {
int pivot = arr[low];
int i = low - 1;
int j = high + 1;
while (true) {
do {
i++;
} while (arr[i] < pivot);
do {
j--;
} while (arr[j] > pivot);
if (i >= j) {
return j;
}
// swap elements at indices i and j
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
public static void quicksort(int[] arr, int low, int high) {
if (low < high) {
int partitionIndex = hoarePartition(arr, low, high);
quicksort(arr, low, partitionIndex);
quicksort(arr, partitionIndex + 1, high);
}
}
public static void main(String[] args) {
int[] arr = { 7, 2, 1, 6, 8, 5, 3, 4 };
quicksort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
```

## Time and Space Complexity

The time complexity of the quicksort algorithm with the Hoare partition algorithm is O(n log n) in the average and best case, and O(n^2) in the worst case. The worst case occurs when the partition algorithm always selects the smallest or largest element as the pivot, resulting in unbalanced partitions.

The space complexity of the algorithm is O(log n) in the average and best case, and O(n) in the worst case due to the recursive nature of the algorithm. In the best case, the recursion tree is balanced and has a height of log n, while in the worst case, the recursion tree is unbalanced and has a height of n.

The space complexity of the algorithm is O(log n) in the average and best case, and O(n) in the worst case due to the recursive nature of the algorithm. In the best case, the recursion tree is balanced and has a height of log n, while in the worst case, the recursion tree is unbalanced and has a height of n.

## Advantages

- Quick: In the average and best case, quicksort is one of the fastest sorting algorithms. It can sort a large array in O(n log n) time.
- In-place: The algorithm sorts the array in-place, which means it doesn't require any additional memory for storing intermediate results.
- Cache-efficient: Quicksort is cache-efficient because it accesses contiguous memory locations, making efficient use of CPU caches.

## Disadvantages

- Unstable: Quicksort is an unstable sorting algorithm, which means that it doesn't preserve the relative order of equal elements.
- Worst-case performance: In the worst-case scenario, where the partition algorithm always selects the smallest or largest element as the pivot, quicksort can degrade to O(n^2) time complexity, making it slower than other algorithms such as mergesort.
- Randomness: The algorithm's performance depends on the choice of pivot, which can be random or deterministic. In the worst-case, a bad pivot can result in a poor partition, making the algorithm slower.