⚙️ C++

Алгоритмы сортировки в C++: подробное руководство

Урок 33 / 39 • Полная теория для чтения

Что это такое и зачем? (аналогия из реальной жизни)

Представьте, что вы — библиотекарь, и у вас есть огромная стопка книг, которые нужно расставить на полки в алфавитном порядке. Если книг всего пять, вы сделаете это за пару минут. Но что, если книг тысяча? Или десять тысяч? Вы будете тратить часы, переставляя книги с места на место, путаться и уставать.

Вот тут-то и приходят на помощь алгоритмы сортировки. Это набор чётких инструкций, которые говорят компьютеру: «Возьми этот список чисел (или имён, или любых других данных) и расположи их по порядку — от меньшего к большему или наоборот».

Сортировка — это не просто «красиво расставить цифры». Это основа для работы многих других алгоритмов. Например:

Поиск: Если массив отсортирован, найти нужный элемент можно в сотни раз быстрее (бинарный поиск).
Базы данных: Чтобы показать вам товары по цене или дате, база данных сортирует миллионы записей.
Графика: В играх сортируют объекты, чтобы понять, какой из них нарисовать первым (ближе к камере).

💡 Запомните: Если вы научитесь понимать сортировку, вы поймёте, как компьютер «думает» и принимает решения. Это первый шаг к написанию быстрых и эффективных программ.

В этой статье мы разберём три самых популярных алгоритма: Пузырьковая сортировка (самая простая для понимания), Сортировка вставками (как мы обычно сортируем карты в руке) и Быстрая сортировка (самая быстрая и популярная).

Теория: как это работает изнутри

Прежде чем писать код, давайте поймём, как каждый алгоритм «думает». У каждого из них есть своя стратегия.

1. Пузырьковая сортировка (Bubble Sort)

Аналогия: Представьте, что вы стоите в очереди, и самый высокий человек должен уйти в конец. Вы смотрите на двух соседей слева. Если левый выше правого — вы их меняете местами. Проходите так всю очередь раз за разом, пока самый высокий не «всплывёт» в конец, как пузырёк в газировке.

Как работает:

Берём первый элемент массива.
Сравниваем его со вторым. Если первый больше второго — меняем их местами.
Переходим ко второму элементу, сравниваем с третьим. И так до конца массива.
После первого прохода самый большой элемент оказывается в конце.
Повторяем шаги 1-4 для оставшейся части массива (без последнего элемента).
Повторяем, пока массив не будет отсортирован.

Сложность: O(n²) — очень медленно для больших массивов. Но очень просто для понимания.

2. Сортировка вставками (Insertion Sort)

Аналогия: Вы играете в карты. Вы берете новую карту из колоды и вставляете её в нужное место среди уже отсортированных карт в вашей руке. Сначала в руке одна карта (она уже отсортирована). Потом вы берёте вторую и решаете, положить её слева или справа от первой. И так далее.

Как работает:

Начинаем со второго элемента (индекс 1). Считаем, что первый элемент (индекс 0) — это уже отсортированная часть.
Запоминаем текущий элемент в переменную key.
Смотрим на элементы слева от key (в отсортированной части). Если они больше key, сдвигаем их на одну позицию вправо.
Как только находим элемент, который меньше или равен key, вставляем key на освободившееся место.
Повторяем для всех элементов массива.

Сложность: O(n²) в худшем случае, но на почти отсортированных данных работает очень быстро (O(n)).

3. Быстрая сортировка (Quick Sort)

Аналогия: Представьте, что вам нужно отсортировать кучу футболок по размеру. Вы берёте одну футболку (назовём её «опорной»). Все футболки, которые меньше опорной, вы кидаете в левую кучу, а те, что больше — в правую. Потом вы берёте каждую кучу и повторяете тот же трюк с новой опорной футболкой. И так до тех пор, пока в каждой куче не останется по одной футболке.

Как работает:

Выбираем опорный элемент (pivot). Обычно берут средний или последний элемент.
Переставляем элементы так, чтобы слева от pivot оказались все элементы меньше него, а справа — все больше. Это называется разделение (partition).
Теперь pivot находится на своём «законном» месте.
Рекурсивно (вызываем функцию саму для себя) применяем шаги 1-3 к левой и правой частям массива.

