Given an array of integer values sort those values using bubble sort algorithm.
Bubble Sort is a simple algorithm to sort an array of integers by comparing and swapping the side-by-side elements to keep the maximum element at the end for every iteration. Please check the below example for a better understanding.
Input = {40, 20, 30, 9, 81, -1, 47}
Output = {-1, 9, 20, 30, 40, 47, 81}
As you can see above output array is in ascending sorted order.
For better understanding please check the below illustration of how algorithm flows.
40 | 20 | 30 | 9 | 81 | -1 | 47 |
As 40 > 20 they swap their positions as shown in picture.
20 | 40 | 30 | 9 | 81 | -1 | 47 |
20 | 40 | 30 | 9 | 81 | -1 | 47 |
As 40 > 30 they swap their positions as shown in right.
20 | 30 | 40 | 9 | 81 | -1 | 47 |
20 | 30 | 40 | 9 | 81 | -1 | 47 |
As 40 > 9 they swap their positions as shown in right.
20 | 30 | 9 | 40 | 81 | -1 | 47 |
20 | 30 | 9 | 40 | 81 | -1 | 47 |
As 40 < 81 they won’t change their positions.
20 | 30 | 9 | 40 | 81 | -1 | 47 |
20 | 30 | 9 | 40 | 81 | -1 | 47 |
As 81 > -1 they swap their positions as shown in right.
20 | 30 | 9 | 40 | -1 | 81 | 47 |
20 | 30 | 9 | 40 | -1 | 81 | 47 |
As 81 > 47 they swap their positions as shown in right.
20 | 30 | 9 | 40 | -1 | 47 | 81 |
The above steps are for on iteration in which the maximum number (i.e., 81) in the array moved to the right edge of the array. Next iteration will be run on N-1 elements in the array on which the highest number among those will be moved to position. We need to process all the N iterations to make a complete array in ascending order.
Below “C” code solves the bubble sorting
#include <iostream>
using namespace std;
/*
* For swaping two input elements.
*/
void swap(int &a, int &b)
{
int temp;
temp = a;
a = b;
b = temp;
}
void bubbleSortAlgo(int inp[], int len)
{
for(int i=0; i<len; i++)
{
for(int j=0; j<len-i-1; j++)
{
if(inp[j] > inp[j+1])
swap(inp[j], inp[j+1]);
}
}
}
void printArray(int inp[], int len)
{
for(int i=0; i<len; i++)
{
cout<<inp[i]<<" ";
}
cout<<endl;
}
int main(int argc, char* argv[])
{
int inp[] = {40, 20, 30, 9, 81, -1, 47};
int len = sizeof(inp) / sizeof(inp[0]);
cout<<"Input Array: "<<endl;
printArray(inp, len);
bubbleSortAlgo(inp, len);
cout<<endl<<"Sorted Array: "<<endl;
printArray(inp, len);
return 0;
}
Output:
Input Array:
40, 20, 30, 9, 81, -1, 47
Sorted Array:
{-1, 9, 20, 30, 40, 47, 81}
Complexity: ,
Space:
This is the end of the Bubble sort algorithm. If you have any better solution or any errors observed in the code, please let our readers know it by commenting here below, Cheers!