Bubble Sort

This is a simple, but quite inefficient algorithm to sort an array of objects (numbers). The basic idea is to compare two neighboring objects, and to swap them if they are in the wrong order.

Given an array a[] of numbers, with length n, the main part of a bubble sort algorithm looks like:

for (i=0; i<n-1; i++) {
  for (j=0; j<n-1-i; j++)
    if (a[j+1] < a[j]) {  /* compare the two neighbors */
      tmp = a[j];         /* swap a[j] and a[j+1]      */
      a[j] = a[j+1];
      a[j+1] = tmp;
  }
}

The algorithm consists of two nested loops. The index j in the inner loop travels up the array, comparing adjacent entries in the array (at j and j+1), while the outer loop causes the inner loop to make repeated passes through the array. After the first pass, the largest element is guaranteed to be at the end of the array, after the second pass, the second largest element is in position, and so on. That is why the upper bound in the inner
loop (n-1-i) decreases with each pass: we don't have to re-visit the end of the array.

The first step in the algorithm takes n-1 comparisons. The second step takes n-2 comparisons, and so on. The last step takes one comparison. The total number of comparisons then is
1+2+...+n-1=n*(n-1)/2, which is O(n^2).