Разные подходы к сортировке вектора

Условие

Опишите и реализуйте несколько методов упорядочения элементов std::vector: с помощью функции std::sort, используя std::sort с лямбда‑выражением и написав собственный алгоритм сортировки (например, пузырьковую).

std::vector<int> vec;
// std::sort(vec.begin(), vec.end());
// std::sort с лямбдой
// собственная сортировка (например, пузырьковая)

Ответ

std::sort сортирует диапазон по возрастанию по умолчанию. Лямбда задаёт другой строгий порядок; собственная пузырьковая сортировка полезна как учебный, но обычно более медленный вариант.

Альтернативные способы:

std::sort(vec.begin(), vec.end());
std::sort(vec.begin(), vec.end(), [](int a, int b) { return a > b; });

Второй пример сортирует по убыванию. Самописный вариант по возрастанию:

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

std::sort требует O(n log n) сравнений, пузырёк — O(n²) в худшем случае. Сравнение a >= b не подходит как компаратор sort: оно нарушает требование строгого порядка.