Bubble Sort

Bubble sort is one of the most inefficient sorting algorithms. While asymptotically equivalent to the other O(n²) algorithms, it will require O(n²) swaps in the worst-case. However, it is probably the simplest to understand. At each step, if two adjacent elements of a list are not in order, they will be swapped. Thus, smaller elements will "bubble" to the front, (or bigger elements will be "bubbled" to the back, depending on implementation) and hence the name. This algorithm is almost never recommended, as insertion sort has the same asymptotic complexity, but only requires O(n) swaps. Bubble sort is stable, as two equal elements will never be swapped.

Time Complexity:

Average Case: O(n²)

Worst Case: O(n²)

Pseudo-code

a is an array size n

func bubblesort( var a as array )
    for i from 1 to N
        for j from 0 to N - 1
           if a[j] > a[j + 1]
              swap( a[j], a[j + 1] )
end func

Optimization (1): A small improvement can be made if each pass you keep track of whether or not an element was swapped. If not, you can safely assume the list is sorted.

func bubblesort2( var a as array )
    for i from 2 to N
        swaps = 0
        for j from 0 to N - 2
           if a[j] > a[j + 1]
              swap( a[j], a[j + 1] )
              swaps = swaps + 1
        if swaps = 0
            break
end func

Java Implementation:

import java.util.Scanner;

public class BubbleSort {
 static void bubblesort(Integer[] ar) {
  for (int i = 0; i < ar.length - 1; i++)
   for (int j = 0; j < ar.length - 1; j++) { if (ar[j] > ar[j + 1]) {
     int temp = ar[j];
     ar[j] = ar[j + 1];
     ar[j + 1] = temp;
    }
   }
 }

 public static void main(String[] args) {
  Scanner in = new Scanner(System.in);
  int n = in.nextInt();
  Integer[] ar = new Integer[n];
  for (int i = 0; i < n; i++)
   ar[i] = in.nextInt();
  bubblesort(ar);
  for (Integer v : ar)
   System.out.print(v + " ");
  System.out.println("");
 }
}