Average Time Complexity: O(n^2)

```python
def bubble_sort(L):
    n = len(L)
    
    for i in range(n):
        for j in range(0, n-1-i):
            if L[j] > L[j+1]:
                L[j], L[j+1] = L[j+1], L[j]

https://www.geeksforgeeks.org/bubble-sort/

Bubble Sort

Bubble Sort (Code)

This algorithm is the simplest of all sorting algorithms. It works by repeatedly swapping the adjacent elements if they are in the wrong order. The name originates from how the elements "bubble" or "float" up to its correct place. 

For instance, to order the array (5, 1 , 4, 2, 8) in ascending order, it will take the following steps:
Loop #1
```
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 )
( 1 5 4 2 8 ) –>  ( 1 4 5 2 8 )
( 1 4 5 2 8 ) –>  ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
```
Loop #2
```
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ) 
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 
( 1 2 4 5 8 ) –>  ( 1 2 4 5 8 )
```

Loop #3 
```
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 
```

Logic behind Bubble Sort

```python
class bubbleSort:

    def bubbleSortRecursive(self, n=None):
        if n is None:
            n = self.length
 
        # Base case
        if n == 1:
            return

        for i in range(n - 1):
            if self.array[i] > self.array[i + 1]:
                self.array[i], self.array[i + 1] = self.array[i + 1], self.array[i]
 
        self.bubbleSortRecursive(n - 1)
```

Learn Before

Related