Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order. The pass through the list is repeated until the list is sorted.
How Bubble Sort Works?
Starting from the first index, compare the first and the second elements.If the first element is greater than the second element, they are swapped.
Now, compare the second and the third elements. Swap them if they are not in order.
The above process goes on until the last element.
The same process goes on for the remaining iterations. After each iteration, the largest element among the unsorted elements is placed at the end.
In each iteration, the comparison takes place up to the last unsorted element.
The array is sorted when all the unsorted elements are placed at their correct positions.
Number of comparisons: (n – 1) + (n – 2) + (n – 3) +…..+ 1 = n(n – 1) / 2 nearly equals to n2
Python Program For Bubble Sort