What is the Bubble Sort in DSA? with Free Notes

Overview

Bubble Sort is the simple sorting algorithm which repeatedly steps through the list, and compare adjacent elements , and swaps them if they are in the wrong order this Process is repeated until the list is sorted.

Key Characterstics

1. Time Complexity: – O(n²) is the worst and average case; O(n) in the best case when the array is already sorted.
2. Space Complexity: – O(1) (in – place sorting)
3. Stability: – Stable (does not change the relative order of equal elements).
4. Algorithm Type:- It is Comparison-based sorting.

How Bubble Sort works ???

1. Pass through the list:-
   • Start at the beginning of the list.
   • Compare the first two elements.
   • If the First element is greater than the second, swap them.
   • Move to the next pair of elements and repeat the comparison and swap if necessary.
   • Continue this process until the end of the list.
2. Repeat: –
   • After the first pass, the largest element will be at the end of the list.
   • Repeat the process for the rest of the list, excluding the last sorted element.
   • Continue until no more swaps are needed.

Steps and Example

Consider the Following unsorted example: –

[5, 3, 8, 4, 2]

1. Pass : 1
   • First we compare the “5” and “3” : Swap since “5 > 3” -> [3, 5, 8, 4, 2]
   • Second we going to compare “5” and “8” : No swap since “5 < 8” -> [3, 5, 8, 4, 2]
   • Third compares “8” and “4” : Swap since “8 >4” -> [3, 5, 4, 8, 2]
   • Lastly, compare “8” and “2” : Swap since “8 > 2” -> ]3, 5, 4, 2, 8]
2. Pass : 2
   • First we compare the “3” and “5” : No Swap needed “3 > 5” -> [3, 5, 4, 2, 8]
   • Second we going to compare “5” and “4” : swap since “5 < 4” -> [3, 4, 5, 2, 8]
   • Third compares “5” and “2” : Swap since “5 >2” -> [3, 4, 2, 5, 8]
   • No need to compare the last element (“8”), as it already in its correct position.
3. Pass : 3
   • First we compare the “3” and “4” : No Swap needed “3 < 4” -> [3, 4, 2, 5, 8]
   • Second we going to compare “4” and “2” : swap since “4 > 2” -> [3, 2, 4, 5, 8]
   • The last two elements (“5” and “8”) are already sorted.
4. Pass : 4
   • Here We are going to compare the “3” and “2” : Swap Since “3 > 2” -> [2, 3, 4, 5, 8]
   • The List is Now Sorted…

Hand Notes of Bubble Sort Algorithm

Join Us

• Instagram
• Telegram
• YouTube