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?

• RubberDuck: This code works. ideone.com/qfUZvR
• Michele Gargiulo: I ended up implementing an optimize version, adding checks to stop the iterations earlier if the list is already ordered at some point.

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.