Jak lze seřadit seznam?

Pro třídění seznamu v C++ můžete použít následující přístupy:

1. std::sort: Iterativní algoritmus ze standardní knihovny.
2. std::list::sort: Metoda třídění pro std::list, která používá odkazy na prvky místo iterátorů.

Porovnání:

Metoda	Používá se na	Složitost	Další paměť	Stabilita	Vlastnosti
std::sort	Náhodný přístup (například std::vector, std::deque)	$O(N \log N)$	$O(\log N)$ (průměrně)	Nestabilní	Pro std::list neefektivní kvůli pomalému náhodnému přístupu.
std::list::sort	std::list	$O(N \log N)$	$O(1)$	Stabilní	Efektivní pro std::list, protože nevyžaduje přesun prvků.

Příklad použití std::list::sort:

#include <list>
#include <iostream>

int main() {
    std::list<int> muj_seznam = {5, 2, 8, 1, 9};
    
    // Seřadit vzestupně
    muj_seznam.sort();
    
    for (int hodnota : muj_seznam) {
        std::cout << hodnota << " ";
    }
    std::cout << std::endl;

    // Seřadit sestupně s porovnávačem
    muj_seznam.sort([](int a, int b){ return a > b; }); 

    for (int hodnota : muj_seznam) {
        std::cout << hodnota << " ";
    }
    std::cout << std::endl;

    return 0;
}