Bubble Sort


Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order. 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.

Complexity

  • Worst case time complexity: O(N^2)
  • Average case time complexity: O(N^2)
  • Best case time complexity: O(N)
  • Space complexity: O(1) auxillary space

Overview

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, and 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.