Bubble sort, sometimes referred to as sinking sort, is a well-known sorting algorithm. Its primary application is to make an introduction to computer sciences.

The algorithm Compare each pair of adjacent elements from the beginning of a sequence and, if they are in reversed order, swap them: more significant elements are "bubbled" down in the sequence.
The pass through the list is repeated until no swaps are needed: it indicates that the list is sorted.

Another way of thinking of this sorting algorithm is:

The larger values might be regarded as more massive and therefore be seen to sink to the bottom of the list progressively.

Steps

  • While there is swap needed:
    • 1. Compare each pair of adjacent elements from the beginning of an array and, if they are in reversed order, swap them.
    • 2. If no swap made, then stop: we are done (optimization).
    • 3. Remove the current last element from the possible comparison (optimization).

Code

void BubbleSort (Iterator begin, Iterator end)
{
  if (distance(begin, end) < 2)
    return;

  // Optimization: after each inner loop: the highest values already
  // is at the end of the array (reduce next loop to n-i).
  auto endIdx = -1;

  // Optimization: if no swaps needed, it indicates that
  // the list is sorted.
  bool hasSwapped;

  // For each pair of elements - bubble the greater up.
  // Then reduce the end to end - 1
  for (auto it = begin; it < end - 1; ++it, --endIdx)
  {
    hasSwapped = false;
    for (auto curIt = begin; curIt < end + endIdx; ++curIt)
      if (Compare(curIt, (curIt + 1)))
      {
        swap(curIt, (curIt + 1));
        hasSwapped = true;
      }

    // Stop if no swap needed
    if (!hasSwapped)
      break;
  }
}

Reminder

Useful mathematical theorems:

$$\sum_{i=0}^{n-1} n = n(n-1)$$ $$\sum_{i=0}^{n-1} i = \frac{n(n + 1)}{2} - n = \frac{n(n - 1)}{2}$$ $$\sum_{i=0}^{n-1} (n+i) = \sum_{i=0}^{n-1} n + \sum_{i=0}^{n-1} i$$

Time

Best

The best configuration occurs when all elements are already sorted.
Consequently, we have to go through the first sequence only once: O(n).

Average / Worst

The worst case O(n2) occurs when the sequence is in reverse order. First, the highest value is bubbled down until the end; then the second highest value bubbled down until end - 1, etc.

Sequences

$$a_0 = n$$ $$a_1 = n - 1$$ $$a_2 = n - 2$$ $$...$$ $$a_i = n - i$$

Computation

$$S(n) = \sum_{i=0}^{n-1} (n-i)$$ $$S(n) = \sum_{i=0}^{n-1} n - \sum_{i=0}^{n-1} i$$ $$S(n) = n(n - 1) - \frac{n(n - 1)}{2}$$ $$S(n) = \frac{n(n - 1)}{2}$$ $$S(n) = k(n^2 - n)$$ $$S(n) \approx O(n^2)$$

Space

Bubble Sort does not use any buffer nor does make any recursion. Thus, it requires O(1) space in all case.