Traces by Bubble Sort on random sequences {50}

Swaps by Bubble Sort on random sequences {50}

Traces by Bubble Sort on reversed sequence {50} (worst case)

Swaps by Bubble Sort on reversed sequence {50} (worst case)

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;
  }
}

Displace the highest value at the end by swapping it successively.

Same with the second loop and second highest value, as you can see: once the loop has made its move, the computation range remove the last item as it is already the highest value.

Further illustration of the previous descriptions.

Algorithm ends when we fully square-iterated the sequence: sort is done.

Reminder

Useful mathematical theorems:

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(n²) 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.

Space

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