Страницы

Поиск по вопросам

вторник, 4 июня 2019 г.

Как с 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. Переписать чётные числа в отдельный массив. 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

Комментариев нет:

Отправить комментарий