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.