5
\$\begingroup\$

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?

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

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.