Написать сортировку массива методом пузырька

Условие

Необходимо реализовать алгоритм пузырьковой сортировки, который упорядочит элементы переданного вектора целых чисел.

std::vector<int> data = {1, -5, 4, 1, 10, 1, -33, 300};
// отсортировать с помощью пузырьковой сортировки

Ответ

На каждом проходе сравнивайте соседние элементы и меняйте их местами, если порядок нарушен. Максимум оставшейся части постепенно перемещается в конец; отсутствие обменов позволяет закончить раньше.

void bubbleSort(std::vector<int>& data) {
    for (std::size_t end = data.size(); end > 1; --end) {
        bool changed = false;
        for (std::size_t i = 1; i < end; ++i) {
            if (data[i - 1] > data[i]) {
                std::swap(data[i - 1], data[i]);
                changed = true;
            }
        }
        if (!changed) break;
    }
}

Пример даёт −33, −5, 1, 1, 1, 4, 10, 300. Худшее время O(n²), на уже отсортированном входе O(n), память O(1). Равные элементы не меняются местами, поэтому сортировка стабильна.