Bubble Sort Algorithm

How does Bubble Sort Work?

Let’s see bubble sort in action. 

Consider an unsorted integer array A = [6,5,8,1,2].

Now, we will use the bubble sort algorithm to sort it in ascending order. 

Here, the number of elements N = 5, so there will be a total of N-1, i.e., four iterations.

1. First Iteration

• Compare A[0] = 6 and A[1] = 5 in [6,5,8,1,2]. Since, 6>5, So we swap them, getting [5,6,8,1,2].
   
• Compare A[1]=6 and A[2]=8 in  [5,6,8,1,2]. Since, 6<8, So, no need to swap. 
   
• Compare A[2]=8 and A[3]=1 in  [5,6,8,1,2]. Since, 8>1, so we need to swap, getting  [5,6,1,8,2]
   
• Compare A[3]=8 and A[4]=2 in [5,6,1,8,2]. Since, 8>2, so we get [5,6,1,2,8]

If you observe, you will see that the greatest element(here, 8) has reached the end of the array, which is its correct position in the sorted array. From the next iteration onwards, we will compare the elements only till the second last position, as the last element is already at its correct place.

2. Second Iteration

• Compare A[0]=5 and A[1]=6 in [5,6,1,2,8]. Since, 5<6, so, no need to swap; they are in the correct order.
• Compare A[1]=6 and A[2]=1 in  [5,6,1,2,8]. Since, 6>1, so we swap them, getting [5,1,6,2,8]. 
• Compare A[2]=6 and A[3]=2 in  [5,1,6,2,8]. Since, 6>2, so we need to swap, getting [5,1,2,6,8].

Notice that 6 is now in the correct position. 

3. Third Iteration

• Compare A[0]=5 and A[1]=1 in [5,1,2,6,8]. Since, 5>1, so we swap them, getting [1,5,2,6,8].
• Compare A[1]=5 and A[2]=2 in  [1,5,2,6,8]. Since 5>2, so we swap them, getting [1,2,5,6,8]. 

Now, 5 is in its correct place. 

4. Fourth Iteration

• Compare A[0]=1 and A[1]=2 in [1,2,5,6,8]. Since, 1<2, so there is no need to swap.
   

The figure below illustrates the steps followed above:

Finally, you can see that the array is sorted.

Implementation of Bubble Sort

In the typical bubble sort algorithm, the outer loop continues to execute even if we don't perform any swap operation in the inner loop. So, essentially, there will be no swapping if the elements are already sorted. 

To avoid these unnecessary comparisons, we can keep a flag set to false. If any swap is performed, it is set to true; otherwise, it remains false. 

Then at each iteration of the outer loop, we just need to check if the flag is false, we break the loop, or else we continue. 

In the next section, we will see the implementation of the bubble sort algorithm along with the space and time complexity. 

Implementation in C

/* C Implementation of Bubble Sort Algorithm */
#include <stdio.h>


/* Function for printing an array of length n */
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}


void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}


void bubbleSortAlgorithm(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
                swap(&arr[j], &arr[j + 1]);
        }
    }
}


// Driver code
int main()
{
    int arr[] = {6, 5, 8, 1, 2};
    int N = sizeof(arr) / sizeof(arr[0]);
    bubbleSortAlgorithm(arr, N);
    printf("The array performing the Bubble Sort Algorithm is:\n");
    printArray(arr, N);
    return 0;
}

Implementation in Python

# Python Implementation of Bubble Sort Algorithm


def bubbleSortAlgorithm(array):
    
  for i in range(len(array)):


    for j in range(0, len(array) - i - 1):


      if array[j] > array[j + 1]:


        temp = array[j]
        array[j] = array[j+1]
        array[j+1] = temp


data = [6, 5, 8, 1, 2]


bubbleSortAlgorithm(data)


print('The array performing the Bubble Sort Algorithm is:')
print(data)

Implementation in Java

// Java Implementation of Bubble Sort Algorithm


import java.util.Arrays;


class Main {


  static void bubbleSortAlgorithm(int array[]) {
    int size = array.length;
    
    for (int i = 0; i < size - 1; i++)
    
      for (int j = 0; j < size - i - 1; j++)


        if (array[j] > array[j + 1]) {


          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
        }
  }


  public static void main(String args[]) {
      
    int[] data = { 6, 5, 8, 1, 2 };
    Main.bubbleSortAlgorithm(data);
    System.out.println("The array performing the Bubble Sort Algorithm is:");
    System.out.println(Arrays.toString(data));
  }
}

