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 ) 
```

University of Michigan - Ann Arbor

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

Bubble Sort

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]

Bubble Sort (Code)

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