Design and Analysis of Algorithms

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.
In this case, the swapping is not required since they are already in ascending order
At the end of pass 2(4 and 2 are swapped)
pass 3
pass 4
pass 5 and final pass

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[0]);
bubbleSort(arr, n);
cout<<”Sorted array: \n”;
printArray(arr, n);
return 0;
}

output is :

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store