0Pricing
C++ Academy · Lekcja

Sortowanie i partycjonowanie: sort, stable_partition

Sortuj i partycjonuj kontenery za pomocą std::sort i std::stable_partition

Sortowanie i partycjonowanie: sort, stable_partition to bezpłatna lekcja C++ Academy na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C++ Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C++ Academy zawiera 4 lekcji w sumie.

std::sort

Podstawowy algorytm sortowania. Średnio O(N log N). Działa w miejscu. Nie gwarantuje stabilności.

#include <algorithm>
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
std::sort(v.begin(), v.end());
// v is sorted ascending

Niestandardowy komparator

Do sortowania według innych kryteriów należy przekazać komparator (lambdę lub funktor).

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

Sortowanie typów niestandardowych

Należy dostarczyć komparator porównujący określone składowe albo zdefiniować w typie operator<.

struct Person { std::string name; int age; };
std::vector<Person> people;
std::sort(people.begin(), people.end(),
    [](const Person& a, const Person& b) { return a.age < b.age; });

std::stable_sort

Działa tak samo jak sort, ale zachowuje względną kolejność równych elementów. Jest nieco wolniejszy (zwykle wymaga dodatkowej pamięci O(N log^2 N)).

std::partial_sort

Umieszcza pierwszych k najmniejszych elementów na początku i sortuje je. Pozostałe elementy mają nieokreśloną kolejność. Jest szybszy od pełnego sortowania, gdy potrzebują Państwo tylko pierwszych k elementów.

std::vector<int> v = {5, 2, 8, 1, 9, 3};
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// first 3 elements are the smallest, sorted

std::nth_element

Dzieli zakres tak, aby element na pozycji nth był taki, jak byłby w pełni posortowanym zakresie. Wszystkie elementy przed nim są ≤ elementu nth, a wszystkie za nim są ≥ elementu nth. Średnio O(N).

std::nth_element(v.begin(), v.begin() + 2, v.end());
// v[2] is the 3rd smallest element

std::is_sorted

Sprawdza, czy zakres jest już posortowany.

if (std::is_sorted(v.begin(), v.end())) {
    std::cout << "already sorted";
}

std::partition

Porządkuje zakres tak, aby elementy spełniające predykat znalazły się na początku. Zwraca iterator wskazujący pierwszy element niespełniający predykatu. Nie zachowuje stabilności.

std::vector<int> v = {1, 2, 3, 4, 5};
auto pivot = std::partition(v.begin(), v.end(),
    [](int x) { return x % 2 == 0; });
// even numbers come first, then odd

std::stable_partition

Działa podobnie jak partition, ale zachowuje względną kolejność elementów w każdej grupie.

Sortowanie według wielu kluczy

Należy użyć komparatora, który porównuje najpierw klucz główny, a następnie klucz dodatkowy, jeśli wartości klucza głównego są równe.

std::sort(people.begin(), people.end(),
    [](const Person& a, const Person& b) {
        if (a.age != b.age) return a.age < b.age;
        return a.name < b.name;
    });

Wyszukiwanie binarne w posortowanych zakresach

Po posortowaniu można użyć std::lower_bound, std::upper_bound i std::binary_search do wyszukiwania w czasie O(log N).

Szybki test

Który algorytm zachowuje względną kolejność równych elementów po sortowaniu?

Podsumowanie

Do ogólnego sortowania należy używać std::sort, gdy kolejność równych elementów ma znaczenie — std::stable_sort, do pierwszych k elementów — std::partial_sort, do wyboru elementu — std::nth_element, a do grupowania — std::partition/std::stable_partition.

Często zadawane pytania

Czy lekcja „Sortowanie i partycjonowanie: sort, stable_partition” jest bezpłatna?

Tak — pełny tekst „Sortowanie i partycjonowanie: sort, stable_partition” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C++ Academy, przejdź na CoddyKit PRO. Kurs C++ Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Sortowanie i partycjonowanie: sort, stable_partition”?

Sortuj i partycjonuj kontenery za pomocą std::sort i std::stable_partition Ćwiczysz C++ Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć C++ Academy?

Nie wymagamy żadnego doświadczenia. C++ Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.

Ile czasu zajmuje lekcja „Sortowanie i partycjonowanie: sort, stable_partition”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji C++ Academy?

Tak. Każda lekcja C++ Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Algorytmy niemodyfikujące: find, count, all_of
  2. Modyfikowanie: transform, copy_if, replace
  3. Sortowanie i partycjonowanie: sort, stable_partition
  4. Algorytmy numeryczne: accumulate, reduce, transform_reduce
← Powrót do C++ Academy