Bubble sort in Python

Question

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

You can implement it with 2 for loops, then you can get rid of the break — Rob Audenaerde
– Rob Audenaerde, Commented Dec 10, 2018 at 13:30
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? — Michael Ogorkovyi
– Michael Ogorkovyi, Commented Dec 10, 2018 at 13:32

SylvainD · Accepted Answer · 2018-12-10 14:09:29Z

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.

I have one more question. How can i make a copy of the structure to return it as sorted does ? — Michael Ogorkovyi
– Michael Ogorkovyi, Commented Dec 10, 2018 at 15:48
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. — SylvainD
– SylvainD, Commented Dec 10, 2018 at 16:51

Stack Exchange Network

Bubble sort in Python

1 Answer 1

You must log in to answer this question.

Linked

Hot Network Questions

Bubble sort in Python

1 Answer 1

You must log in to answer this question.

Linked

Related

Hot Network Questions