0Pricing
C++ Academy · Lezione

Ordinamento e partizionamento: sort, stable_partition

Ordini e partizioni i contenitori con std::sort e std::stable_partition

Ordinamento e partizionamento: sort, stable_partition è una lezione C++ Academy gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento C++ Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso C++ Academy include 4 lezioni in totale.

std::sort

L'algoritmo di ordinamento più utilizzato. O(N log N) in media. Opera sul posto. Non garantisce la stabilità.

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

Comparatore personalizzato

Passi a sort un comparatore (lambda o functor) per ordinare secondo altri criteri.

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

Ordinamento di tipi personalizzati

Fornisca un comparatore che confronti membri specifici oppure definisca operator< sul tipo.

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

Come sort, ma mantiene l'ordine relativo degli elementi equivalenti. È leggermente più lento (in genere usa memoria aggiuntiva O(N log^2 N)).

std::partial_sort

Posiziona per primi i k elementi più piccoli (ordinati). Gli elementi rimanenti sono in un ordine non specificato. È più veloce di un ordinamento completo quando servono solo i primi k elementi.

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

Partiziona il range in modo che l'elemento nella posizione nth sia quello che si troverebbe lì in un range completamente ordinato. Tutto ciò che precede è ≤ dell'elemento in quella posizione; tutto ciò che segue è ≥. O(N) in media.

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

std::is_sorted

Verifica se un range è già ordinato.

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

std::partition

Riordina un range in modo che gli elementi che soddisfano un predicato vengano prima. Restituisce l'iteratore al primo elemento che non lo soddisfa. Non è stabile.

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

Come partition, ma mantiene l'ordine relativo all'interno di ciascun gruppo.

Ordinamento con più chiavi

Usi un comparatore che confronti la chiave primaria e poi quella secondaria se la primaria è uguale.

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;
    });

Ricerca binaria su range ordinati

Una volta ordinato il range, usi std::lower_bound, std::upper_bound e std::binary_search per ricerche in O(log N).

Verifica rapida

Quale algoritmo mantiene l'ordine relativo degli elementi equivalenti dopo l'ordinamento?

Riepilogo

Usi std::sort per l'ordinamento generale, std::stable_sort quando l'ordine degli elementi equivalenti è importante, std::partial_sort per i primi k elementi, std::nth_element per la selezione e std::partition/std::stable_partition per il raggruppamento.

Domande Frequenti

La lezione «Ordinamento e partizionamento: sort, stable_partition» è gratuita?

Sì — il testo completo di «Ordinamento e partizionamento: sort, stable_partition» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso C++ Academy, passa a CoddyKit PRO. Il corso C++ Academy include 4 lezioni in totale.

Cosa imparerò in «Ordinamento e partizionamento: sort, stable_partition»?

Ordini e partizioni i contenitori con std::sort e std::stable_partition Eserciti C++ Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare C++ Academy?

Non è richiesta alcuna esperienza precedente. C++ Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.

Quanto tempo richiede la lezione «Ordinamento e partizionamento: sort, stable_partition»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione C++ Academy?

Sì. Ogni lezione C++ Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

  1. Algoritmi non modificanti: find, count, all_of
  2. Algoritmi modificanti: transform, copy_if, replace
  3. Ordinamento e partizionamento: sort, stable_partition
  4. Algoritmi numerici: accumulate, reduce, transform_reduce
← Torna a C++ Academy