Bubble Sort Algorithm - Sorting Guide 101

Introduction: Bubble Sort Algorithm

Bubble Sort algorithm is one of the simplest and well-known sorting algorithms. Though it is not one of the most efficient sorting algorithms, its straight forward approach makes it an excellent starting point for anyone learning algorithms.

Bubble sort works by iterating through the given array multiple times and repeatedly swapping adjacent elements until all elements in the array are sorted. In each pass, the largest element is pushed or bubbled to its correct position towards the end of the array. Hence the name bubble sort.

Bubble sort segregates the array into two parts:

1. Sorted portion

2. Unsorted portion

Sorted elements are placed towards the end of the array. In every pass, one of the elements from unsorted portion is moved to its correct position in the sorted portion of the array. Once an element is placed in its correct sorted position, there is no need to check this element again.

Let's see how this algorithm works in detail.

Algorithm

For a given input array arr that needs to be sorted in ascending order, bubble sort does the following steps:

1. Compare adjacent elements:

   Iterate through the given array arr from start to end. In each iteration, compare adjacent elements. We start by comparing the 1st and 2nd elements in arr:

   1. If 1st element is greater than 2nd element, it means elements are not in correct order, so we swap them.

   2. If 1st element is smaller than or equal 2nd element, it means elements are in correct order. So no need to swap, continue to next iteration.

   3. In the next iteration, we compare 2nd and 3rd elements and repeat steps a and b.

   4. Next we compare 3rd and 4th elements and so on until we reach the end of array.

2. Repeat step 1 until sorted:

   The procedure described in step 1, comparing and swapping elements from start to end is known as one "pass" on the array arr.

   
   

   For each pass through the array arr, one element is bubbled to its correct position towards the end of the array. For an array of size n, we need to do n-1 such passes to make it fully sorted.

Note: In each pass, once an element is moved to its correct sorted position in the array, we don't have to consider this element again in the next pass as it is already sorted.

Note: If two elements are equal, we do not swap them, because whether we swap them or not it doesn't make any difference to the output (however if you want your algorithm to be stable, then you should not be swapping them).

Simulation

Below is a pictorial depiction of the working of the algorithm:

Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses:

1. Udemy Video Tutorials - Available at 95% off

2. System Design Interview Complete Guide

3. Cracking The Coding Interview - Most Preferred Book For Coding Interviews

4. Data Structures And Algorithms - A Complete Guide

5. Learn In-Demand Tech Skills And Stay Ahead Of Others

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

TypeScript Solution

C++ Solution

C# Solution

C Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

Scala Solution

Rust Solution

Complexity Analysis

Time Complexity

The worst case time complexity for bubble sort algorithm is  O(n²) since we have to run two loops to implement it and in the worst case we would end up making nearly  O(n²) comparisons to get the final sorted array.

Therefore the worst case time complexity of this algorithm is  O(n²). The worst case occurs when the input array is in non-increasing or descending order.

The best case time complexity of bubble sort is  O(n). The best case occurs when the input array is already sorted. Bubble sort just needs one pass in this case to determine that the array is already sorted.

Space Complexity

Bubble sort does not use any extra space to sort the given array, it sorts the given array in place. So the space complexity is O(1).

Conclusion

Bubble sort works well for large arrays where the given data is mostly sorted since it takes just one pass on the array to determine if the array is already sorted. But if most elements in the array are not sorted and if it is a large array, then it is not preferred to use bubble sort as it is not efficient, algorithms like quick sort would be a better choice in such cases. Bubble sort is only useful for very small and nearly sorted arrays.

Now you know how bubble sort works. Don't stop here, you can explore more sorting algorithms from code recipe here.

That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you.

If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form).

You can explore more such amazing articles from code recipe in our blogs section. You can explore more algorithms in our algorithms section.

Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.

Follow us: YouTube, Facebook, Twitter, LinkedIn, Tumblr, Instagram.