Глиф Учебники

Как отсортировать вектор

Справочник · C++ · 1 минута чтения

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

int main() {
    vector<int> v = {5, 3, 8, 1, 9, 2};
    sort(v.begin(), v.end());                  // по возрастанию
    for (int x : v) cout << x << " ";
    cout << "\n";
    sort(v.rbegin(), v.rend());                // по убыванию
    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}
Вывод
1 2 3 5 8 9
9 8 5 3 2 1

sort из <algorithm> сортирует диапазон «от начала до конца». rbegin() и rend() — тот же вектор, но с конца, поэтому сортировка по возрастанию «задом наперёд» даёт убывание. Другой способ убывания — sort(v.begin(), v.end(), greater<int>()); с #include <functional>.

Обычный массив и часть вектора

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

int main() {
    int a[5] = {4, 2, 5, 1, 3};
    sort(a, a + 5);                            // весь массив из 5 элементов
    for (int x : a) cout << x << " ";
    cout << "\n";
    vector<int> v = {9, 7, 5, 3, 1};
    sort(v.begin(), v.begin() + 3);            // только первые три
    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}
Вывод
1 2 3 4 5
5 7 9 3 1

Для массива из n элементов — sort(a, a + n). Если массив заполнен с индекса 1 (так бывает в олимпиадных решениях) — sort(a + 1, a + n + 1).

Свой порядок

Третий аргумент — функция сравнения: получает два элемента и возвращает true, если первый должен стоять раньше второго. Удобнее всего лямбда — короткая функция, написанная прямо в месте вызова:

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

int main() {
    vector<int> v = {-7, 3, -1, 5, -4};
    sort(v.begin(), v.end(), [](int a, int b) {
        return abs(a) < abs(b);                // по модулю
    });
    for (int x : v) cout << x << " ";
    cout << "\n";

    vector<string> w = {"pear", "fig", "banana", "kiwi"};
    sort(w.begin(), w.end(), [](const string& a, const string& b) {
        if (a.size() != b.size()) return a.size() < b.size();
        return a < b;                          // по длине, потом по алфавиту
    });
    for (const string& s : w) cout << s << " ";
    cout << "\n";
    return 0;
}
Вывод
-1 3 -4 5 -7
fig kiwi pear banana

Структуры сортируют так же — лямбдой, сравнивающей нужные поля (пример — в уроке STL: sort, map и set). Векторы пар pair и строки сортируются и без функции: по первому элементу, при равенстве — по второму, строки — по алфавиту.

Сохранить порядок равных

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

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

В функции сравнения нельзя писать <= или >=. Она должна отвечать «строго раньше». С <= поведение не определено: на больших массивах с повторами программа может выйти за границы вектора и упасть.