CodeEval Interrupted Bubble Sort

Question

In interrupted bubble sort, we need to stop the sorting based on the iteration count. This seems pretty straightforward to me. I have this code, which seems to work fine, but it isn't fast enough for larger input sets. How can I make this faster?

s = '36 47 78 28 20 79 87 16 8 45 72 69 81 66 60 8 3 86 90 90 | 2'
ls = s.split('|')
l = [int(n) for n in ls[0].split(' ') if n.isdigit()]
icount = int(ls[1].strip())
print "list is", l, len(l)
print "count is ", icount

ic = 0
while ic < icount:
    i = 0
    while i < len(l) - 2:
        if l[i + 1] < l[i]:
            tup = l[i], l[i + 1]
            l[i + 1], l[i] = tup
        i += 1
    ic += 1
print ' '.join(str(i) for i in l)

It is not fast enough for larger input sets. How can I make this faster?

Answer 1

First, move these into well-defined functions:

def bubble(l):
    i = 0
    while i < len(l) - 2:
        if l[i + 1] < l[i]:
            tup = l[i], l[i + 1]
            l[i + 1], l[i] = tup
        i += 1

def partial_bubble_sort(l, iterations):
    ic = 0
    while ic < icount:
        bubble(l)
        ic += 1

def main():
    s = '36 47 78 28 20 79 87 16 8 45 72 69 81 66 60 8 3 86 90 90 | 2'
    ls = s.split('|')
    l = [int(n) for n in ls[0].split(' ') if n.isdigit()]
    icount = int(ls[1].strip())
    print("list is", l, len(l))
    print("count is ", icount)

    partial_bubble_sort(l, icount)
    print(' '.join(str(i) for i in l))

main()
#>>> list is [36, 47, 78, 28, 20, 79, 87, 16, 8, 45, 72, 69, 81, 66, 60, 8, 3, 86, 90, 90] 20
#>>> count is  2
#>>> 36 28 20 47 78 16 8 45 72 69 79 66 60 8 3 81 86 87 90 90

Your while i < len(l) - 2 should be while i <= len(l) - 2; currently you are missing the last element.

Change the i = 0; while i < x; i += 1 loops to for i in range(x).

Your tup = l[i], l[i + 1]; l[i + 1], l[i] = tup would be faster on one line; CPython won't optimize out the intermediate for you.

Since you only want to split the string into two, I recommend:

in_string = '36 47 78 28 20 79 87 16 8 45 72 69 81 66 60 8 3 86 90 90 12 | 2'

numbers, sep, iterations = in_string.rpartition('|')
assert sep

numbers = [int(n) for n in numbers.split()]
iterations = int(iterations.strip())

...although I don't see why you're not just doing

numbers = [36, 47, 78, 28, 20, 79, 87, 16, 8, 45, 72, 69, 81, 66, 60, 8, 3, 86, 90, 90, 12]
iterations = 2

Anyhow, I'm finding this takes 30-50% less time than the original.

There are still more optimizations you can do. This is a more efficient bubble which avoids shifts by holding the moving element. This can be further improved by using enumerate to avoid the indexing.

def bubble(lst):
    held, rest = lst[0], lst[1:]

    for i, v in enumerate(rest):
        if v > held:
            v, held = held, v

        lst[i] = v

    lst[-1] = held

Each pass of bubble, one more element on the end of the array is already sorted. This means we can give bubble a paramenter of how many elements to skip.

def bubble(lst, skip):
    held, rest = lst[0], lst[1:len(lst)-skip]

    for i, v in enumerate(rest):
        if v > held:
            v, held = held, v

        lst[i] = v

    lst[-skip-1] = held

def partial_bubble_sort(lst, iterations):
    for skip in range(iterations):
        bubble(lst, skip)

You need len(lst)-skip here instead of just -skip since skip could be 0.

This explicitly checks lst[0], so you should cap iterations in partial_bubble_sort to len(lst) - 1 to prevent it ever being called for empty lists (or do a check in the function itself):

def partial_bubble_sort(lst, iterations):
    for skip in range(min(iterations, len(lst)-1)):
        bubble(lst, skip)

This should all end up several times (4-5) as fast as the original.