# What is the value returned by Hoare partitioning?

Following the article about Quicksort from Wikipedia, there is an implementation of Hoare partitioning:

def partition(A, left, right):
pivot_idx = (left + right) // 2
pivot_val = A[pivot_idx]
while True:
while A[left] < pivot_val:
left += 1
while A[right] > pivot_val:
right -= 1
if left >= right:
return right
A[left], A[right] = A[right], A[left]
left += 1
right -= 1


And running this for the following inputs:

A = [4, 6, 2, 7, 1]
ret = partition(A, 0, len(A)-1) # pivot_val=2
print(A) # [1, 2, 6, 7, 4]
print(A[ret]) # 2

A = [5, 3, 6, 1, 2]
ret =  partition(A, 0, len(A)-1) # pivot_val=6
print(A) # [5, 3, 2, 1, 6]
print(A[ret]) # 1


In the first case, the returned index points to the original pivot which was 2. However, in the second case the returned index points to element 1, which is one position before the original pivot 6.

It seems that for Lomuto partitioning the returned index is always the pivot. However for Hoare partitioning it's not always the case. How could be interpreted the value returned by Hoare partitioning? All elements from the returned index are less or equal than the pivot?

• I may be wrong, but the Python code does not look like the pseudocode on the wikipedia page. Aug 25 at 20:15