Как с qsort отсортировать массив так, чтобы нечетные числа остались на своем месте?

#c #qsort

Привет! Не получается решить задачу (ниже есть моя попытка решения):



Напечатайте входную последовательность натуральных чисел, отсортировав ее по возрастанию
четных чисел, нечетные остаются на своих местах с помощью страндартной функции языка
с qsort.

Входные данные

Целое число 0 < N ≤ 1000. Затем N натуральных чисел, не превышающих 30000, через пробел.

Выходные данные

Нечетные числа остаются на своих местах, четные отсортированы по возрастанию.



Написал такую функцию сравнения:

int cmp_int(const void * p1, const void * p2) {
    int s1 = *(int*)p1; int s2 = *(int*)p2;
    if ((s1 % 2 == 0) && (s2 % 2 == 0)) {
      if (s1 < s2) return -1;
      else if (s1 > s2) return 1;
    }
  return 0;
}


Но она не проходит тест для массива "5 122 3 26 48". Получается "26 3 48 122 5",
а должно "5 26 3 48 122". Не знаю, как пропустить нечетные числа: если писать "return
0" при встрече с нечетными, то программа случайно сортирует два числа, которые она
в данный момент сравнивает. Что нужно исправить?
    

Ответы

Ответ 1

Можно так, конечно:
1. Переписать чётные числа в отдельный массив.
2. Отсортировать полученный массив.
3. Последовательно заменить чётные числа исходного массива отсортированными числами
из полученного массива.

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

P.S. Но можно и по полной программе:
Алгоритм такой:
1. Создаём flip-массив (в котором ключи и элементы поменялись ролями), применяя flip-функцию
к исходному массиву.
2. Проводим сортировку с дополнительной опцией:
"если выполнены условия перестановки чётных элементов, то произвести обмен значениями
для соответствующих элементов flip-массива".
3. Cортируем flip-массив, сохраняя связи между ключами и элементами.
4. Применяем flip-функцию к flip-массиву. 

На PHP это выглядит так:

$common = array(5,122,3,26,48);
$flip = array_flip($common);
var_dump($common);
var_dump($flip);
$changes = array();
usort($common, function($a,$b) use(&$flip) { 
    if($a==$b) return 0;                        
    if(!(($a|$b)%2) && ($a>$b)){                // при перестановке чётных элементов
        $temp = $flip[$a];                      // обмениваем их ключи
        $flip[$a] = $flip[$b];
        $flip[$b] = $temp;
    }
    return $a-$b;
});
var_dump($common);
var_dump($flip);
asort($flip);
$common = array_flip($flip);
var_dump($common); 


Результаты:


array (size=5)
  0 => int 5
  1 => int 122
  2 => int 3
  3 => int 26
  4 => int 48
array (size=5)
  5 => int 0
  122 => int 1
  3 => int 2
  26 => int 3
  48 => int 4
array (size=5)
  0 => int 3
  1 => int 5
  2 => int 26
  3 => int 48
  4 => int 122
array (size=5)
  5 => int 0
  122 => int 4
  3 => int 2
  26 => int 1
  48 => int 3
array (size=5)
  0 => int 5
  1 => int 26
  2 => int 3
  3 => int 48
  4 => int 122


Благодарности: VladD, Mike.


Ответ 2

Предположите, что p1 всегда левее в массиве чем p2 и давайте ответ в соответствии с этим