Bubble sort

1. Overview

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. It's one of the Greedy Algorithms.

2. Description

2.1 Procedure

• Step 1: Starting with the first element(index = 0), compare the current element with the next element of the array.
• Step 2: If the current element is greater than the next element of the array, swap them.
• Step 3: If the current element is less than the next element, move to the next element. Repeat Step 1.

2.2 Implementation

# Python3 Optimized implementation 
# of Bubble sort 
  
# An optimized version of Bubble Sort 
def bubbleSort(arr): 
    n = len(arr) 
   
    # Traverse through all array elements 
    for i in range(n): 
        swapped = False
  
        # Last i elements are already 
        #  in place 
        for j in range(0, n-i-1): 
   
            # traverse the array from 0 to 
            # n-i-1. Swap if the element  
            # found is greater than the 
            # next element 
            if arr[j] > arr[j+1] : 
                arr[j], arr[j+1] = arr[j+1], arr[j] 
                swapped = True
  
        # IF no two elements were swapped 
        # by inner loop, then break 
        if swapped == False: 
            break
           
# Driver code to test above 
arr = [64, 34, 25, 12, 22, 11, 90] 
   
bubbleSort(arr) 
   
print ("Sorted array :") 
for i in range(len(arr)): 
    print ("%d" %arr[i],end=" ") 
  
# This code is contributed by Shreyanshi Arun 

2.3 Time Complexity

Particular	Description
Best	O(n) comparisons, O(1) swaps
Worst and Average	O($n^{2}$) comparisons, O($n^{2}$) swaps
Space	O(1) auxiliary
Boundary Case	Bubble sort takes minimum time (Order of n) when elements are already sorted
Sorting In Place	Yes
Stable	Yes

3. Reference

https://en.wikipedia.org/wiki/Bubble_sort

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

https://www.studytonight.com/data-structures/bubble-sort

https://www.youtube.com/watch?v=nmhjrI-aW5o&feature=emb_title