Hoare partitioning falls into infinite loop

Question

I am trying to write a Hoare partitioning function that takes an array as input, and partitions it with the first element as pivot (I know it's not a good idea, I should be using randomized pivots, like the median-of-medians approach). Problem is that this function falls into infinite loop when the first element is the highest, as with the array [14,6,8,1,4,9,2,1,7,10,5]. I can see the error, after the first iteration of the outer while, both i and j equal 10, and hence the loop continues forever. Which portion should I mend to get the desired effect? Here's the code:

def hoare(arr):
    pivot = arr[0]
    i,j = 1,len(arr)-1
    while i <= j:
        while i < j and arr[i] < pivot:
            i += 1
        while j >= i and arr[j] >= pivot:
            j -= 1
        if i < j:
            arr[i],arr[j] = arr[j],arr[i]
    if j != 0:
        arr[0],arr[j] = arr[j],arr[0]
        return j

Answer 1

I believe the problem is that you've converted a do-while (or repeat-until, in Hoare's terms) loop into a while loop, so it never does the first j -= 1.

The simplest transformation in Python should be to change the two inner while loops like this:

while True:
    i += 1
    if not (i < j and arr[i] < pivot): break
while True:
    j -= 1
    if not (j >= i and arr[j] >= pivot): break

(I'm assuming here that the if i < j: is supposed to be outside the second while loop, and all of the other initial indentation is correct.)

I haven't reasoned this through completely, or run a variety of tests, but there's probably more than just this one error in your translation. You may need to also convert the outer loop into a do-while (Hoare actually makes it an explicit while TRUE with a check at the end), but I'm not sure. Anyway, for your sample input, the modified version returns 9, and arr is [10, 6, 8, 1, 4, 9, 2, 1, 7, 14, 5], which is incorrect, but it solves your infinite loop problem.

The next problem is an off-by-one error. If you're going to do the += 1 and -= 1 first in the inner loops, you have to start at -1, len(arr) rather than 0, len(arr)-1 (or, as you did, 1, len(arr)-1).

There may still be other problems. But I don't want to dig through your code finding all possible mistakes and explaining them. If you need that, tell us what our source was, and explain each transformation you made from that source, and it'll be much easier to explain where you went wrong. If not, it's much simpler to just translate Hoare's algorithm to Python directly, and then hopefully you can figure it out.

Here's a copy of the Hoare pseudocode that I found online (just replacing all tabs with two spaces):

Hoare-Partition (A, p, r)
  x ← A[p]
  i ← p − 1
  j ← r + 1
  while  TRUE
    repeat  j ←  j − 1
      until  A[j] ≤ x
    repeat  i ←  i + 1
      until  A[i] ≥ x
    if  i < j
      exchange  A[i] ↔ A[j]
    else
      return  j

Here's a trivial translation into Python; the only changes are minor syntax (including the way "exchange" is spelled) and turning each repeat/until into a while True/break.

def hoare(a, p, r):
  x = a[p]
  i, j = p-1, r+1
  while True:
    while True:
      j -= 1
      if a[j] <= x:
        break
    while True:
      i += 1
      if a[i] >= x:
        break
    if i < j:
      a[i], a[j] = a[j], a[i]
    else:
      return j

For a function with the same signature as yours:

def hoare0(arr):
  return hoare(arr, 0, len(arr)-1)

Answer 2

There is an error in this line:

while i < j and arr[i] < pivot:

It should be:

while i <= j and arr[i] < pivot:

The whole code for partition looks like:

def partition(a, l, r):
    pivot = a[r]
    i = l - 1
    j = r
    while i <= j:
        if i <= j and a[i] < pivot:
            i += 1
        if i <= j and a[j] >= pivot:
            j -= 1
        if i < j:
            a[i], a[j] = a[j], a[i]
    a[l], a[j] = a[j], a[l]
    return j

Why there was an infinite loop?

The pivot chosen here is 14.

So, after this code is executed:

while i < j and arr[i] < pivot:
    i += 1

i is 10 and j is 10.

Now, when this block is executed:

while i <= j and arr[j] >= pivot:
    j -= 1

As a[10] < 14, nothing happens. Since, i equals j, no swap happens. Now, since the outermost loop has condition i <= j, the loop keeps repeating.

What happens with correction?

So, after this code is executed:

while i <= j and arr[i] < pivot:
    i += 1

i is 11 (because the condition is still true when i equals j) and j is 10.

Now, when this block is executed:

while i <= j and arr[j] >= pivot:
    j -= 1

As a[10] < 14, nothing happens.

Now, i is 11 and j is 10, so no swap happens. But, the outermost loop is broken and a[j] swaps with pivot.

Your array becomes:

[5, 6, 8, 1, 4, 9, 2, 1, 7, 10, 14]

You can play here. It contains code with debug prints for both right and wrong partition schemes.

Answer 3

This Also Works :

key = arr[0]
i = 0
j = n-1
while i >= j:
    while arr[i] < key:
        i += 1
    
    while arr[j] > key:
        j -= 1
arr[j], arr[0] = arr[0], arr[j]

Answer 4

Partition algorithm has many variants, (short/long step), but we should be very careful with invariants,preconditions and non-structured programming statements (break, return ) concerning this classic algorithm.

Otherwise, we may fall in big troubles. Even when this can be against 'pythonic' philosophy of coding.

The next annotated solution (for didactic purposes) yields (10, [5, 6, 8, 1, 4, 9, 2, 1, 7, 10, 14]) for the original list [14,6,8,1,4,9,2,1,7,10,5], as expected. Comments can be stripped off,

def hoare(arr):
    # P: len(arr) > 0
    assert len(arr)>0
    i,j = 1,len(arr)
    # INV : \forall n : 1<=n<i :arr[n]<arr[0]
    #       \forall n : j<=n<len(arr) :arr[n]>=arr[0]
    # Quote(j-i)>=0
    while i < j:
        aa,bb=i,j
        while aa < j and arr[aa] < arr[0]:
            aa += 1
        while bb > aa and arr[bb-1] >= arr[0]:
            bb -= 1
        #let
        # aa = min n : i<=n<=j: n<j -> arr[n]>=arr[0]
        # bb = max n : aa<=n<=j: n>aa -> arr[n-1]<arr[0]
        #in
        if (bb-aa)==(j-i):
            #restore
            arr[i],arr[j-1] = arr[j-1],arr[i]
            #step
            i, j = i+1 , j -1
        else:
            #restore
            pass
            #step
            i,j = aa,bb

    arr[0],arr[j-1] = arr[j-1],arr[0]
    return j-1,arr
    # Q : \forall n : 0<=n<j-1 :arr[n]<arr[j]
    #     \forall n : j-1<=n<len(arr) :arr[n]>=arr[j]

EDIT: I'm not against goto, breaks, and continues... Donald Knuth stresses that "structured programming" is an idea rather than a language... Once you understand the laws, you can break them... is this more pythonic? Invariant keeps and quote decreases every loop.

def hoare_non_str(arr):
    assert len(arr)>0
    i,j = 1,len(arr)
    while i < j:
        while i < j and arr[i] < arr[0]:
            i += 1
        if i==j:
            break
        while j > i and arr[j-1] >= arr[0]:
            j -= 1
        if i==j:
            break
        #It is safe to swap here.
        arr[i],arr[j-1] = arr[j-1],arr[i]
        i = i + 1
    # swap pivote
    arr[0],arr[j-1] = arr[j-1],arr[0]
    return j-1,arr