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:
- 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.
- If the first element is greater than the next element then swap both elements.
- 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.
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
Time Complexity:
- Best Case Complexity: O(n) If the array of the element is already sorted then we don't need sorting.
- Average Case Complexity: O(n^2) when the elements of an array are in jumbled order.
- 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 😊