DEV Community

Cover image for Bubble Sort
Payalsasmal
Payalsasmal

Posted on

Bubble Sort

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.

bubble sort explanation

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

Let's implement so far we discussed:

bubble sort code

output:
output of bubble sort

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.

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.

optimized code

Output:
optimized 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

Top comments (2)

Collapse
 
thekrprince profile image
Kumar Prince

Great article.⚡

Collapse
 
payalsasmal profile image
Payalsasmal

Thank you 😊