What is Quick Sort - Hoare
The 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:
The Hoare partition algorithm is faster than other partitioning algorithms because it makes fewer swaps of the numbers in the list.
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();
}
}