# Bubble Sort: Time and Space Complexities

### 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.

• I don't understand what you are really asking, all of your answers are here and in Wikipedia, you pretty much tackle it already – Alper Aug 5 '19 at 10:53

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