Bubble Sort

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.

402030981-147

As 40 > 20 they swap their positions as shown in picture.

204030981-147
after swapping 20 & 40
204030981-147

As 40 > 30 they swap their positions as shown in right.

203040981-147
after swapping 30 & 40
203040981-147

As 40 > 9 they swap their positions as shown in right.

203094081-147
after swapping 9 & 40
203094081-147

As 40 < 81 they won’t change their positions.

203094081-147
no swap 40 & 81 remains at same position
203094081-147

As 81 > -1 they swap their positions as shown in right.

2030940-18147
after swapping -1 & 81
2030940-18147

As 81 > 47 they swap their positions as shown in right.

2030940-14781
after swapping 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 (N-1)th 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: O(n^2),
Space: O(n)

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!