What is bubble sort?

While learning Data Structure and Algorithm (DSA) you must have come across different sorting techniques like merge sort, selection sort, insertion sort, etc. In today’s article, we will take a closer look at how bubble sort works, its history, its advantages and disadvantages, its applications, and when it should be considered over other sorting algorithms.

Introduction

Bubble sort is a simple and straightforward sorting algorithm used to sort things in a list in ascending or descending order. The working principle of the method is swapping of the very next element or the consecutive element if it is smaller than the previous one and continues till it is sorted in ascending order and vice-versa for sorting in descending order.

The algorithm starts by pointing to the first element of the inputted array, followed by comparison of the adjacent element. Two case can arise, either the first element will be larger than the second or smaller than second, they are swapped if the first element is larger. This goes same for the next pair and iterates till we reach the end of the array. Now, we start over the process from the starting of array, and follow the same above steps again and again until all the elements are sorted in the desired order.

The method is most simple but it is not efficient for large lists and one of the slowest sorting algorithm in time complexity when compared to quicksort, insertion sort, mergesort etc. However, it is an excellent algorithm to use for small lists or as a teaching tool to help understand the concept of sorting algorithms.

History of bubble sort

The exact origin of bubble sort is not known, but it is believed to have been developed in the 1950s or 1960s. It is the earliest and was a popular method during the starting days of computing. Today, bubble sort is not widely used in practice, but it is the first sorting algorithm taught if you are learning computer science or programing.

How bubble sort works

A step-by-step explanation of the sorting process is as follows:

The starting point is set at the first element of list
The two consecutive elements are compared.
Swapping occurs if first element is larger than the second.
Move to the next pair of elements and repeat step 3.
The process continues till we reach the last element of list is reached.
Start over from the beginning of the list and repeat steps 2 to 5 until no more swaps are needed.

Following is the example for the sorting technique:

Consider the array [3, 43, 15, 9, 1]. The first iteration of the bubble sort algorithm will start by comparing the first two elements of the list, and since 43 is greater than 3, they would be left as is. The array will now look like [3, 43, 15, 9, 1].

The second iteration would compare elements 43 and 15, and since 43 is greater than 15, they would be swapped. The array will be like [3, 15, 43, 9, 1].

The third iteration would compare elements 43 and 9, and since 43 is greater than 9, they would be swapped. The array would then look like [3, 15, 9, 43, 1].

The fourth iteration would compare elements 43 and 1, and since 43 is greater than 1, they would be swapped. The array would then look like [3, 15, 9, 1, 43].

The fifth iteration would start over again, comparing the first two elements (3 and 15). Since 15 is greater than 3, they would be left as is. The array would then look like [3, 15, 9, 1, 43].

The above process continus till all the elements are sorted in the array.

Here is an illustration for you to have a better understanding of the sorting method.

Bubble sort algorithm

Here is the sorting algorithm code in Python:

def bub_sort(s):
    n = len(s)
    
    for k in range(n):
        for l in range(0, n-k-1):
            if s[l] > s[l+1]:
                s[l], s[l+1] = s[l+1], s[l]
                
    return sCode language: Python (python)

The function takes an array s as input and returns a sorted version of the array. The outer loop iterates n times, and the inner loop iterates n-k-1 times, where k is the current iteration of the outer loop. The two nested loops compare adjacent elements of the array and swap them, it will go on till list is sorted.

We will call the bubble_sort function and pass the array to bes sorted to use the algorithm. For example:

srt_arr=[3, 43, 15, 9, 1]
print("List before bubble sort\n",srt_arr)
sort_list = bub_sort(srt_arr)
print("List after bubble sort\n",sort_list) Code language: Python (python)

This will return a new sorted list in ascending order. If you want to sort the list in descending order, you can modify the comparison operator in the while loop from > to <.

Click Here to try this code by yourself

Pros and Cons of bubble sort

This algorithm in comparison with other sorting techniques has the following advantages and disadvantages.

Pros:

Simple to understand and implement making it a good choice for students and novice programmers.
A stable sorting algorithm as relative positions of elements will remain unchanged after sorting.

Cons:

Slow and inefficient sorting algorithms and is not recommended for large datasets.
Not suitable for real-world applications due to its slow performance and lack of efficiency compared to other algorithms.

Applications of bubble sort

This sorting method is usually not used in real-life applications due to its bad time complexity, especially for large datasets.

Educational purposes: Bubble sort is widely used in computer science education as a teaching tool to help students understand the concept of sorting algorithms.
Testing and debugging other sorting algorithms: Bubble sort can be used to test and debug other sorting algorithms by serving as a simple and straightforward reference point.

Conclusion

To conclude today’s article, we discussed bubble sort which is a simple sorting algorithm that first checks for the greatest element and bubbles up to the end in the array by comparing to its adjacent elements and getting swapped. This process goes on till array is sorted in the desired order. Although it is one of the earliest and simplest sorting algorithms, it is also one of the slowest and is not recommended for real-world applications.

I hope you found my article helpful and that it made you one step closer to your coding journey. If you have any queries, you can comment them down below and I’ll be happy to answer them. We will be back again with another amazing article soon. Till then, keep coding, and have a great day ahead!