Welcome to our deep dive into the world of Quick Sort! This lesson is designed for both beginners and intermediate learners. We'll explore the Quick Sort algorithm, its variations (Hoare and Lomuto Partition), and put our new skills to practice with real-world examples. Let's get started! š
Quick Sort is a popular sorting algorithm that works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. This process is repeated recursively on the sub-arrays until the entire array is sorted.
The Hoare Partition Scheme is a more efficient implementation of the Quick Sort algorithm. It uses a properly chosen pivot to ensure that the sub-arrays have approximately equal sizes, leading to faster sorting. Here's the Hoare Partition algorithm:
Choose a pivot: The pivot can be the first element, the last element, or a random element. For now, we'll use the first element as our pivot.
Initialize three pointers: left, right, and pivotIndex. Initially, left and right point to the first and last elements, respectively.
While left is less than right:
left is less than the pivot, move left to the next element.right is greater than the pivot, move right to the previous element.left and right meet, swap the elements at left and pivotIndex.left and decrement right.Swap the pivot with the element at pivotIndex.
Recursively sort the sub-arrays left and right.
The Lomuto Partition Scheme is simpler than the Hoare Partition Scheme but may lead to unbalanced sub-arrays, potentially slowing down the sorting process. Here's the Lomuto Partition algorithm:
Choose a pivot: Similar to the Hoare Partition, we can choose the first, last, or a random element as the pivot.
Initialize three pointers: left, right, and pivotIndex. Initially, left points to the first element, and right points to the last element.
While right is greater than or equal to left:
right is greater than the pivot, move right to the previous element.left and right.left and decrement right.Swap the pivot with the element at left.
Recursively sort the sub-arrays left and right.
Let's put our new knowledge into practice with some code examples!
def hoare_partition(arr, low, high):
pivot = arr[low]
left = low + 1
right = high
while True:
while left <= right and arr[left] < pivot:
left += 1
while arr[right] > pivot:
right -= 1
if left >= right:
break
arr[left], arr[right] = arr[right], arr[left]
arr[low], arr[right] = arr[right], arr[low]
return right
arr = [3, 7, 8, 2, 1, 9, 5, 6]
pivotIndex = hoare_partition(arr, 0, len(arr) - 1)
print("Pivot Index:", pivotIndex)
print("Sorted Array:", sorted(arr))def lomuto_partition(arr, low, high):
pivot = arr[low]
left = low + 1
right = high
while left <= right:
while left <= right and arr[left] <= pivot:
left += 1
while arr[right] > pivot:
right -= 1
if left > right:
break
arr[left], arr[right] = arr[right], arr[left]
arr[low], arr[right] = arr[right], arr[low]
return right
arr = [3, 7, 8, 2, 1, 9, 5, 6]
pivotIndex = lomuto_partition(arr, 0, len(arr) - 1)
print("Pivot Index:", pivotIndex)
print("Sorted Array:", sorted(arr))Question: Which partition scheme uses a properly chosen pivot to ensure that the sub-arrays have approximately equal sizes?
A: Hoare Partition B: Lomuto Partition C: Neither, they both use random pivots
Correct: A: Hoare Partition Explanation: The Hoare Partition scheme uses a properly chosen pivot to balance the sub-arrays, making the sorting process faster.
That's it for today's lesson on Quick Sort (Hoare vs Lomuto Partition)! Keep practicing, and you'll master this powerful sorting algorithm. Until next time! š