2
\$\begingroup\$

I have written the following code for bubble sort. How can it be optimised?

def bubble_sort(details):  
    """compares two consecutive integers in a list and shifts the smaller one to left """
    for i in range(len(details)-1):
        try:
            if details[i] > details[i+1]:
                temp = details[i]
                details[i]= details[i+1]
                details[i+1] = temp
                bubble_sort(details)
        except IndexError:
            return
    return details


sort_me = [11,127,56,2,1,5,7,9,11,65,12,24,76,87,123,65,8,32,86,123,67,1,67,92,72,39,49,12, 98,52,45,19,37,22,1,66,943,415,21,785,12,698,26,36,18,97,0,63,25,85,24,94,1501]
print sort_me 
print bubble_sort(sort_me)
\$\endgroup\$
  • \$\begingroup\$ Bubble sort can't be optimized! \$\endgroup\$ – Gareth Rees Jan 21 '18 at 17:27
2
\$\begingroup\$

thanks for sharing your code.

There are a few things I wanted to talk about.

  1. You shouldn't try / except an IndexError as a form of control flow.

An IndexError here would be the programmer's mistake, you should make sure that your code can't even raise an IndexError in the first place by using correct conditions in your loops. You can also removed the try/except sections completely and your code still behaves the same way.

  1. Recursion

BubbleSort is an inefficient sorting algorithm when dealing with large inputs. The sheer number of comparisons done with larger inputs will cause some serious problems if you recursively call the function.

With the example input you gave, your function gets called 568 times. I tried sorting a list of double the size and got this

RecursionError: maximum recursion depth exceeded in comparison

Using a more straightforward iterative approach would be much more efficient.

def bubble_sort(details):  
    """compares two consecutive integers in a list and shifts the smaller one to left """
    for i in range(len(details) - 1):
        swapped = False
        for j in range(len(details) - 1):
            if details[j] > details[j+1]:
                temp = details[j]
                details[j] = details[j+1]
                details[j+1] = temp
                swapped = True

        if not swapped:
            break

    return details


sort_me = [11,127,56,2,1,5,7,9,11] * 100 # give it a large input
print sort_me
print bubble_sort(sort_me)

A few additional things,

  • Consider implementing a version that doesn't modify the original list, think sorted(list) vs list.sort().

  • Your current implementation sorts the method in place but also returns the same list. If your method is mutating the list, consider not having a return value (or returning None instead).

Hopefully this was useful for you!

\$\endgroup\$
0
\$\begingroup\$

Python has in place swap available:

temp = details[i]
details[i]= details[i+1]
details[i+1] = temp

will become:

details[i], details[i+1] = details[i+1], details[i]

Instead of recursing on the whole list, use 2 iterators (nested loops).

\$\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.