Сортировки на C++: пузырек и быстрая сортировка

Сортировки в C++ часто дают как первые алгоритмы. И тут есть ловушка: новичок заучивает пузырек, но не понимает, почему в реальном коде обычно используют std::sort

Разберем честно. Пузырек полезен как учебный пример: он показывает сравнение и обмен. Для реальной работы почти всегда лучше стандартная библиотека. Быстрая сортировка полезна как идея разделения данных

Исходный массив

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 7};

    for (int number : numbers) {
        std::cout << number << " ";
    }

    return 0;
}

Вывод:

5 2 9 1 7

Нужно получить:

1 2 5 7 9

Сортировка пузырьком

Идея: сравниваем соседние элементы и меняем их местами, если они стоят неправильно. После каждого прохода большой элемент "всплывает" к концу

#include <iostream>
#include <vector>

void bubbleSort(std::vector<int>& numbers) {
    int size = numbers.size();

    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (numbers[j] > numbers[j + 1]) {
                int temp = numbers[j];
                numbers[j] = numbers[j + 1];
                numbers[j + 1] = temp;
            }
        }
    }
}

int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 7};

    bubbleSort(numbers);

    for (int number : numbers) {
        std::cout << number << " ";
    }

    return 0;
}

Как читать пузырек

Внутренний цикл сравнивает пару:

if (numbers[j] > numbers[j + 1])

Если левый больше правого, меняем:

int temp = numbers[j];
numbers[j] = numbers[j + 1];
numbers[j + 1] = temp;

temp нужен, чтобы не потерять значение при обмене

Оптимизация пузырька

Если за проход не было обменов, массив уже отсортирован:

void bubbleSort(std::vector<int>& numbers) {
    int size = numbers.size();

    for (int i = 0; i < size - 1; i++) {
        bool swapped = false;

        for (int j = 0; j < size - i - 1; j++) {
            if (numbers[j] > numbers[j + 1]) {
                std::swap(numbers[j], numbers[j + 1]);
                swapped = true;
            }
        }

        if (!swapped) {
            break;
        }
    }
}

Здесь используем std::swap, для него можно подключить:

#include <utility>

std::sort: как делают в обычном коде

Для реальной сортировки:

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 7};

    std::sort(numbers.begin(), numbers.end());

    for (int number : numbers) {
        std::cout << number << " ";
    }

    return 0;
}

std::sort из стандартной библиотеки быстрее, надежнее и привычнее для production-кода, чем самописный пузырек

Сортировка по убыванию:

std::sort(numbers.begin(), numbers.end(), std::greater<int>());

Нужно подключить:

#include <functional>

Быстрая сортировка как идея

Быстрая сортировка выбирает опорный элемент, разделяет массив на меньшие и большие элементы, потом сортирует части

Учебная версия:

#include <iostream>
#include <vector>

void quickSort(std::vector<int>& numbers, int left, int right) {
    if (left >= right) {
        return;
    }

    int pivot = numbers[(left + right) / 2];
    int i = left;
    int j = right;

    while (i <= j) {
        while (numbers[i] < pivot) {
            i++;
        }

        while (numbers[j] > pivot) {
            j--;
        }

        if (i <= j) {
            std::swap(numbers[i], numbers[j]);
            i++;
            j--;
        }
    }

    quickSort(numbers, left, j);
    quickSort(numbers, i, right);
}

Вызов:

quickSort(numbers, 0, numbers.size() - 1);

Для первого знакомства не надо пытаться запомнить весь код. Важно понять принцип: разделить данные относительно опорного элемента и рекурсивно повторить

Что выбрать в задаче

Частые ошибки

Выход за границы

В пузырьке важно:

j < size - i - 1

Потому что мы обращаемся к numbers[j + 1]

Забыли include algorithm

Для std::sort нужно:

#include <algorithm>

Пишут пузырек в реальном проекте

Для учебы нормально. Для реального кода почти всегда бери стандартную библиотеку

Рекурсия без условия остановки

В quick sort обязательно:

if (left >= right) {
    return;
}

Мини-задание

1. Отсортируй массив оценок по возрастанию через пузырек.
2. Отсортируй тот же массив через std::sort.
3. Сделай сортировку по убыванию.
4. Выведи минимальный и максимальный элемент после сортировки.

Пример:

std::vector<int> scores = {8, 10, 7, 9, 6};

Ответы на эти вопросы могут быть для вас полезными

Что такое сортировка пузырьком?

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

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

Обычно нет. В C++ для реальной сортировки лучше использовать std::sort

Что такое быстрая сортировка?

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

Почему std::sort лучше?

Он реализован в стандартной библиотеке, оптимизирован и хорошо проверен

Что учить после сортировок?

Поиск, рекурсию, структуры данных и работу с алгоритмами стандартной библиотеки

Что почитать дальше по C++

Чтобы тема складывалась в понятный маршрут, рядом лучше открыть:

• Массивы в C++ на примерах — повторить массивы перед сортировкой.
• Функции в C++: как убрать повтор кода — вынести сортировку и вывод в отдельные функции.
• Типы данных в C++: int, double, bool, char, string — закрепить типы элементов массива.
• Классы и ООП в C++: первый пример без перегруза — двигаться дальше к структурам и объектам.