CODEWITHSUNDEEP
python
RussW
RussW

Reputation: 437

Python insertion sort with binary search not (but almost) working

As far as I can see, the binary search specified by the while loop should always continue searching until the min and max of the search space is equal. But on testing it, and always after having already sorted most of the items, it gets stuck in an infinite loop because mx somehow obtains the value -2.

I suppose I could change the condition of the while loop to patch that, but I'm trying to understand why it's behaving as it is, and have tried going over it with my eye and on paper but can't reproduce the event where mx = -2.

def insort(seq):
    for a in xrange(1, len(seq)):
        if seq[a] > seq[a - 1]:
            continue
        else:
            mn, mx = 0, a - 1
            while mn != mx:
                pivot = mn + ((mx - mn) / 2)
                if seq[a] > seq[pivot]:
                    mn = pivot + 1
                else:
                    mx = pivot - 1
            seq.insert(mn, seq.pop(a))

Upvotes: 0

Views: 816

Answers (1)

yanhan
yanhan

Reputation: 3537

NOTE: I am using python 2.7.3 . I'm not sure if other versions of python have different results arising from division, so here's a heads up.

Several changes are required:

  • Change mn != mx to mn < mx
  • Change pivot = mn + ((mx - mn) / 2) statement to pivot = int(math.floor((mn + mx) / 2)) or pivot = mn + int(math.floor((mx - mn) / 2)) to prevent any kind of surprises when it comes down to division.
  • Search interval indicated by mn, mx is changed to a half open interval, given by [mn, mx), because that is something I'm more familiar with when it comes to a hand coded binary search. So mx should be set to a initially, and mx should be set to pivot instead of pivot - 1 in the case where seq[a] <= seq[pivot] (iow, if the if test is False).

So the code with the edits should look like:

import math

def insort(seq):
    for a in xrange(1, len(seq)):
        if seq[a] > seq[a - 1]:
            continue
        else:
            mn, mx = 0, a
            while mn < mx:
                pivot = mn + int(math.floor(((mx - mn) / 2)))
                if seq[a] > seq[pivot]:
                    mn = pivot + 1
                else:
                    mx = pivot
            seq.insert(mn, seq.pop(a))

For the original code, I will give you an example where mx gets stuck at -2.

Given this list: [10, 7, 8, 5, 13, 2, 6, 1, 50]

Everything works fine until the element at index 5, which has a value of 2 (Verify this for yourself by adding some print statements). Since seq[a] > seq[a-1] is false (2 is the smallest element so far), we enter the else branch of the if statement.

At this point:

seq = [5, 7, 8, 10, 13, 2, 6, 1, 50]
a = 5
mn = 0
mx = a - 1 = 4

Since mn != mx (0 != 4), we enter the while loop. pivot is set to 0 + ((4 - 0) / 2) = 2. Next we perform if seq[a] > seq[pivot]. seq[a] = 2, while seq[pivot] = 8 and 2 > 8 is False, so we go to the else branch and perform mx = pivot - 1 = 2 - 1 = 1

At this point:

seq = [5, 7, 8, 10, 13, 2, 6, 1, 50]
a = 5
mn = 0
mx = 1

We perform the check at the while loop again. mn != mx (0 != 1), so we go inside the body of the while loop. We set pivot = 0 + ((1 - 0) / 2) = 0 (I am using python 2.7 to perform this division, so do verify at a repl), then perform the check seq[a] > seq[pivot] (2 > 5), which is False. Hence, we set mx = pivot - 1 = 0 - 1 = -1.

At this point:

seq = [5, 7, 8, 10, 13, 2, 6, 1, 50]
a = 5
mn = 0
mx = -1

Now, we perform the check at the while loop, mn != mx (0 != -1), so we enter the body of the while loop. pivot = 0 + ((-1 - 0) / 2) = -1. Then we perform the check seq[a] > seq[pivot] (seq[5] > seq[-1], which compares the 5th element with the last element of seq, in other words 2 > 50), and that is False. So mx = pivot - 1 = -1 - 1 = -2.

Now we've reached the final step:

seq = [5, 7, 8, 10, 13, 2, 6, 1, 50]
a = 5
mn = 0
mx = -2

At the while loop check, mn != mx, so we go on to pivot = 0 + ((-2 - 0) / 2) = -1. Observe that this is the same pivot as the above step. Then seq[5] > seq[-1] is performed (2 > 50), which is False. So mx = pivot - 1 = -1 - 1 = -2. And we end up in the same state as above. Which is why you see an infinite loop.

Finally, I just want to say that, binary search is a pretty tricky algorithm to code out since it's quite easy to make mistakes for the boundary indices. I've coded it by hand quite a lot of times and I still find it quite tricky. You might want to read this as well: http://en.wikipedia.org/wiki/Binary_search_algorithm

Hope that helps!

Upvotes: 3

Related Questions