# Quick Access

# How To Build

**Bubble sort**, sometimes referred to as **sinking sort**,
is a simple and well-known sorting algorithm. It is used in practice once in a blue moon
and its main application is to make an introduction to the sorting algorithms.

The algorithm Compare each pair of adjacent elements from the beginning of a sequence and,
if they are in reversed order, swap them: larger 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.

An other way of thinking at this sorting algorithm is:

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

## 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 possible comparison (optimization).

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

# Visualization Analysis

# Complexity

## Reminder

Usefull 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( n^{2})** 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.

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

$$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.