Сложность: O(n log n) в среднем — это очень быстро. O(n²) в худшем случае (если неудачно выбирать pivot), но на практике это случается редко.

Синтаксис в C++: все формы и варианты

В C++ есть два подхода к сортировке: написать свой алгоритм (для учёбы) или использовать встроенную функцию (для реальной работы).

Стандартная функция: `std::sort`

Это «швейцарский нож» сортировки. Она находится в библиотеке <algorithm>. Она использует гибридный алгоритм (обычно IntroSort — смесь быстрой, кучей и вставками), который в 99% случаев работает быстрее всего, что вы напишете сами.

Форма вызова	Описание	Пример
`std::sort(start, end)`	Сортирует от start до end (не включая end) по возрастанию.	`std::sort(arr, arr + n);`
`std::sort(start, end, comp)`	Сортирует с пользовательским компаратором (функцией сравнения).	`std::sort(arr, arr + n, std::greater<int>());`
`std::stable_sort(start, end)`	То же, что и sort, но сохраняет порядок равных элементов.	`std::stable_sort(v.begin(), v.end());`

⚠️ Важно: std::sort требует, чтобы итераторы были RandomAccessIterator. Это значит, что она работает с обычными массивами (int arr[100]) и с std::vector, но не работает с std::list (для списков есть std::list::sort).

Сортировка для разных контейнеров

Контейнер	Метод сортировки	Примечание
`std::vector`	`std::sort(v.begin(), v.end())`	Самый популярный способ.
`std::array`	`std::sort(arr.begin(), arr.end())`	Работает как с вектором.
`std::list`	`list.sort()`	Собственный метод, так как итераторы не random access.
`std::set` / `std::map`	Не нужно сортировать	Они всегда отсортированы по ключу автоматически.

Примеры кода — от простого к сложному

Все примеры ниже — рабочие. Вы можете скопировать их в свой компилятор (например, онлайн-компилятор на Wandbox) и запустить.

Пример 1: Пузырьковая сортировка (Bubble Sort) — классика

#include <iostream>
using namespace std;

// Функция для пузырьковой сортировки
void bubbleSort(int arr[], int n) {
    // Внешний цикл: делаем n-1 проходов
    for (int i = 0; i < n - 1; i++) {
        // Внутренний цикл: сравниваем соседние элементы
        // После каждого прохода самый большой элемент "всплывает" в конец
        for (int j = 0; j < n - i - 1; j++) {
            // Если текущий элемент больше следующего
            if (arr[j] > arr[j + 1]) {
                // Меняем их местами
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]); // Вычисляем размер массива

    cout << "Исходный массив: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";

    bubbleSort(arr, n);

    cout << "
Отсортированный массив: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;
}

Пример 2: Пузырьковая сортировка с оптимизацией (флаг)

#include <iostream>
using namespace std;

void optimizedBubbleSort(int arr[], int n) {
    bool swapped; // Флаг: были ли обмены на этом проходе?
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]); // Используем встроенный swap
                swapped = true;
            }
        }
        // Если не было ни одного обмена — массив уже отсортирован
        if (!swapped) break;
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6}; // Уже отсортированный массив
    int n = sizeof(arr) / sizeof(arr[0]);

    optimizedBubbleSort(arr, n);

    cout << "Отсортировано: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;
}

Пример 3: Сортировка вставками (Insertion Sort)

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    // Начинаем со второго элемента (индекс 1)
    for (int i = 1; i < n; i++) {
        int key = arr[i]; // Запоминаем текущий элемент
        int j = i - 1;    // Начинаем смотреть налево

        // Сдвигаем элементы вправо, пока не найдём место для key
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        // Вставляем key на правильное место
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    cout << "Результат: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;
}

Пример 4: Быстрая сортировка (Quick Sort) — разделение

#include <iostream>
using namespace std;

