1
\$\begingroup\$

I am quite new in Python and I am starting my journey with sorting algorithms, PEP8 and the Zen of Python. I would like to get some feedback about my BubbleSort algorithm which I wrote. Also, is there a possibility to change the break statement to something else which will stop the loop?

def bubble_sort(structure):
    """
        Bubble sort.

        Description
        ----------
        Performance cases:
        Worst      : O(n^2)
        Average    : O(n^2)
        Best case  : O(n)

        Parameters
        ----------
        structure : Mutable structure with comparable objects.

        Returns
        -------
        structure : return sorted structure.

        Examples
        ----------
        >>> bubble_sort([7,1,2,6,4,2,3])
        [1, 2, 2, 3, 4, 6, 7]

        >>> bubble_sort(['a', 'c', 'b'])
        ['a', 'b', 'c']

    """

    length = len(structure)

    while True:
        changed = False
        for i in range(length - 1):
            if structure[i] > structure[i + 1]:
                structure[i], structure[i + 1] = structure[i + 1], structure[i]
                changed = True
        if not changed:
            break
    return structure
\$\endgroup\$
  • \$\begingroup\$ You can implement it with 2 for loops, then you can get rid of the break \$\endgroup\$ – RobAu Dec 10 '18 at 13:30
  • \$\begingroup\$ I get an idea now what if i change the break statment to return structure and delete the last line return structure. Will it harmonize with PEP8? \$\endgroup\$ – Michael Ogorkovyi Dec 10 '18 at 13:32
0
\$\begingroup\$

Your code looks nice and the documentation is high quality.

Maybe a few things can be improved anyway.

API

It could be a good idea to get inspiration from the Python API functions related to sorting, we have:

  • sorted returning a new list from an iterable
  • list.sort sorts a list in place, returns None

In your case, as structure is sorted in place, I am not sure it makes sense to return it.

Parameter structure

This is mostly personal opinion but instead of structure, I'd find container to be a better name.

Also, if you want to be precise in the documentation, you might want to say that it is mutable but also that it implements __len__, __getitem__ and __setitem__. These objects are also called (mutable) sequences.

The code

Not much to say about the code itself.

Instead of having if not changed: break, you could write a: while changed loop which is very slightly more concise.

Also, you'll find an optimisation suggestion on Wikipedia:

The bubble sort algorithm can be easily optimized by observing that the n-th pass finds the n-th largest element and puts it into its final place. So, the inner loop can avoid looking at the last n − 1 items when running for the n-th time

Before getting into such a change, I highly recommend writing unit tests.

\$\endgroup\$
  • \$\begingroup\$ I have one more question. How can i make a copy of the structure to return it as sorted does ? \$\endgroup\$ – Michael Ogorkovyi Dec 10 '18 at 15:48
  • \$\begingroup\$ Changing the struct in place is fine to me. However, if you need, you could use the copy module. Alternatively, you could just also just call list to copy your container as a list. \$\endgroup\$ – SylvainD Dec 10 '18 at 16:51

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.