Come si può ordinare una lista?

Per ordinare una lista in C++, puoi utilizzare i seguenti approcci:

1. std::sort: Algoritmo iterativo della libreria standard.
2. std::list::sort: Metodo di ordinamento per std::list, che utilizza riferimenti agli elementi invece di iteratori.

Confronto:

Metodo	Applicato a	Complessità	Memoria aggiuntiva	Stabilità	Caratteristiche
std::sort	Accesso casuale (ad esempio, std::vector, std::deque)	$O(N \log N)$	$O(\log N)$ (in media)	Non stabile	Per std::list inefficiente a causa dell'accesso casuale lento.
std::list::sort	std::list	$O(N \log N)$	$O(1)$	Stabile	Efficiente per std::list, poiché non richiede spostamenti di elementi.

Esempio di utilizzo di std::list::sort:

#include <list>
#include <iostream>

int main() {
    std::list<int> mia_lista = {5, 2, 8, 1, 9};
    
    // Ordinamento crescente
    mia_lista.sort();
    
    for (int val : mia_lista) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // Ordinamento decrescente usando un comparatore
    mia_lista.sort([](int a, int b){ return a > b; }); 

    for (int val : mia_lista) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}