Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. (Wikipedia)

Worst case performance - O(n^2)

Source - Wikipedia

C++

void bubble_sort(int array[], int length)
{
    bool swapped;
    do
    {
        swapped = false;
        for (int i = 1; i < length; i++)
        {
            if (array[i - 1] > array[i])
            {
                int temp = array[i];
                array[i] = array[i - 1];
                array[i - 1] = temp;
                swapped = true;
            }
        }

    }
    while (swapped);
}

Java

public int[] bubble_sort(int[] array) {
    boolean swapped;
    do {
        swapped = false;
        for (int i = 1; i < array.length; i++) {
            if (array[i - 1] > array[i]) {
                int temp = array[i];
                array[i] = array[i - 1];
                array[i - 1] = temp;
                swapped = true;
            }
        }

    } while (swapped);
    return array;
}

Matlab

function array = bubble_sort(array)
    length = numel(array);
    swapped = true;
    while swapped
        swapped = false;
        for i=2:length
            if array(i-1)>array(i)
                array([(i-1) i]) = array([i (i-1)]);
                swapped = true;
            end
        end
    end
end

Python

def bubble_sort(array):
  swapped = True
 
  while swapped:
    swapped = False
   
    for i in range(1,len(array)):
      if array[i-1]>array[i]:
        temp = array[i]
        array[i] = array[i - 1]
        array[i - 1] = temp
        swapped = True
      

More generally, it can happen that more than one element is placed in their final position on a single pass. In particular, after every pass, all elements after the last swap are sorted, and do not need to be checked again. (Wikipedia). Therefore we can further optimize the algorithm. Here is the Java implementation of the optimized algorithm.

 public int[] bubble_sort(int[] array) {
    int n = array.length;
    int newLimit = 0;
    boolean swapped;
    do {
        swapped = false;
        for (int i = 1; i < n; i++) {
            if (array[i - 1] > array[i]) {
                int temp = array[i];
                array[i] = array[i - 1];
                array[i - 1] = temp;
                swapped = true;
                newLimit = i;
            }
        }
        n = newLimit;

    } while (swapped);
    return array;
}