Implementation in C++

/* C++ Implementation of the Bubble Sort Algorithm */
#include <bits/stdc++.h>
using namespace std;

void bubbleSortAlgorithm(int arr[], int n)
{
    int i, j;
    bool flag;
    for (i = 0; i < n - 1; i++)
    {
        flag = false;
        for (j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
                flag = true;
            }
        }

        // If no swapping is performed, then we break the loop
        if (flag == false)
            break;
    }
}

// Function for printing an array of length n
void printArr(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// Driver Program
int main()
{
    int arr[] = {6, 5, 8, 1, 2};
    int N = sizeof(arr) / sizeof(arr[0]);
    bubbleSortAlgorithm(arr, N);
    cout << "The array performing the Bubble Sort Algorithm is:\n";
    printArr(arr, N);
    return 0;
}

Output

The array performing the Bubble Sort Algorithm is:
1 2 5 6 8

Complexity Analysis of Bubble Sort

In this section, we will have a look at the time and space complexities of the bubble sort algorithm.

Time Complexity

The time complexity of the bubble sort algorithm is O(n²), where n is the number of elements present in the given array.

You can see that we use two nested loops for sorting. The inner loop can run up to n times, and the outer loop can also run up to n times in the worst case. Hence, the total number of comparisons will be O(n*n); thus, time complexity will be O(n*n) which is O(n²).

The best case occurs when the array is already sorted. So, the best case time complexity is O(n), as we need at least a single pass to know that no swapping has been performed. 

The worst case occurs when the array elements are sorted in reverse order, which implies that the algorithm will not finish before O(n²) operations. 

Space Complexity

The space complexity of the bubble sort algorithm is O(1). 

Since the algorithm uses only a constant amount of space for the loop variables and an extra variable to store the swapping status.

Moreover, bubble sort is an in-place sorting algorithm which implies that it manipulates the original array for sorting. 

Applications of Bubble Sort Algorithm

Several applications of Bubble Sort Algorithm are as follows:

• Educational Purpose: Bubble Sort is frequently used in computer science classes to teach fundamental sorting algorithms and algorithm analysis.
   
• Small Data Sets: It may be appropriate for sorting small arrays or lists because of its simplicity, which makes it simpler to use and comprehend.
   
• Debugging: Due to its simplicity in implementation and debugging, Bubble Sort can occasionally be used as a stepping stone for troubleshooting more complicated sorting algorithms.
   
• Adaptive Sorting: Bubble Sort is adaptive; it improves in effectiveness when dealing with partially sorted data. It can function reasonably effectively in scenarios when the data is mostly sorted.
   

Advantages of Bubble Sort Algorithm

Some of the advantages of the bubble sort algorithm are:

• It's a very simple algorithm.
   
• Memory efficient.
   
• Detects early when the input is already sorted.
   
• It is very intuitive to understand.
   
• Bubble sort swaps the elements without any extra memory requirements.
   
• Bubble sort code is very small and simple computer program.

Disadvantages of Bubble Sort Algorithm

Some of the disadvantages are:

• Time Complexity is high.
   
• It is majorly suitable for academic teaching purposes only.
   
• It does not work well for real-life applications.
   
• Not suitable for larger inputs.
   
• Prims and Kruskal Algorithm

Frequently Asked Questions

What are the 5 steps of bubble sort? 

A basic sorting algorithm called Bubble Sort has five steps: comparing nearby entries, swapping them if they are in the wrong order, moving on to the next pair, repeating this process until there are no swaps in a pass, and iterating over all of the elements until the list is sorted.

Why is it called bubble sort algorithm? 

Bubble Sort get its name because smaller elements "bubble" to the top of the list during each pass. The smaller values gradually move to the top of the list in each iteration, mimicking bubbles rising to the surface. Adjacent components are compared and swapped if they are out of order.

What is the formula for bubble sort algorithm?

On average, Bubble sort requires n/2 passes and O(n) comparisons for each pass. So, the formula for computing the time complexity of bubble sort is O(n/2*n) = O(n^2), where n is the total number of elements in the list.

Conclusion

In this article, we discussed the bubble sort algorithm from scratch, starting with the introduction followed by the working of the algorithm with the help of an example. We also learned the optimized bubble sort algorithm's implementation and the time and space complexity analysis. 

We hope this blog has helped you enhance your knowledge regarding the bubble sort algorithm. 

Do upvote our blog to help other ninjas grow.

Happy Coding!‍