Bubble Sort Algorithm - OpenGenus IQ

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

Algorithm

Example

Complexity

Implementations

Applications

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?

log N

N/2

N^2

Consider the case that the smallest element is at the right side while it should be in the right side. On adjacent comparison run from left to right, the last element will be able to move by one place each run and it has to move N places. Hence, the limit is N

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.