Bubble Sort
Bubble sort works by comparing pairs of adjacent elements repeatedly and then swapping their positions in order to make them sorted. In order to sort elements, bubble sort performs this step multiple times which are called Passes.
Let’s see this with a help of an example:
Bubble sort is popular in computer graphics for its capability to detect a very small error (like swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n).
The number of comparisons in worst case for bubble sort is N(N-1) / 2 where N is the number of elements.
Complexity
Worst and Average Case Time Complexity: O(n²). Worst case occurs when array is sorted in opposite direction.
Best Case Time Complexity: O(n). Best case occurs when array is already sorted.
Auxiliary Space: O(1)
Sorting In Place: Yes
Stable: Yes
I hope this article helped you, feel free to get connected and ask your doubts.
If you really learned something just give a try to this question and post your answers in comment section.
Write a program to find the number of swaps in Bubble Sort.
Keep Growing! Happy Learning!😊
