Dokumentacja C++ z przykładami: Sortowanie

Q: Jak posortować wektor w C++?

Dołącz i wywołaj sort(v.begin(), v.end()). To sortuje elementy w miejscu w kolejności rosnącej przy użyciu operator<. Aby posortować tablicę, przekaż arr i arr + n (albo begin(arr) / end(arr)).

Q: Jak sortować malejąco w C++?

Przekaż komparator, który zwraca a > b: sort(v.begin(), v.end(), [](int a, int b){ return a > b; });. Możesz też użyć wbudowanego sort(v.begin(), v.end(), greater ()); z .

Q: Dlaczego mój komparator w C++ powoduje awarię std::sort?

Komparator musi definiować ścisły porządek słaby: dla dwóch równych argumentów musi zwracać false. Użycie = (które zwracają true dla równych elementów) łamie tę zasadę i jest niezdefiniowanym zachowaniem: std::sort może czytać poza zakresem i się wysypać. Zawsze porównuj przez .

Sortowanie to po prostu kolejny algorytm

Na poprzedniej stronie widać było, że biblioteka standardowa ma gotowe algorytmy, które działają na dowolnym zakresie przez iteratory. Po sortowanie będziesz sięgać najczęściej, a ma ono własną stronę, bo ma kilka ostrych krawędzi: własne porządki, stabilność i zasadę, której złamanie daje niezdefiniowane zachowanie zamiast złej odpowiedzi.

Koniem roboczym jest std::sort z <algorithm>. Podajesz mu początek i koniec zakresu, a on przestawia elementy w miejscu w kolejności rosnącej:

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

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

    sort(nums.begin(), nums.end());   // rosnąco, w miejscu

    for (int n : nums) cout << n << " ";  // 1 2 3 5 8 9
    cout << "\n";
    return 0;
}

Nie powstaje żadna kopia: przestawiany jest sam wektor. Pod spodem std::sort to zwykle introsort (quicksort, który w razie potrzeby przechodzi na heapsort), co daje średnio O(n log n). To prawie zawsze szybsze i znacznie mniej podatne na błędy niż pisanie własnego sortowania.

Działa też na zwykłych tablicach z C: zakres opisujesz po prostu wskaźnikami:

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

int main() {
    int arr[] = {40, 10, 30, 20};
    int n = 4;

    sort(arr, arr + n);               // albo sort(begin(arr), end(arr));

    for (int x : arr) cout << x << " ";  // 10 20 30 40
    return 0;
}

Własna kolejność z komparatorem

Domyślnie std::sort porządkuje elementy przez operator<. Aby sortować inaczej, przekaż trzeci argument: komparator, który przyjmuje dwa elementy i zwraca true, jeśli pierwszy ma stać przed drugim.

Naturalnym wyborem jest lambda. Kolejność malejąca to po prostu a > b:

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

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

    sort(nums.begin(), nums.end(), [](int a, int b) {
        return a > b;   // "a przed b", gdy a jest większe -> malejąco
    });

    for (int n : nums) cout << n << " ";  // 9 8 5 3 2 1
    cout << "\n";
    return 0;
}

Dla częstego przypadku zwykłej kolejności malejącej na typach wbudowanych biblioteka ma nawet gotowy komparator, greater<T>() z <functional>:

#include <functional>
sort(nums.begin(), nums.end(), greater<int>());  // to samo co a > b

Komparator pozwala też sortować według czegoś innego niż sama wartość, na przykład napisy według długości zamiast alfabetycznie:

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

int main() {
    vector<string> words = {"pear", "fig", "banana", "kiwi"};

    sort(words.begin(), words.end(), [](const string& a, const string& b) {
        return a.size() < b.size();   // krótsze słowa najpierw
    });

    for (const string& w : words) cout << w << " ";  // fig kiwi pear banana
    cout << "\n";
    return 0;
}

Parametry komparatora przyjmuj przez const& dla wszystkiego, co jest większe niż kilka bajtów (jak string): kopiowanie każdego elementu przy każdym porównaniu to czyste marnotrawstwo.

Sortowanie struktur według pola

W prawdziwych programach zwykle sortujesz kolekcje struktur według jednego z ich pól. Komparator po prostu sięga do pola, które cię interesuje. Tutaj sortujemy osoby według wieku, od najmłodszej:

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

struct Person {
    string name;
    int age;
};

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return a.age < b.age;
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    return 0;
}

Zauważ, że Linus i Dennis mają po 25 lat. Tutaj wyszli w swojej pierwotnej względnej kolejności, ale std::sort tego nie gwarantuje. Jeśli względna kolejność równych elementów ma znaczenie, użyj std::stable_sort, które ją zachowuje (kosztem niewielkiej utraty wydajności):

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

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    stable_sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) { return a.age < b.age; });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    // Linus zostaje przed Dennisem: ich kolejność z wejścia jest zachowana
    return 0;
}

