Hoe kan een lijst worden gesorteerd?

Om een lijst in C++ te sorteren, kunt u de volgende benaderingen gebruiken:

1. std::sort: Iteratief algoritme uit de standaardbibliotheek.
2. std::list::sort: Sorteermethode voor std::list, die verwijzingen naar de elementen gebruikt in plaats van iterators.

Vergelijking:

Methode	Toepasbaar op	Complexiteit	Extra geheugen	Stabiliteit	Kenmerken
std::sort	Willekeurige toegang (bijvoorbeeld, std::vector, std::deque)	$O(N \log N)$	$O(\log N)$ (gemiddeld)	Onstabiel	Voor std::list niet efficiënt vanwege trage willekeurige toegang.
std::list::sort	std::list	$O(N \log N)$	$O(1)$	Stabiel	Efficiënt voor std::list, omdat het geen elementen hoeft te verplaatsen.

Voorbeeld van gebruik van std::list::sort:

#include <list>
#include <iostream>

int main() {
    std::list<int> mijn_lijst = {5, 2, 8, 1, 9};
    
    // Oplopende sortering
    mijn_lijst.sort();
    
    for (int waarde : mijn_lijst) {
        std::cout << waarde << " ";
    }
    std::cout << std::endl;

    // Aflopende sortering met comparator
    mijn_lijst.sort([](int a, int b){ return a > b; }); 

    for (int waarde : mijn_lijst) {
        std::cout << waarde << " ";
    }
    std::cout << std::endl;

    return 0;
}