// Функция разделения (partition)
// Возвращает индекс, на котором стоит опорный элемент после разделения
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Берём последний элемент как опорный
    int i = low - 1;       // Индекс меньшего элемента

    for (int j = low; j < high; j++) {
        // Если текущий элемент меньше или равен pivot
        if (arr[j] <= pivot) {
            i++; // Увеличиваем индекс меньшего элемента
            swap(arr[i], arr[j]); // Меняем местами
        }
    }
    // Ставим pivot на его законное место
    swap(arr[i + 1], arr[high]);
    return i + 1; // Возвращаем индекс pivot
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi — индекс pivot после разделения
        int pi = partition(arr, low, high);

        // Рекурсивно сортируем левую и правую части
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    cout << "Быстрая сортировка: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;
}

Пример 5: Использование `std::sort` с вектором

#include <iostream>
#include <vector>
#include <algorithm> // Для std::sort
using namespace std;

int main() {
    vector<int> vec = {5, 2, 8, 1, 9, 3};

    cout << "До сортировки: ";
    for (int x : vec) cout << x << " ";

    // Сортировка по возрастанию (по умолчанию)
    sort(vec.begin(), vec.end());

    cout << "
После сортировки: ";
    for (int x : vec) cout << x << " ";
    return 0;
}

Пример 6: Сортировка по убыванию и с компаратором

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> vec = {5, 2, 8, 1, 9, 3};

    // Сортировка по убыванию с помощью функтора greater
    sort(vec.begin(), vec.end(), greater<int>());

    cout << "По убыванию: ";
    for (int x : vec) cout << x << " ";

    // Сортировка по возрастанию с помощью лямбда-функции
    sort(vec.begin(), vec.end(), [](int a, int b) {
        return a < b; // Если a меньше b, то a идёт раньше
    });

    cout << "
Снова по возрастанию (лямбда): ";
    for (int x : vec) cout << x << " ";
    return 0;
}

Пример 7: Сортировка массива структур

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

// Структура "Студент"
struct Student {
    string name;
    int grade;
};

int main() {
    vector<Student> students = {
        {"Alice", 85},
        {"Bob", 92},
        {"Charlie", 78},
        {"David", 92}
    };

    // Сортируем по оценке (по убыванию)
    // Если оценки равны — по имени (по алфавиту)
    sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
        if (a.grade != b.grade)
            return a.grade > b.grade; // Сначала высокие оценки
        return a.name < b.name; // Если оценки равны — по имени
    });

    cout << "Список студентов (по оценкам):
";
    for (const auto& s : students) {
        cout << s.name << ": " << s.grade << endl;
    }
    return 0;
}

Пример 8: Сортировка строк (лексикографическая)

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main() {
    vector<string> words = {"banana", "apple", "cherry", "date"};

    // Сортировка строк по алфавиту
    sort(words.begin(), words.end());

    cout << "Слова по алфавиту: ";
    for (const string& w : words) cout << w << " ";

    // Сортировка по длине строки
    sort(words.begin(), words.end(), [](const string& a, const string& b) {
        return a.length() < b.length();
    });

    cout << "
По длине: ";
    for (const string& w : words) cout << w << " ";
    return 0;
}

Сравнение с Python: чем похоже и чем отличается

Если вы уже знаете Python, то заметите, что идея сортировки везде одинакова. Но есть важные различия в синтаксисе и философии.

Характеристика	C++	Python
Встроенная функция	`std::sort(start, end)`	`sorted(list)` или `list.sort()`
Сортировка по убыванию	`std::sort(v.begin(), v.end(), std::greater<int>())`	`sorted(list, reverse=True)`
Сортировка по ключу	Нужно писать компаратор (лямбду)	`sorted(list, key=lambda x: x[1])`
Стабильность	`std::stable_sort` — стабильная, `std::sort` — нет	`sorted` и `list.sort` — стабильные
Скорость	Очень быстрая (компилируемый язык)	Медленнее (интерпретируемый), но для большинства задач хватает
Сложность написания своего алгоритма	Нужно управлять памятью, индексами	Проще, меньше синтаксического шума

💡 Совет: Если вы пишете на C++ для реального проекта — всегда используйте std::sort. Если вы учитесь — напишите свою пузырьковую сортировку один раз, чтобы понять, как работают циклы и обмены. Но не используйте её в продакшене — она слишком медленная.

