Bubble Sort: Time and Space Complexities

Question

Algorithm

Bubble sort, also known as sinking sort, is a sorting algorithm that repeatedly steps through a list, compares adjacent pairs and swaps them if they are not in the right order. The pass through the list is repeated, until the sorting is complete. The algorithm, which is a comparison sort, is named for the way smaller or larger elements "bubble" to the top of the list.

---

Solution 1

This is my BubbleSort function:

def BubbleSort(l):
    for i in range(len(l)-1):
        for j in range(len(l)-1-i):
            if (l[j]>l[j+1]):
                l[j],l[j+1]=l[j+1],l[j]
    return l

which outputs:

print(BubbleSort([1,5,-5,0,10,100]))
[-5, 0, 1, 5, 10, 100]

Solution 2

With some detailed advice, here is a second solution, limited to using one list comprehension:

def BubbleSort(l):
    [l.append(l.pop(0) if i == len(l) - 1 or l[0] < l[1] else l.pop(1)) for j in range(0, len(l)) for i in range(0, len(l))]

which somewhat outputs the same:

l = [1,5,-5,0,10,100]
BubbleSort(l)
print(l)
[-5, 0, 1, 5, 10, 100]

---

Would you be so kind and review it? I'd also like to know about time/space complexities, if you possibly had time.

Answer 1

BubbleSort is not an efficient algorithm. Talking time-complexity it runs in \$O(n^2)\$ which is okay given a very small array, but for a larger amount of numbers its almost unusable.

This is a comparison between a few sorting algorithms that i wrote in C#. As you can see the only advantage of BubbleSort over the other algorithms is that it is very easy to program.

Anyway - back to your code. I would your implementation is good although i find the first one way more readable. All in all if you just wanted to implement BubbleSort you did a good job, but if you really want to sort a list, you should definitely consider another algorithm that runs in \$O(log(n))\$.