# Bubble Sorting

Bubble sort, sometimes referred to as sinking sort, is a sorting algorithm that compares the adjacent elements and swaps their positions if they are not in the intended order. The order can be ascending or descending or alphabetical.

# How does Bubble Sort work?

For instance, let us assume an example of an array that requires sorting in ascending order

1. Starting from the first index, compare the first and the second elements. If the first element is greater than the second element, they are swapped.
2. Now, compare the second and the third elements. Swap them if they are not in order.
3. The above process goes on until the last element.

# Implementation of Bubble sorting algorithm in Cpp

#include <bits/stdc++.h>
using namespace std;

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

// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)

// Last i elements are already in place
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}

/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << “ “;
cout << endl;
}

// Driver code
int main()
{
int arr[] = {5, 1, 4, 2, 8, 9};
int n = sizeof(arr)/sizeof(arr);
bubbleSort(arr, n);
cout<<”Sorted array: \n”;
printArray(arr, n);
return 0;
}

Sorted array:

## optimized bubble sort :

// Optimized implementation of Bubble sort
#include <stdio.h>

# Complexity

we can analyze the complexity by simply observing the number of loops. There are 2 loops so the complexity is n*n=n².

## Complexity: O(n²)

Worst Case Complexity: O(n²)
This case is possible when we want to sort in ascending order and the array is in descending order or vice versa

--

--