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)

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

Bubble Sort with Recursion

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

University of Minnesota - Twin Cities

- Bubble Sort
- Selection Sort
- Merge Sort
- Quick Sort
- Shell Sort
- Radix Sort
- Bitonic Sort
- Bucket Sort
- Quickselect
- Heap Sort

Sorting & Selection Algorithms

Bubble Sort

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

Selection Sort

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

Merge Sort

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

Quick Sort

Shell Sort

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

Radix Sort

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

Bitonic Sort

https://www.geeksforgeeks.org/bucket-sort-2/

Bucket Sort

A heap is a tree in which items are sorted in a special way. There are two types of heaps: a min-heap and a max heap. A min-heap is one where the parent value is less than the value of the children. A max heap is one where the parent value is greater than the value of the children.

A heap sort algorithm for sorting in increasing order is as follows:
1) Build a max heap from input data
2) Replace the largest item (root) with the last item of the heap and reduce the size of the heap by 1. Then heapify the root of the tree.
3) Repeat step 2 while the size of the heap is greater than 1.

Learn Before

Related

Learn After