Bubble Sort in Python

Bubble sort is a sorting algorithm in data structures that works with an average time complexity of O(n²). Let us look at the working of the algorithm on the list [2, 3, 1, 4, 0] before implementing it. The basic outline of the algorithm is that two successive elements are checked and if the right side element is less than the left side element, the elements are swapped. This makes sure that the elements are sorted from right to left.

General Rule: Swap two successive numbers [a, b] if a > b

1. In this step, we put the max element to the last.
   a. First 2 and 3 are checked, since 2 is less than 3, no change is done
   b. Then 3 and 1 is checked, is 1 is less than 3, the two numbers are swapped and the new list is [2, 1, 3, 4, 0]
   c. Now, 3 and 4 are compared, since it does not satisfy the rule, no change is done.
   d. Then we check 4 and 0, according to the rule, we swap the two numbers. Now the list after the first iteration is [2, 1, 3, 0, 4]
2. We now need to sort (n-1)th element. We follow the same procedure as before.
   a. We check the first two elements and since 2 > 1, we swap the two numbers. The new list reads as [1, 2, 3, 0, 4]
   b. We now check the 2nd and 3rd elements and since they are sorted, we do not change the list.
   c. The last elements to check are 3 and 0 and they are going to swap. This is the last to be checked because the number 4 has been sorted and stored in its value. The list after second iteration is [1, 2, 0, 3, 4].
3. We repeat the same steps as before and after the end of the third iteration, we get the list [1, 0, 2, 3, 4]
4. The last iteration is going to give us a sorted list [0, 1, 2, 3, 4]

The bubble sort algorithm is implemented as shown below using Python.

import random
def bubble_sort(arr):
  size= len(arr)
  for i in range(size - 1):
    for j in range(size - 1 - i):
      if arr[j + 1] < arr[j]:    
        arr[j + 1], arr[j] = arr[j] = arr[j + 1]
  return arr
arr = []
for _ in range(100):
  arr.append(random.randint(1, 500))
print(bubble_sort(arr))    

I hope you guys have learned how the bubble sort algorithm works. Keep learning guys :)