Подготовка к тех.интервью

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

Дан массив:

const nums = [1,9,4,2,3,6,7,1,5];

Необходимо написать функцию sortOddNums, которая принимает аргументом массив чисел и возвращает массив чисел, в котором нечётные числа отсортированы по возрастанию, а чётные оставлены на своих местах:

sortOddNums(nums) // [1,1,4,2,3,6,5,7,9];

Примеры:

[1,9,4,2,3,6,7,1,5] --> [1,1,4,2,3,6,5,7,9]
[1,4,3,7,9,5,2,1,6] --> [1,4,1,3,5,7,2,9,6]
[5,3,6,234,67,63,212,24,11] --> [3,5,6,234,11,63,212,24,67]
[1,2,3,4,5,6,7,8,9] --> [1,2,3,4,5,6,7,8,9]
[10,356,11,258,2,978,3,15,4] --> [10,356,3,258,2,978,11,15,4]

Теория по задаче

Задача относится к классу «частичная сортировка с фиксацией позиций»: сортируются только элементы, удовлетворяющие условию (нечётные), а остальные (чётные) сохраняют исходные индексы. Решение удобно строить как «разделение → сортировка → сборка результата», потому что обычная сортировка всего массива нарушит требование «чётные остаются на своих местах».

Как определить чётность и нечётность

В JavaScript чаще всего применяется оператор остатка %:

  • Чётное число: n % 2 === 0.
  • Нечётное число: n % 2 !== 0.
Оператор % в JavaScript является оператором остатка, а не математического модуля: результат сохраняет знак делимого. Например, -3 % 2 даёт -1, и условие нечётности n % 2 !== 0 по-прежнему корректно определяет нечётные числа (остаток не равен нулю).
Если в массив могут попадать нецелые числа (например, 3.5), то понятия «чётное/нечётное» теряют смысл. Для учебной задачи предполагаются целые числа.

Почему нельзя «просто отсортировать»

У Array.prototype.sort() есть две особенности, которые важны:

  1. Без компаратора элементы сортируются как строки (лексикографически), что может дать неправильный порядок для чисел (например, 100 может оказаться «меньше» 2 при строковом сравнении).
  2. sort() изменяет массив «на месте», то есть мутация может привести к тому, что исходные данные будут потеряны.

Отсюда следует правило: для сортировки чисел необходимо передавать компаратор (a, b) => a - b, а при необходимости сохранять исходный массив — сортировать копию.

Пример корректной числовой сортировки (демонстрационный):

const arr = [9, 1, 10, 2];
arr.sort((a, b) => a - b); // [1, 2, 9, 10]

Базовый алгоритм «разделение → сортировка → сборка»

Алгоритм удобно описывать так:

  1. Выделение: из исходного массива выбираются все нечётные элементы (например, через filter или циклом).
  2. Сортировка: полученный список нечётных сортируется по возрастанию числовым компаратором.
  3. Сборка: создаётся новый массив-результат, в котором:
    • на позициях с чётными числами остаются исходные значения;
    • на позициях с нечётными числами последовательно подставляются элементы из отсортированного списка.

Схема потока данных (на примере):

исходный nums:    [1, 9, 4, 2, 3, 6, 7, 1, 5]
нечётные odds:    [1, 9, 3, 7, 1, 5]
отсорт. odds:     [1, 1, 3, 5, 7, 9]
результат:        [1, 1, 4, 2, 3, 6, 5, 7, 9]

Ключевая идея: чётные значения вообще не перемещаются, изменяются только значения в тех индексах, где изначально стояли нечётные числа.

Почему `map()` удобно для сборки

map() проходит массив по индексам слева направо и создаёт новый массив той же длины. Это позволяет на каждом шаге принимать решение: если текущий элемент нечётный, то подставляется следующее значение из отсортированного списка нечётных, иначе возвращается исходное чётное значение.

Механика указателя i:

  • i хранит «номер следующего нечётного числа» в отсортированном массиве odds.
  • Каждый раз при встрече нечётного элемента в исходном массиве берётся odds[i], после чего i увеличивается на 1.

Фрагмент (демонстрационный):

let i = 0;
const result = nums.map((n) => (n % 2 !== 0 ? odds[i++] : n));

Сложность (время и память)

Пусть n — длина массива, k — количество нечётных элементов:

  • Время: выделение нечётных — O(n), сортировка нечётных — O(k log k), сборка результата — O(n). Итог: O(n + k log k).
  • Память: список нечётных — O(k), новый массив результата — O(n) (если требуется вернуть новый массив).
Если нечётных мало (k заметно меньше n), сортировка выполняется быстрее, чем сортировка всего массива длины n, потому что сортируется только подмножество.

Частые ошибки и как их избегать

  • Ошибка: сортировка без компаратора sort() для чисел; исправление: обязательно задавать (a, b) => a - b.
  • Ошибка: вызов sort() на массиве, который нельзя менять; исправление: сортировать копию (slice(), [...arr]) или применять toSorted().
  • Ошибка: подмена нечётных чисел без сохранения порядка обхода; исправление: подставлять нечётные строго по порядку индексов слева направо (подходит map() или цикл по исходному массиву).
  • Ошибка: попытка «переставлять элементы местами» в исходном массиве; исправление: не перемещать чётные вообще, а только заменять значения в нечётных позициях.

Кратко: в задаче необходимо сортировать только нечётные элементы, сохраняя чётные на исходных индексах, поэтому решение строится как: сбор нечётных → числовая сортировка (a, b) => a - b → последовательная подстановка обратно в нечётные позиции. Важно помнить, что sort() мутирует массив, поэтому при сохранении исходных данных требуется сортировать копию или использовать toSorted().