0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ I may be wrong, but the Python code does not look like the pseudocode on the wikipedia page. $\endgroup$
    – Nathaniel
    Aug 25 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.