Hi everybody and welcome.
Learning about computer algorithms is very important in today's world. If you want to learn the computer then you definitely got to learn about the design and analysis of computer algorithms.
Within algorithms, a very important subtopic is “Sorting Algorithm” and in today's blog we are going to learn about the most important and basic form of sorting called “Bubble Sorting Algorithm”
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
- 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.
- Now, compare the second and the third elements. Swap them if they are not in order.
- The above process goes on until the last element.
This entire process of checking and swapping for one time is called a “pass” or an “iteration”.
We can vividly notice that with one pass the entire array is not fully sorted as we intended.
The same process goes on for the remaining iterations. After each iteration, the largest element among the unsorted elements is placed at the end.
In each iteration, the comparison takes place up to the last unsorted element.
The array is sorted when all the unsorted elements are placed at their correct positions.
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:
1 2 4 5 8 9
But, implementing the above algorithm takes too long because all the possible comparisons are made even if the array is already sorted.
we need to reduce the execution time by optimizing the code by introducing an extra variable called “swapped”. This variable helps in stopping the algorithm if the inner loop didn’t cause any swap.
optimized bubble sort :
// Optimized implementation of Bubble sort
#include <stdio.h>
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// An optimized version of Bubble Sort
void bubbleSort(int arr[], int n)
{
int i, j;
bool swapped;
for (i = 0; i < n-1; i++)
{
swapped = false;
for (j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
swap(&arr[j], &arr[j+1]);
swapped = true;
}
}
// IF no two elements were swapped by inner loop, then break
if (swapped == false)
break;
}
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf(“%d “, arr[i]);
printf(“n”);
}
// Driver program to test above functions
int main()
{
int arr[] = {5, 1, 4, 2, 8, 9};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
printf(“Sorted array: \n”);
printArray(arr, n);
return 0;
}
Complexity
we can analyze the complexity by simply observing the number of loops. There are 2 loops so the complexity is n*n=n².
Total number of comparisons : (n — 1) + (n — 2) + (n — 3) +…..+ 1 =
n(n — 1) /2 . This nearly equals 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
Best Case Complexity: O(n)
If the array is already sorted, then there is no need for sorting.
Space Complexity:
Space complexity is O(1) because an extra“temp” variable is used for swapping.
In the optimized algorithm, the “swapped” variable adds to the space complexity thus, making it O(2)
