Bubble Sort

bubble sort

Bubble sort is the simplest sorting algorithm. This sorting algorithm is the easiest algorithm to understand but this algorithm is not suited for large set of data as its complexity is Ο(n2) . Bubble sort is comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order.

Some Important points :

  • It is very simple algorithm to understand.
  • It is a comparison based algorithm.
  • Its average and worst case complexity is Ο(n2) where n is the number of items.

Working of Bubble Sort?

Let us take an example of set of items :  [3  , 6  , 4 , 7 , 2 ]

First Pass:

[3  , 6  , 4 , 7 , 2 ]

Here Algorithm compares first two elements of the set and as 6 > 3 ,so no swapping happens in this step.

[3  , 6  , 4 , 7 , 2 ]

Now 3rd element is lesser than second element , 4 < 6 so 6 is swapped with 4.

[3  , 4  , 6 , 7 , 2 ]

Now 4th element is greater than third element , 7 > 6 so no swapping happens in this step.

[3  , 4  , 6 , 7 , 2 ]

Now 5th element is lesser than 4th element, 2 < 7 so 2 is swapped with 7.

[3  , 4  , 6 , 2 , 7]

Second Pass: Same steps are performed in second pass also.

[3  , 4  , 6 , 2 , 7]

4 > 3, so no swapping done.

[3  , 4  , 6 , 2 , 7]

6 > 4, so no swapping is done.

[3  , 4  , 6 , 2 , 7]

2 < 6, so 2 is swapped with 6.

[3  , 4  , 2 , 6 , 7]

7 > 6, so no swapping is done.

Third Pass: Same steps are performed in third pass also.

[3  , 4  , 2 , 6 , 7]

4 > 3, so no swapping done.

[3  , 4  , 2 , 6 , 7]

2 < 4, so 2 is swapped with 4.

[3  , 2  , 4 , 6 , 7]

6 >  4, so no swapping is done.

[3  , 2  , 4 , 6 , 7]

7 > 6, so no swapping is done.

Fourth Pass: Same steps are performed in fourth pass also.

[3  , 2  , 4 , 6 , 7]

2 < 3, so 2 is swapped with 3.

[2  , 3  , 4 , 6 , 7]

4 > 3, so no swapping is done.

[2  , 3  , 4 , 6 , 7]

6 > 4 , so no swapping is done.

[2  , 3  , 4 , 6 , 7]

7 > 6 , so no swapping is done.

Now, we can see that the array is already sorted, but our algorithm will take one more step to know if it is completed. The Bubble Sort algorithm needs one whole pass without any swap to know it is sorted.

Fifth Pass: Same steps are performed in fifth pass also.

[2  , 3  , 4 , 6 , 7]

3 > 2 , no swapping.

[2  , 3  , 4 , 6 , 7]

4> 3, no swapping.

[2  , 3  , 4 , 6 , 7]

6 > 4 , no swapping.

[2  , 3  , 4 , 6 , 7]

7 > 6 , no swapping.

Final Sorted Array : [2  , 3  , 4 , 6 , 7]

Algorithm of Bubble Sort

In below algorithm , we have assumed that elements is the array containing n elements to be sorted and swapFunction is the function which swaps the elements passed in its arguments.

begin BubbleSort(elements)

for all item of elements
   if elements[i] > elements[i+1]
     swapFunction(elements[i], elements[i+1])
   end if
end for

return elements

end BubbleSort

Implementation of Bubble Sort in Java

// Java program for implementation of Bubble Sort 
public class BubbleSortEx 
{ 
	void bubbleSort(int elements[]) 
	{ 
		int l = elements.length; 
		for (int i = 0; i < l-1; i++) 
			for (int j = 0; j < l-i-1; j++) 
				if (elements[j] > elements[j+1]) 
				{ 
					// swap the elements[j+1] and elements[i] 
					int temp = elements[j]; 
					elements[j] = elements[j+1]; 
					elements[j+1] = temp; 
				} 
	} 

	/* Method to Print the elements */
	void printElements(int elements[]) 
	{ 
		int n = elements.length; 
		for (int i=0; i<n; ++i) 
			System.out.print(elements[i] + " , "); 
		System.out.println(); 
	} 

	// Main method
	public static void main(String args[]) 
	{ 
		BubbleSortEx bs = new BubbleSortEx(); 
		int elements[] = {5, 2, 3, 6, 1, 4, 8}; 
		System.out.println("Actual list of elements"); 
	    bs.printElements(elements); 
		bs.bubbleSort(elements); 
		System.out.println("Sorted list of elements"); 
		bs.printElements(elements); 
	} 
}
Output :

Actual list of elements
5 , 2 , 3 , 6 , 1 , 4 , 8 , 
Sorted list of elements
1 , 2 , 3 , 4 , 5 , 6 , 8 ,

Implementation of Bubble Sort in C / C++

// C program for implementation of Bubble sort

#include <stdio.h>

