Как работает сортировка по убыванию в c ++?

Question

Я искал, как отсортировать вектор в порядке убывания, тогда я нашел этот код

std::sort(numbers.begin(), numbers.end(), std::greater<int>());

Это работает, но я просто хочу знать, как это работает

Answer 1

Третий аргумент std::sort - это функтор / функция, которая возвращает true, если первый аргумент должен быть помещен перед вторым элементом в порядке сортировки.

std::greater<int>::operator()(...) возвращает true, если первый аргумент больше, чем второй аргумент.

Следовательно, использование std::greater<int>() в качестве третьего аргумента для std::sort приводит к сортировке объектов в порядке убывания.

Answer 2

В документации для std::sort ( здесь среди других мест) говорится что-то вроде

Сортирует элементы в диапазоне [первый, последний) в порядке возрастания.

Это удобное упрощение, но оно сбивает с толку, когда вы не хотите по возрастанию.

Полезнее думать, что sort реорганизует ваш диапазон в соответствии с некоторой функцией - назовем ее pre - которая говорит для любой пары элементов, какой из них должен предшествовать (предшествовать) другому.

То есть функция выглядит примерно так:

bool pre(int a, int b); // return true if a should precede b

Поведение по умолчанию , если вы не укажете что-то другое, заключается в использовании std::less, что примерно так и сделает:

bool less(int a, int b) { return a<b; }

и это значение по умолчанию (где меньшее значение всегда предшествует большему) дает результат, отсортированный в порядке возрастания.

Если вы укажете std::greater, вы говорите, что большее значение всегда должно предшествовать меньшему (потому что если greater(a,b)==true, это означает, что a>b, а также что a будет предшествовать b в выводе).

Итак, это то же самое, что сказать, что результат отсортирован в порядке убывания.

---

NB. Я назвал сравнение pre и потому, что оно говорит вам, какие элементы должны предшествовать каким, а также потому, что это предикат (в частности, BinaryPredicate и даже больше в частности, Сравнение ).

Answer 3

Функция std::sort ожидает, что вы ^{& dagger;} дадут ей функцию, которая скажет ей, как сортировать диапазон в порядке возрастания, поэтому по умолчанию она будет использовать что-то вроде std::less<int>().

Предоставляя функцию с противоположным эффектом (т. Е. std::greater<int>()), вы превращаете это ожидание буквально с ног на голову, в результате чего получается абсолютно законное «зеркальное отображение» поведения по умолчанию. То есть обратная сортировка.

Другой способ объяснить это состоит в том, что на каждом шаге своего алгоритма, когда он хочет знать, должен ли один элемент A идти "перед" другим элементом B , он спросит std::greater<int>(), что скажет ему: да, один элемент A должен идти "перед" другим элементом B , если A > B, и вот вам.

 5   3   2   1
   >   >   >

Это противоречит поведению по умолчанию, которое использует что-то вроде < вместо:

 1   2   3   5
   <   <   <

_{^{& dagger;} Конечно, вы можете наделить его функцией, которая определяет любой другой порядок, который вам нравится (с учетом определенных ограничений), так что вариантов гораздо больше. Здесь я исследую только две наиболее очевидные методологии сортировки.}