Bubble Sort in Data Structure

In this tutorial, You will learn bubble sort. Also, you'll C++ example of bubble sort and find complexity in terms of space and time.

Bubble Sort

Bubble sort is the data structure stable sorting algorithm. It is the algorithm in which we compare two adjacent elements and swap elements in ascending or descending order.

Bubble Sort Algorithm

In Bubble Sort, we can compare all elements one by one and sort one element at a time based on their value element. 

A few steps involved in the implementation of bubble sort are:

1. You have to start from the value of the first element index i.e. index=0. Now, Compare the element with the adjacent next elements.
2. If the first element is greater than the next element then swap both elements.
3. And If the first element is less than the next element then move to the next element i.e. index=1 and repeat steps from step 1. 

After each iteration of these 3 steps, the largest element of the unsorted elements placed at the end.

One by one each iteration one element is sort. so, we compare all elements upto the last unsorted elements.

Finally, when all unsorted elements are placed at their correct index then we can say elements are sorted.

Compare adjacent elements

Compare adjacent elements

Compare adjacent elements

Example:

C++

//C++ program for Bubble Sort
#include<iostream>
using namespace std;

void bubbleSort(int arr[], int n);
// function declaration

int main()
{
    int n, i;
     // User have to enter number of elements to be sorted
    cout<<"Enter Number of Elements to be Sorted :)";
    cin>>n;
	int arr[n];
    // Input array elements
    for(i = 0; i < n; i++)
    {
        cout<<"Enter element number: ";
        cin>>arr[i];
    }
    // Call bubbleSort function
    bubbleSort(arr, n);
    
    return 0;
}

// function definition
void bubbleSort(int arr[], int n)
{
    int pass, i, temp;
    for(pass = 0; pass < n; pass++)
    {
        for(i = 0; i < n-pass-1; i++)
        {
            if( arr[i] > arr[i+1])
            {
                // Swap logic to swap the elements
                temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            } 
        }
    }
// Print Sorted Array
    cout<<"Sorted Array :) ";
    for(i = 0; i < n; i++)
    {
       cout<<arr[i]<<" ";
    }
}

Output

Enter Number of Elements to be Sorted :)4
Enter element number: 3
Enter element number: 20
Enter element number: 10
Enter element number: 5
Sorted Array :) 3 5 10 20
--------------------------------

Complexity of Bubble Sort

The time complexity of the above algorithm is O(n^2).

Time Complexity:

1. Best Case Complexity: O(n)                                                                                                                                         If the array of the element is already sorted then we don't need sorting.
2. Average Case Complexity: O(n^2)                                                                                                                             when the elements of an array are in jumbled order.
3. Worst Case Complexity: O(n^2)                                                                                                                                    If the array of elements are present in descending order and we need to sort an array in ascending order.

Space Complexity:

Space complexity for bubble sort is always O(1) because of the extra temporary variable for a swap.

We learn more about only complexity in another tutorial and learn bubble sort in java.

In this tutorial, you learn bubble sort algorithm, and complexity of bubble sort in terms of time and space. I hope you enjoy this article.

Happy Coding 😊