Привет! Не получается решить задачу (ниже есть моя попытка решения):
Напечатайте входную последовательность натуральных чисел, отсортировав ее по возрастанию четных чисел, нечетные остаются на своих местах с помощью страндартной функции языка с 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
Комментариев нет:
Отправить комментарий