Типичные ошибки и подводные камни

Даже опытные программисты иногда допускают эти ошибки. Вот список самых частых проблем при сортировке на C++.

1. Ошибка на единицу (Off-by-one error)

Самая популярная ошибка. Вы передаёте в std::sort неправильные границы.

int arr[5] = {5, 3, 1, 4, 2};
// НЕПРАВИЛЬНО: sort(arr, arr + 5); — это правильно
// НЕПРАВИЛЬНО: sort(arr, arr + 4); — последний элемент не будет отсортирован
// НЕПРАВИЛЬНО: sort(arr, arr + 6); — выход за границы массива (undefined behavior)

2. Забыли подключить `<algorithm>`

Без этого заголовочного файла std::sort не будет работать. Компилятор выдаст ошибку.

3. Сортировка `std::list` через `std::sort`

std::list не поддерживает std::sort, потому что у него нет RandomAccessIterator. Используйте list.sort().

4. Компаратор, который не является строгим слабым порядком

Компаратор должен возвращать true, если первый аргумент должен идти строго перед вторым. Если вы напишете return a <= b;, это может привести к неопределённому поведению (краш программы).

// НЕПРАВИЛЬНО:
sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });
// ПРАВИЛЬНО:
sort(v.begin(), v.end(), [](int a, int b) { return a < b; });

5. Сортировка константного массива

Если массив объявлен как const int arr[], вы не сможете его отсортировать, потому что элементы нельзя изменять.

6. Путаница между `std::sort` и `std::stable_sort`

Если вам важен порядок равных элементов (например, сортировка студентов сначала по классу, потом по имени), используйте std::stable_sort. std::sort может переставить равные элементы в произвольном порядке.

Лучшие практики и советы профессионалов

Вот что советуют опытные разработчики, которые пишут на C++ каждый день.

1. Всегда используйте `std::sort` вместо своего велосипеда

Исключение — только учебные задачи. std::sort оптимизирован лучше, чем 99% самодельных алгоритмов. Он использует интроспективную сортировку (IntroSort), которая сочетает в себе скорость быстрой сортировки и надёжность сортировки кучей.

2. Для сортировки по ключу используйте лямбды

Лямбда-функции делают код читаемым и компактным. Не пишите отдельные функции-компараторы, если они используются только один раз.

// Хорошо:
sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
    return a.age < b.age;
});
// Плохо (отдельная функция в глобальной области видимости):
bool compareByAge(const Person& a, const Person& b) { return a.age < b.age; }
sort(people.begin(), people.end(), compareByAge);

3. Если массив почти отсортирован — используйте сортировку вставками

Но только если вы пишете свой алгоритм. std::sort сам решит, когда переключиться на вставки.

4. Избегайте сортировки больших объектов по значению

Если вы сортируете вектор структур, которые весят много (например, содержат строки и другие контейнеры), сортировка будет копировать эти объекты при каждом обмене. Используйте вектор указателей или индексов.

// Вместо сортировки vector<BigObject>
// Сортируйте vector<int> индексов
vector<int> indices(n);
iota(indices.begin(), indices.end(), 0);
sort(indices.begin(), indices.end(), [&](int i, int j) {
    return bigObjects[i].key < bigObjects[j].key;
});

5. Проверяйте, нужно ли вообще сортировать

Иногда вместо сортировки можно использовать std::nth_element (если нужен только k-й по порядку элемент) или std::partial_sort (если нужны только первые k элементов). Это работает быстрее полной сортировки.

Вопросы для самопроверки

Проверьте, как вы усвоили материал. Постарайтесь ответить сначала сами, потом посмотрите ответы.

Вопрос: Какой алгоритм сортировки самый простой для понимания, но самый медленный на больших данных?
Вопрос: Какая функция в C++ отвечает за сортировку и из какой она библиотеки?
Вопрос: Что такое «стабильная сортировка»? Приведите пример, когда это важно.
Вопрос: Почему std::sort не работает с std::list?
Вопрос: Как отсортировать массив по убыванию с помощью std::sort?
Вопрос: В чём разница между пузырьковой сортировкой и сортировкой вставками?
Вопрос: Какая средняя временная сложность у быстрой сортировки?
Вопрос: Что произойдёт, если передать в std::sort компаратор, который возвращает a <= b?
Вопрос: Как отсортировать вектор структур по двум полям (сначала по возрасту, потом по имени)?
Вопрос: Какой алгоритм использует std::sort внутри себя?

