Bubble Sort

#dsa #python #codenewbie #beginners

Hi Everyone, Hope you are safe.
I thought to create a series of sorting algorithms. I will try my best to make it simple. If you still have doubt let me know in the comment section.

Let's begin........

Background:

Bubble sort is the simplest algorithm. This is used for understanding purpose of a student. How the sorting algorithms works.
Bubble sort is good for small size of input.

What is Bubble sort:
Take the larger number to the end and repeatedly swapping the adjacent elements.

Examples:
arr = [4, 8, 1, 2, 6, 7]
First times:

[4, 8, 1, 2, 6, 7] -> it compares between first and 2nd element i.e, 4>8. it is false. so, it didn't swap.
[4, 8, 1, 2, 6, 7] -> it compares between 2nd and 3rd element i.e 8>1. Now array is [4, 1, 8, 2, 6, 7].same way it will go for others array values.
[4, 1, 8, 2, 6, 7] -> [4, 1, 2, 8, 6, 7], 8>2,swapped it.
[4, 1, 2, 8, 6, 7] -> [4, 1, 2, 6, 8, 7], 8>6,swapped it.
[4, 1, 2, 6, 8, 7] -> [4, 1, 2, 6, 7, 8], 8>7,swapped it.

Second times:

[4, 1, 2, 6, 7, 8] -> [1, 4, 2, 6, 7, 8], 4>1,swapped it.
[1, 4, 2, 6, 7, 8] -> [1, 2, 4, 6, 7, 8], 4>2,swapped it.
[1, 2, 4, 6, 7, 8] -> [1, 2, 4, 6, 7, 8], elements(4 & 6) are already in correct position so it did not swap.
[1, 2, 4, 6, 7, 8] -> [1, 2, 4, 6, 7, 8], elements(6 & 7) are already in correct position so it did not swap.

It will go for other iterations. Check the below illustration for better understanding.

We can see that larger element is going at end position using this algorithm.

Let's implement so far we discussed:

output:

Time complexity:
The time complexity of this algorithm is O(n^2) for worst case.

when times=0 we iterate till n-1 where n = len(arr).
when times=1 we iterate till n-2 where n = len(arr).
when times=2 we iterate till n-3 where n = len(arr).
and so no.........

Based on above iteration, we calculated the time complexity.

Optimization: As per the above code, time complexity would be O(n^2) even though array is in sorted order. Because the inner loop always iterate and swap the value. If we stop the swapping then the time complexity would be O(n) for sorted array.

Output:

Worst and Average Case Time Complexity: O(n^2). worst case occurs when array is in descending order.
Best Case Time Complexity: O(n) when array is in sorted order.
Space Complexity: There is no extra array or something else so space complexity should be O(1).
Stable: Yes