Aby celowo rozstrzygać remisy, na przykład sortować według wieku, a potem alfabetycznie według imienia, porównuj klucz drugorzędny tylko wtedy, gdy klucze główne są równe. std::tie czyni to przejrzystym:

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

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return tie(a.age, a.name) < tie(b.age, b.name);  // wiek, potem imię
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";  // Dennis i Linus 25, alfabetycznie
    return 0;
}

Pułapka ścisłego porządku słabego

To najgroźniejszy błąd przy sortowaniu w C++, bo nie daje złej odpowiedzi, tylko niezdefiniowane zachowanie, co często oznacza awarię albo odczyt poza zakresem.

std::sort wymaga, żeby komparator definiował ścisły porządek słaby. Praktyczna zasada: comp(x, x) musi być false dla każdego elementu x. Innymi słowy element nigdy nie stoi „przed” samym sobą. Dokładnie to dają < i >, i dokładnie to łamią <= i >=:

// BŁĄD: zwraca true, gdy a == b, co łamie ścisły porządek słaby.
sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;   // niezdefiniowane zachowanie: dla niektórych danych może się wysypać
});

Przy <= komparator twierdzi, że 5 stoi przed inną 5, co jest sprzeczne. std::sort może wtedy przesunąć wskaźnik za koniec zakresu. Małe dane czasem wyglądają na działające, przez co ten błąd jest przerażający: może przejść twoje testy i wysypać się na produkcji. Naprawa to po prostu <:

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

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

    sort(v.begin(), v.end(), [](int a, int b) {
        return a < b;   // poprawnie: false, gdy są równe
    });

    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

Druga klasyczna pułapka: sortowanie unieważnia wszystko, co wskazuje do wnętrza zakresu. Iteratory, wskaźniki i indeksy zapisane przed sortowaniem nie odnoszą się już potem do tego samego logicznego elementu, bo elementy się przesunęły. Każdą potrzebną pozycję wyznaczaj ponownie po sortowaniu, nigdy przed.

Sortowanie części zakresu

Czasem nie potrzebujesz posortować wszystkiego: chcesz tylko kilka pierwszych. Sortowanie całego wektora po to, żeby odczytać pierwsze trzy elementy, to marnotrawstwo. std::partial_sort układa tylko elementy, o które prosisz, a resztę zostawia w nieokreślonej kolejności, co jest tańsze:

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

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

    // Umieść 3 najmniejsze, po kolei, na początku. Reszta jest nieokreślona.
    partial_sort(v.begin(), v.begin() + 3, v.end());

    for (int i = 0; i < 3; i++) cout << v[i] << " ";  // 1 2 3
    cout << "\n";
    return 0;
}

A jeśli potrzebujesz tylko jednego elementu, który stałby na danej pozycji, na przykład mediany, std::nth_element wykonuje jeszcze mniej pracy: umieszcza właściwy element pod tym indeksem, wszystko mniejsze przed nim, a wszystko większe za nim, średnio w czasie O(n).

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

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};
    size_t mid = v.size() / 2;

    nth_element(v.begin(), v.begin() + mid, v.end());

    cout << "median is " << v[mid] << "\n";  // 5
    return 0;
}

Sięgaj po nie, gdy „w pełni posortowane” to więcej, niż problem faktycznie wymaga: na dużych danych oszczędzają realny czas.

Dalej: szablony

Zauważasz, że ten sam std::sort obsłużył int, string i twoją własną strukturę Person, a greater<int>() mogłoby równie dobrze być greater<string>()? Ta ogólność to nie magia, tylko szablony: mechanizm, który pozwala jednemu kawałkowi kodu działać dla dowolnego typu, jaki podstawi wywołujący. Na następnej stronie zobaczysz, jak pisać własne funkcje i klasy szablonowe, żeby twój kod był tak niezależny od typów jak algorytmy, których tu używasz.

Najczęściej zadawane pytania

Jak posortować wektor w C++?

Dołącz <algorithm> i wywołaj sort(v.begin(), v.end()). To sortuje elementy w miejscu w kolejności rosnącej przy użyciu operator<. Aby posortować tablicę, przekaż arr i arr + n (albo begin(arr) / end(arr)).

Jak sortować malejąco w C++?

Przekaż komparator, który zwraca a > b: sort(v.begin(), v.end(), [](int a, int b){ return a > b; });. Możesz też użyć wbudowanego sort(v.begin(), v.end(), greater<int>()); z <functional>.

Dlaczego mój komparator w C++ powoduje awarię std::sort?

Komparator musi definiować ścisły porządek słaby: dla dwóch równych argumentów musi zwracać false. Użycie <= albo >= (które zwracają true dla równych elementów) łamie tę zasadę i jest niezdefiniowanym zachowaniem: std::sort może czytać poza zakresem i się wysypać. Zawsze porównuj przez < albo >.

Powiązane zagadnienia