# CodeEval Interrupted Bubble Sort

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.split(' ') if n.isdigit()]
icount = int(ls.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?

• This code works. ideone.com/qfUZvR – RubberDuck Jan 2 '15 at 21:34
• I ended up implementing an optimize version, adding checks to stop the iterations earlier if the list is already ordered at some point. – Michele Gargiulo Oct 28 '16 at 14:50

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.split(' ') if n.isdigit()]
icount = int(ls.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, 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, 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, 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.