Как може да се сортира списък?

За сортиране на списък в C++ можете да използвате следните подходи:

1. std::sort: Итеративен алгоритъм от стандартната библиотека.
2. std::list::sort: Метод за сортиране за std::list, който използва препратки към елементите, а не итератори.

Сравнение:

Метод	Приложим към	Сложност	Допълнителна памет	Стабилност	Характеристики
std::sort	Случаен достъп (например, std::vector, std::deque)	$O(N \log N)$	$O(\log N)$ (средно)	Нестабилен	За std::list неефективен поради бавен случайен достъп.
std::list::sort	std::list	$O(N \log N)$	$O(1)$	Стабилен	Ефективен за std::list, тъй като не изисква преместване на елементите.

Пример за използване на std::list::sort:

#include <list>
#include <iostream>

int main() {
    std::list<int> моя_списък = {5, 2, 8, 1, 9};
    
    // Сортиране във възходящ ред
    моя_списък.sort();
    
    for (int стойност : моя_списък) {
        std::cout << стойност << " ";
    }
    std::cout << std::endl;

    // Сортиране в низходящ ред с помощта на компаратор
    моя_списък.sort([](int a, int b){ return a > b; }); 

    for (int стойност : моя_списък) {
        std::cout << стойност << " ";
    }
    std::cout << std::endl;

    return 0;
}