# 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.

## 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.