What Is Bubble Sort Algorithm in Data Structure?

When it comes to sorting algorithms, the bubble sort algorithm is one of the simplest and most widely known. It is an elementary sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. In this article, we will explore how the bubble sort algorithm works and its time complexity.

How Bubble Sort Works

The bubble sort algorithm gets its name from the way smaller elements “bubble” to the top of the list. The basic idea behind this algorithm is to repeatedly compare adjacent elements and swap them if they are in the wrong order.

Let’s take a look at an example to understand how bubble sort works:

• Step 1: Start with an unsorted list of numbers: [7, 3, 9, 2]
• Step 2: Compare the first two elements (7 and 3). As 7 is greater than 3, swap them: [3, 7, 9, 2]
• Step 3: Compare the next two elements (7 and 9).

  They are already in order.

• Step 4: Compare the next two elements (9 and 2). As 9 is greater than 2, swap them: [3, 7, 2, 9]

This completes one pass of the list. Now we repeat these steps until the list is sorted.

Pseudocode for Bubble Sort Algorithm

The pseudocode for bubble sort can be written as follows:

function bubbleSort(list)
    n = length(list)
    for i = 0 to n-1
        for j = 0 to n-i-1
            if list[j] > list[j+1]
                swap(list[j], list[j+1])

The outer loop runs from 0 to n-1, where n is the length of the list. The inner loop compares adjacent elements and swaps them if they are in the wrong order. This process is repeated until the entire list is sorted.

Time Complexity of Bubble Sort

The time complexity of bubble sort algorithm is O(n^2), where n is the number of elements in the list. This means that as the size of the input increases, the time taken by bubble sort grows quadratically.

Although bubble sort is simple to understand and implement, it is not efficient for large lists or datasets. Other sorting algorithms, such as quicksort or mergesort, have better average and worst-case time complexities.

Conclusion

Bubble sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements until the entire list is sorted. It has a time complexity of O(n^2), which makes it inefficient for large datasets. However, it serves as a good introduction to sorting algorithms and can be used for small lists or educational purposes.