Как порядок возникновения поддерживается данными условиями

Question

Я наткнулся на этот GeeksForGeeks, который гласил: «Переставьте положительные и отрицательные числа, используя встроенную функцию сортировки, чтобы все отрицательные целые числа появлялись перед всеми положительными целыми числами, и порядок появления должен поддерживаться .

Функция сравнения функции sort () была изменена для достижения этой цели.

bool comp(int a, int b)
{
    // This is to maintain order
    if ((a >= 0 && b >= 0) || (a < 0 && b < 0))
        return false;

    // Swapping is must
    if ((a >= 0) && (b < 0))
        return false;
    return true;
}

Но как получается, что заказ поддерживается этим блоком:

if ((a >= 0 && b >= 0) || (a < 0 && b < 0))
    return false;

Answer 1

Функция comp нарушает строгий слабый порядок для

if ((a >= 0 && b >= 0) || (a < 0 && b < 0))
    return false;

Если a равно 0, а b равно + ve, то a меньше b, но возвращается false, а не true

Попробуйте

bool comp(int a, int b)
{
   const int first = ((a < 0) ? -1 : (a == 0) ? 0 : 1);
   const int second = ((b < 0) ? -1 : (b == 0) ? 0 : 1);

   return (first < second);
}

и подключите его к std :: stable_sort

Answer 2

Но как получается, что порядок поддерживается этим блоком:

Заказ не "поддерживается" в компараторе.Компаратор может только сказать, что после сортировки два элемента a и b должны быть в итоге

• a до b
• a после b
• a вместе с b (до тех же элементов, после тех же элементов)

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

Answer 3

Похоже, что это оригинальная статья

https://www.geeksforgeeks.org/rearrange-positive-negative-numbers-using-inbuilt-sort-function/

Как это (вроде) работает: std :: sort переставляет все в соответствии с компаратором.Этот компаратор основан на том, что «все отрицательные числа точно равны друг другу. Все положительные числа точно равны друг другу. Отрицательные числа меньше положительных чисел».

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

Что не так:

1) Функция сравнения некорректно обрабатывает 0. Она дает неправильные ответы, и, что еще хуже, онадает ответы, которые нарушают строгий слабый порядок.(см. ниже)

2) std :: sort не является стабильной сортировкой.Это не гарантирует сохранение порядка.Им повезло на одном наборе данных.Если бы они использовали std :: stable_sort и правильную функцию сравнения, это была бы «встроенная функция», отвечающая требованиям.Но одна функция сравнения не может сделать алгоритм устойчивым.См. В чем разница между std :: sort и std :: stable_sort? или просто посмотрите в верхней части документа на http://www.cplusplus.com/reference/algorithm/sort/

3) Они делают причудливые трюки, чтобы придуматьс решением сложности O (n log n) для тривиально простой задачи O (n).Таким образом, помимо неправильности в нескольких точках, это неэффективно без всякой веской причины.

Возможно, им следовало бы рассмотреть https://en.cppreference.com/w/cpp/algorithm/stable_partition, если нам разрешено просто исключать нули в данных.

---

Вот определение строгого слабого упорядочения (также связанное с некоторыми программистами) https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings

For all x in S, it is not the case that x < x (irreflexivity).
For all x, y in S, if x < y then it is not the case that y < x (asymmetry).
For all x, y, z in S, if x < y and y < z then x < z (transitivity).
For all x, y, z in S, if x is incomparable with y (neither x < y nor y < x hold), and y is incomparable with z, then x is incomparable with z (transitivity of incomparability).

Обратите внимание, что comp (0, что угодно) возвращает false, поэтому 1 <0, чтопозволяет легко нарушать транзитивность, в дополнение к очевидным ошибкам. </p>