I found lots of the hoare partition implementation for quick sorting, it didn't do the boundary check while finding the larger item or smaller item comparing to the pivot item. anyone know why?
For example, below is from https://www.techiedelight.com/quick-sort-using-hoares-partitioning-scheme/. While increasing i, decreasing j, the a[i] might be out of upper boundary when the array a is already a descending array.
# Partition using Hoare's Partitioning scheme
def partition(arr, low, high):
pivot = arr[low]
(i, j) = (low - 1, high + 1)
while True:
while True:
i = i + 1
if arr[i] >= pivot:
break
while True:
j = j - 1
if arr[j] <= pivot:
break
if i >= j:
return j
swap(arr, i, j)
my understanding is to add the boundary check for i, and j, like below:
# Partition using Hoare's Partitioning scheme
def partition(arr, low, high):
pivot = arr[low]
(i, j) = (low - 1, high + 1)
while True:
while True:
i = i + 1
if arr[i] >= pivot and i < high:
break
while True:
j = j - 1
if arr[j] <= pivot and j > low:
break
if i >= j:
return j
swap(arr, i, j)
