Bubble Sort Algorithm

May 9, 2021, 4:37 p.m.

1) Bubble sort repeatedly steps through the list to be sorted compares each pair of adjacent items and swps them if they are in wrong order.
2) It is too slow and impractical for most problems even when compared to insertion sort.
3) Worst case & Average Case time complexity in O(N²)
4) Not a practical sorting algorithm.
5) In computer graphics it can detect a very small error.
6) Stable sorting algorithm.

After every iteration we compare and swap if the element is greater than the next.

After completion of an iteration largest element will be at the last index.

class BubbleSort:
 def __init__(self,nums):
  self.nums=nums
 def sort(self):
  for i in range( len(self.nums)-1):
   for j in range(len(self.nums)-i-1):
    if self.nums[j] >self.nums[j+1]:
     self.swap(j,j+1)
 
 def swap(self,i,j):
  self.nums[i], self.nums[j] = self.nums[j], self.nums[i]

if __name__ == '__main__':
 n = [ 1, -5, 0, 2, 3, 6, -3]
 bubble_sort = BubbleSort(n)
 print(bubble_sort.nums)

Complexity:

1) N-1 comparisons are made to place the highest element in its correct position.

2) N-2 for the second highest element.