BubbleSort

BubbleSort is an exchange sort that is inefficient, but easy to to understand.

Keep passing through the list, exchanging adjacent elements, if necessary; when no exchanges are required on some pass, the file is sorted.

  1. begin with elements 0 and 1 ('i' and 'j')
  2. compare two adjacent elements 'i' and 'j'
  3. if element 'i' less than element 'j', swap them
  4. move one position to the right

When sorting in ascending order, the largest element "sinks" to the end of the list and the smallest values "bubble up" towards their proper positions near the front of the list.

BubbleSort pseudo-code:

   // assume we have an array 'a' with length 'n'

   end_i = n-1;
   while (end_i > 0) {
      last_i = 0;
      for (next_i = 0; next_i < end_i; next_i++) {
         if (COMPARE (a, next_i, next_i+1)) {
            SWAP (a, next_i, next_i+1);
            last_i = next_i;
         }
      }
      end_i = last_i;
   }

BubbleSort is terrible [O(n^2)] if the list is sorted in reverse order. It works great given a list that is already sorted.

YouTube.com::Bubble Sort by CS50 at Harvard