Ответы на вопросы

Ответ: Пузырьковая сортировка (Bubble Sort). Её сложность O(n²).
Ответ: std::sort из библиотеки <algorithm>.
Ответ: Стабильная сортировка сохраняет относительный порядок равных элементов. Например, если сортировать студентов сначала по классу, а потом по имени, стабильная сортировка не «перемешает» студентов внутри одного класса.
Ответ: Потому что std::list имеет только двунаправленные итераторы (BidirectionalIterator), а std::sort требует итераторы произвольного доступа (RandomAccessIterator).
Ответ: Использовать компаратор std::greater<int>() или лямбду [](int a, int b) { return a > b; }.
Ответ: Пузырьковая сортировка «проталкивает» самый большой элемент в конец массива за каждый проход. Сортировка вставками берёт каждый новый элемент и вставляет его в уже отсортированную часть массива.
Ответ: O(n log n).
Ответ: Это может привести к неопределённому поведению (undefined behavior), программа может упасть или выдать неправильный результат. Компаратор должен быть строгим слабым порядком (strict weak ordering).
Ответ: Нужно написать лямбду, которая сначала сравнивает возраст, а если возраст равен — сравнивает имена.
Ответ: IntroSort (интроспективная сортировка) — гибрид быстрой сортировки, сортировки кучей и сортировки вставками.

Итог и что изучить дальше

Мы прошли долгий путь. Вы узнали:

Что такое сортировка и зачем она нужна (аналогия с библиотекой).
Как работают три основных алгоритма: пузырёк, вставки и быстрая сортировка.
Как использовать std::sort и её варианты в C

← Предыдущая Регулярные выражения в C++: подробное руководство Вперёд → Алгоритмы поиска в C++: подробное руководство

Алгоритмы сортировки в C++: подробное руководство

Что это такое и зачем? (аналогия из реальной жизни)

Теория: как это работает изнутри

1. Пузырьковая сортировка (Bubble Sort)

2. Сортировка вставками (Insertion Sort)

3. Быстрая сортировка (Quick Sort)

Синтаксис в C++: все формы и варианты

Стандартная функция: std::sort

Сортировка для разных контейнеров

Примеры кода — от простого к сложному

Пример 1: Пузырьковая сортировка (Bubble Sort) — классика

Пример 2: Пузырьковая сортировка с оптимизацией (флаг)

Пример 3: Сортировка вставками (Insertion Sort)

Пример 4: Быстрая сортировка (Quick Sort) — разделение

Пример 5: Использование std::sort с вектором

Пример 6: Сортировка по убыванию и с компаратором

Пример 7: Сортировка массива структур

Пример 8: Сортировка строк (лексикографическая)

Сравнение с Python: чем похоже и чем отличается

Типичные ошибки и подводные камни

1. Ошибка на единицу (Off-by-one error)

2. Забыли подключить <algorithm>

3. Сортировка std::list через std::sort

4. Компаратор, который не является строгим слабым порядком

5. Сортировка константного массива

6. Путаница между std::sort и std::stable_sort

Лучшие практики и советы профессионалов

1. Всегда используйте std::sort вместо своего велосипеда

2. Для сортировки по ключу используйте лямбды

3. Если массив почти отсортирован — используйте сортировку вставками

4. Избегайте сортировки больших объектов по значению

5. Проверяйте, нужно ли вообще сортировать

Вопросы для самопроверки

Ответы на вопросы

Итог и что изучить дальше

Стандартная функция: `std::sort`

Пример 5: Использование `std::sort` с вектором

2. Забыли подключить `<algorithm>`

3. Сортировка `std::list` через `std::sort`

6. Путаница между `std::sort` и `std::stable_sort`

1. Всегда используйте `std::sort` вместо своего велосипеда