Сортировка по абсолютному значению с использованием собственного компаратора

Question

Справочная информация:

Мне задали этот вопрос на собеседовании и я не смог пройти все контрольные примеры.

Вопрос:

Сортировка по абсолютному значению

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

Примеры:

input: arr = [2, -7, -2, -2, 0]

вывод: [0, -2, -2, 2, -7]

Моя попытка:

  std::sort(nums.begin(), nums.end(), [](int a, int b) {
    if(abs(a) < abs(b))
      return true;
    return a < b ? (a < 0 && abs(a) > b) : (b < 0 && abs(b) > a);
  });

Я пропускаю некоторые тестовые примеры, но не все, например

Input: [2,-7,-2,-2,0]
Expected: [0,-2,-2,2,-7]
Actual: [0, -2, -7, 2, -2 ]

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

Answer 1

Компаратор для std::sort является , а не произвольной двоичной функцией. Следует установить строгий слабый порядок . В противном случае поведение не определено.

Давайте посмотрим на компаратор (ранее предложенный, теперь исправленный)

bool comp(int a, int b) {
    if (std::abs(a) != std::abs(b))
        return std::abs(a) < std::abs(b);
    return (a < 0);
}

Первое свойство слабого порядка:

Для всех a, comp(a, a) == false

Это свойство не работает для a = -1: comp(-1, -1) == true.

Так что comp не определяет слабое упорядочение ивызов std::sort с ним приводит к неопределенному поведению!

Answer 2

std::sort(nums.begin(), nums.end(),
    [](int a, int b) {
        if (abs(a) != abs(b))  //a & b not equal in absolute value
            return abs(a) < abs(b);
        return (a < b);       //a & b have equal absolute value -> check sign
    });

Обновление: исправлено второе условие для return (a < b) из (a < 0).