3

Подскажите как отсортировать вектор по модулю элементов?

то есть, если вектор [-1,4,7,9,-97,54,-114],то ответ [-1,4,7,9,54,-97,-114].

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

Руслан
  • 111
  • 7

1 Answers1

7

Сортировка с компаратором:

sort(v.begin(),v.end(),[](int a, int b){ return abs(a) < abs(b); }
Harry
  • 221,325
  • почему надо использовать меньше, если мы хотим сохранить порядок равных по модулю элементов исходного массива? Например если был массив 1 -1 -1 1, чтобы он после сортировки остался таким же. Сравнивая первые 2 элемента мы берем a=1 и b=-1, компаратор возвращает false и логично поменять элементы местами в сортированном массиве. Но на деле я вижу обратное, что с < все работает как надо, а с <= порядок меняется. – Evgeny Sep 08 '21 at 06:39
  • Вообще гарантируется ли сохранение порядка?) – Evgeny Sep 08 '21 at 06:45
  • 1
    @Evgeny Для этого надо использовать stable_sort. А что касается <=, то, увы, вы нарушаете главный принцип строгого упорядочения. И с таким компаратором сортировка может вообще не сработать. – Harry Sep 08 '21 at 07:25
  • окей, сравниваются два элемента a=1 b=-1. Компаратор возвращает false. Почему элементы не меняются местами? Я запустил stable_sort, у меня 2 числа в векторе 1 -1. И со знаком < порядок сохранился. – Evgeny Sep 08 '21 at 07:37
  • Еще раз — sort не обеспечивает устойчивую сортировку, когда элементы с одинаковыми значениями (т.е. те — обратите внимание! — для которых ложны одновременно и сравнение comp(a,b), и comp(b,a)! Скажите теперь — если comp — это <= — то будет ли работать это правило проверки на равенство?...) располагаются в том же порядке, что и до сортировки. Для этого следует использовать другой алгоритм. – Harry Sep 08 '21 at 09:21
  • Мой вопрос скорее в другом. Если comp возвращает false, почему равные по модулю элементы не меняются местами??? – Evgeny Sep 08 '21 at 09:30
  • А зачем им меняться?... Раз они равны по модулю — они рассматриваются алгоритмом как равные, а значит, их порядок между собой может быть каким угодно. – Harry Sep 08 '21 at 09:33
  • Потому что если comp вернул true, то тогда понятно, что a < b и их менять не надо. А если вернул false, то надо менять. Что не так в этой логике? – Evgeny Sep 08 '21 at 09:35
  • Ваша логика годится для, например, пузырьковой сортировки. Но с чего вы решили, что sort действует так же?... – Harry Sep 08 '21 at 10:17
  • То есть вы хотите сказать что comp для каждой пары элементов вызывается дважды и уже затем решается, менять элементы или нет? – Evgeny Sep 08 '21 at 10:19
  • Если вызывать comp для каждой пары — это неэффективная сортировка O(N^2). Словом, посмотрите что-то из книг в этом вопросе — https://ru.stackoverflow.com/q/576507/195342 – Harry Sep 08 '21 at 10:37
  • Я знаю как работает алгоритм сортировки. Мой вопрос лишь в том как компоратор между собой различает false в случае если элементы равны и в случае если они не равны. Казалось бы, надо менять местами, а получается что при равенстве они не меняются. То есть когда компаратор сравнивает пару элементов он это делает дважды в разном порядке, а затем уже выносит вердикт. Верно? – Evgeny Sep 08 '21 at 11:10