Cum se poate sorta o listă?

Pentru sortarea unei liste în C++, puteți utiliza următoarele abordări:

1. std::sort: Algoritm iterativ din biblioteca standard.
2. std::list::sort: Metoda de sortare pentru std::list, care utilizează referințe la elemente în loc de iteratori.

Comparatie:

Metodă	Se aplică la	Complexitate	Memorie suplimentară	Stabilitate	Caracteristici
std::sort	Acces aleator (de exemplu, std::vector, std::deque)	$O(N \log N)$	$O(\log N)$ (în medie)	Nesigur	Pentru std::list ineficient din cauza accesului aleator lent.
std::list::sort	std::list	$O(N \log N)$	$O(1)$	Stabil	Eficient pentru std::list, deoarece nu necesită mutarea elementelor.

Exemplu de utilizare a std::list::sort:

#include <list>
#include <iostream>

int main() {
    std::list<int> lista_mea = {5, 2, 8, 1, 9};
    
    // Sortare crescătoare
    lista_mea.sort();
    
    for (int val : lista_mea) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // Sortare descrescătoare folosind comparator
    lista_mea.sort([](int a, int b){ return a > b; }); 

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

    return 0;
}