Наш первый подход будет заключаться в следующем: обозначим за $n$ длину массива и $n$ раз пройдёмся по нему слева направо, меняя два соседних элемента, если первый больше второго.
Каждую итерацию максимальный элемент «всплывает» как пузырек к концу массива — отсюда и название.
void bubble_sort(int *a, int n) {
for (int k = 0; k < n; k++)
for (int i = 0; i < n - 1; i++)
// сравниваем элемент со следующим
if (a[i] > a[i + 1])
// меняем местами, если следующий меньше
swap(a[i], a[i + 1]);
}
int a[5] = {5, 2, 1, 3, 1};
bubble_sort(a, 5);
for (int i = 0; i < 5; i++)
cout << a[i] << " ";
Корректность. По индукции можно показать, что после $k$ шагов алгоритма сортировки пузырьком последние $k$ чисел всегда отсортированы, а значит алгоритм работает корректно.
Асимптотика. Так как у нас два вложенных цикла, каждый из которых делает не более $O(n)$ итераций, внутри которых за $O(1)$ происходит сравнение и swap, суммарное время работы будет не более $O(n^2)$.
Упражнение. Алгоритм можно немного (неасимптотически) ускорить. Как нужно изменить границы в двух for-циклах, чтобы не делать никаких лишних действий?