Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
Reading time: 20 minutes | Coding time: 10 minutes
Bubble Sort is the one of the most simple yet widely used comparison based sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
Complexity
The complexity of Bubble Sort algorithm is as follows:
- Worst case time complexity:
Ξ(N^2) - Average case time complexity:
Ξ(N^2) - Best case time complexity:
Ξ(N) - Space complexity:
Ξ(1)auxillary space
Read on to make sense of the complexity denoted above
In computer graphics, it is popular for its capability to detect a very small error (like swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n).
For example, it is used in a polygon filling algorithm, where bounding lines are sorted by their x coordinate at a specific scan line (a line parallel to x axis) and with incrementing y their order changes (two elements are swapped) only at intersections of two lines.
Algorithm
Step 1: Compare two adjacent elements and swap them if they are not in the correct order
Step 2: Do this for all elements in the list
Step 3: If even one element has been swapped in the above run of N elements, go to Step 1 and repeat the process. If no element has been swapped in the above run for N elements, stop. The list is sorted.
What is the limit to have any element swapped in a adjacent comparison run?
Example
First Pass: ( 5 1 4 2 8 ) β> ( 1 5 4 2 8 ),
Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) β> ( 1 4 5 2 8 ), Swap since 5 > 4.
( 1 4 5 2 8 ) β> ( 1 4 2 5 8 ), Swap since 5 > 2.
( 1 4 2 5 8 ) β> ( 1 4 2 5 8 ),
Now, since these elements are already in order (8 > 5), algorithm does not swap them.
Second Pass: ( 1 4 2 5 8 ) β> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) β> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) β> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) β> ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is
completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass: ( 1 2 4 5 8 ) β> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) β> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) β> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) β> ( 1 2 4 5 8 )
Implementations
Implementation of Bubble sort algorithm in 5 languages that includes C, C++, Java, Go and CSharp.
- C
- C++
- Java
- Go
- C#
C
/*Part of Cosmos by OpenGenus Foundation*/
#include <stdio.h>
typedef int bool;
#define true 1
#define false 0
void swap(int *p, int *q)
{
int temp = *p;
*p = *q;
*q = temp;
}
/*Sorting an array a[] consisting of n
elements with bubble sort method*/
void bubbleSort(int a[], 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 (a[j] > a[j + 1])
{
swap(&a[j], &a[j + 1]);
swapped = true;
}
}
if (swapped == false)
break;/*break if array is sorted
i.e. no swapping possible*/
}
}
void print(int a[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", a[i]);
printf("\n");
}
int main()
{
int n, i;
printf("What is the size of the array?\n");
scanf("%d",&n);
int a[n];
printf("Enter elements of the array one by one\n");
for(i = 0; i < n; i++){
scanf("\n%d",&a[i]);
}
bubbleSort(a, n);
printf("Sorted array: ");
print(a, n);
return 0;
}
C++
/*
Part of Cosmos by OpenGenus Foundation
bubble sort synopsis
template<typename _Bidirectional_Iter, typename _Compare>
void
bubbleSort(_Bidirectional_Iter begin, _Bidirectional_Iter end, _Compare compare);
template<typename _Bidirectional_Iter>
void
bubbleSort(_Bidirectional_Iter begin, _Bidirectional_Iter end);
*/
#include <functional>
template<typename _Bidirectional_Iter, typename _Compare>
void
bubbleSort(_Bidirectional_Iter begin, _Bidirectional_Iter end, _Compare compare)
{
if (begin != end)
{
auto frontOfSorted = end;
for (--frontOfSorted; frontOfSorted != begin; --frontOfSorted)
{
bool swapped{};
for (auto j = begin; j != frontOfSorted; ++j)
{
auto nextOfJ = j;
if (compare(*++nextOfJ, *j))
{
std::iter_swap(nextOfJ, j);
swapped = true;
}
}
if (swapped == false)
break;
}
}
}
template<typename _Bidirectional_Iter>
void
bubbleSort(_Bidirectional_Iter begin, _Bidirectional_Iter end)
{
using value_type = typename std::iterator_traits<_Bidirectional_Iter>::value_type;
bubbleSort(begin, end, std::less<value_type>());
}
Java
/* Part of Cosmos by OpenGenus Foundation */
import java.util.Arrays;
/**
* Implements the bubble sort sorting algorithm
*/
public class BubbleSort {
static void bubbleSort(int[] array) {
int flag = 1;
for (int i = 0; i < array.length - 1; i++) {
flag = 1;
for (int j = 0; j < array.length - 1; j++) {
if(array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
flag = 0;
}
}
if (flag == 1) {
break;
}
}
}
public static void main(String[] args) {
int array[] = { 4, 2, 3, 1 };
bubbleSort(array);
System.out.println("Sorted array: ");
System.out.println(Arrays.toString(array));
}
}
Go
/* Part of Cosmos by OpenGenus Foundation */
package main
import "fmt"
func bubbleSort(arrayzor []int) {
swapped := true
for swapped {
swapped = false
for i := 0; i < len(arrayzor)-1; i++ {
if arrayzor[i+1] < arrayzor[i] {
arrayzor[i], arrayzor[i+1] = arrayzor[i+1], arrayzor[i]
swapped = true
}
}
}
}
func main() {
arrayzor := []int{1, 6, 2, 4, 9, 0, 5, 3, 7, 8}
fmt.Println("Unsorted array: ", arrayzor)
bubbleSort(arrayzor)
fmt.Println("Sorted array: ", arrayzor)
}
C#
/* Part of Cosmos by OpenGenus Foundation */
using System;
using System.Linq;
namespace BubbleSortCSharp
{
class BubbleSort
{
static void sort(int[] a){
for (int i = a.Length - 1; i > 0; i--)
{
for (int j = 0; j <= i - 1; j++)
{
if (a[j] > a[j + 1])
{
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
static void Main(string[] args)
{
Console.WriteLine("Enter values to sort separated by space");
var a = Console.ReadLine().Split(' ')
.Select(i => int.Parse(i))
.ToArray();
sort(a);
Console.WriteLine("Sorted Array: ");
foreach(int item in a)
{
Console.WriteLine(item);
}
}
}
}
Applications
-
In computer graphics, it is popular for its capability to detect a very small error (like swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n).
-
Bubble sort interacts poorly with modern CPU hardware. It produces at least:
- twice as many writes as insertion sort
- twice as many cache misses
- asymptotically more branch mispredictions.
-
Bubble sort is asymptotically equivalent in running time to insertion sort in the worst case, but the two algorithms differ greatly in the number of swaps necessary.
-
Odd-Even sorts and Cocktail sorts are improvements over Bubble sort.
-
It is used in a polygon filling algorithm, where bounding lines are sorted by their x coordinate at a specific scan line (a line parallel to x axis) and with incrementing y their order changes (two elements are swapped) only at intersections of two lines.