void swapFunc(int *ap, int *bp) 
{ 
int temp = *ap; 
*ap = *bp; 
*bp = temp; 
}

// function to implement bubble sort 
void bubbleSort(int elements[], 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 (elements[j] > elements[j+1]) 
swapFunc(&elements[j], &elements[j+1]); 
}

/* Function to print the array */
void printArray(int elements[], int n) 
{ 
int i; 
for (i=0; i < n; i++){ 
printf("%d ", elements[i]); 
printf(","); }

}

// Main function
int main() 
{ 
int elements[] = {5, 2, 3, 6, 1, 4, 8}; 
int n = sizeof(elements)/sizeof(elements[0]); 

printf("Actual list of elements: \n"); 
printArray(elements, n); 

bubbleSort(elements, n); 

printf("\nSorted list of elements: \n"); 
printArray(elements, n); 

return 0; 
}

Output :

Actual list of elements: 
5 ,2 ,3 ,6 ,1 ,4 ,8 ,
Sorted list of elements: 
1 ,2 ,3 ,4 ,5 ,6 ,8 ,

Implementation of Bubble Sort in Python

# Python program for implementation of Bubble Sort 

def bubbleSort(elements): 
l = len(elements) 

# Traverse through all elements 
for i in range(l): 

# Last i elements are already in place 
for j in range(0, l-i-1): 

# traverse the array from 0 to l-i-1 
# Swap if the element is greater than the next element 
if elements[j] > elements[j+1] : 
elements[j], elements[j+1] = elements[j+1], elements[j] 

# Main code to test the bubble sort 
elements = [5, 2, 3, 6, 1, 4, 8]

print ("Actual list of elements is:") 
for i in range(len(elements)): 
print ("%d" %elements[i]), 

bubbleSort(elements) 

print ("\nSorted list of elements is:") 
for i in range(len(elements)): 
print ("%d" %elements[i]),
Output :

Actual list of elements is:
5 2 3 6 1 4 8 
Sorted list of elements is:
1 2 3 4 5 6 8

Implementation of Bubble Sort in C# / C Sharp

// C# program for implementation of Bubble Sort 
using System; 

class Test 
{ 
static void bubbleSort(int []elements) 
{ 
int l = elements.Length; 
for (int i = 0; i < l - 1; i++) 
for (int j = 0; j < l - i - 1; j++) 
if (elements[j] > elements[j + 1]) 
{ 
// swap the elements
int temp = elements[j]; 
elements[j] = elements[j + 1]; 
elements[j + 1] = temp; 
} 
} 

/* Prints the elements */
static void printArray(int []elements) 
{ 
int l = elements.Length; 
for (int i = 0; i < l; ++i) 
Console.Write(elements[i] + " "); 
Console.WriteLine(); 
} 

// Main method 
public static void Main() 
{ 
int []elements = {5, 2, 3, 6, 1, 4, 8}; 

Console.WriteLine("Actual list of elements is :"); 
printArray(elements); 

bubbleSort(elements); 

Console.WriteLine("Sorted list of elements is :"); 
printArray(elements); 
} 

} 

Output : 

Actual list of elements is :
5 2 3 6 1 4 8 
Sorted list of elements is :
1 2 3 4 5 6 8

Implementation of Bubble Sort in Php

<?php 
// PHP program for implementation of Bubble Sort

function bubbleSort(&$elements) 
{ 
$l = sizeof($elements);

// Traverse through all elements 
for($i = 0; $i < $l; $i++) 
{ 
// Last i elements are already in place 
for ($j = 0; $j < $l - $i - 1; $j++) 
{ 
// traverse the array from 0 to n-i-1 
// Swap if the element is greater than the next element 
if ($elements[$j] > $elements[$j+1]) 
{ 
$temp = $elements[$j]; 
$elements[$j] = $elements[$j+1]; 
$elements[$j+1] = $temp; 
} 
} 
} 
}


$elements = array(5, 2, 3, 6, 1, 4, 8); 
$l = sizeof($elements);

echo "Actual list of elements is : \n";

for ($i = 0; $i < $l; $i++) 
echo $elements[$i]." "; 

bubbleSort($elements);

echo "\nSorted list of elements is : \n";

for ($i = 0; $i < $l; $i++) 
echo $elements[$i]." ";

?>

Output :

Actual list of elements is : 
5 2 3 6 1 4 8 
Sorted list of elements is : 
1 2 3 4 5 6 8
Best Case Time Complexity O(n). Best case occurs when array is already sorted.
Worst and Average Case Time Complexity O(n*n). Worst case occurs when array is reverse sorted.
Boundary Cases Bubble sort takes minimum time (Order of n) when elements are already sorted.
Auxiliary Space O(1)
Sorting In Place YES
Stable YES

Thanks a lot for reading this article.

If you have any query / suggestion / feedback, please post the same into below comment box. You can also connect directly with me through social media icons placed on top of this page.

Happy Reading!!!!

Leave a Reply

Your email address will not be published. Required fields are marked *