Недавно я прочитал интригующую запись в блоге, в которой описывалась техническая задача для собеседования. Задача состоит в том, чтобы отсортировать по возрастанию массив строк, содержащих номера версий программного обеспечения, например. 1.2, 3.43, 3.33. Решил заняться проблемой самостоятельно, так как сам готовлюсь к интервью.

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

Собственный метод JavaScript Sort сортирует, сравнивая последовательные элементы соседних строк. Сравнение основано на значениях кодовых единиц символов UTF-16 — для наших целей это буквенно-цифровой порядок.

Если первый элемент A ‹ B, нет необходимости менять местами.

Если A › B или если в этой позиции в B нет символа, позиции элементов необходимо перевернуть.

Если A = B, сравнивается следующий символ, и так далее.

Для строк этот метод сортирует, как и ожидалось:

Для нашей задачи частичные числа, которые остаются однозначными, сортируются, как и ожидалось:

arr = ["1.0", "3.3.3", "3.3", "1.6", "5" ]

arr.sort() = [“1.0”, “1.6”, “3.3”, “3.3.3”, “5”]

Однако, как только мы отсортируем случай, когда некоторые частичные версии длиннее других, мы столкнемся с проблемой, используя метод стандартной сортировки, как показано ниже:

arr = [‘1.5’, ‘1.22’, ‘3.3’]
arr.sort() = [‘1.22’, ‘1.5’, ‘3.3’]

Причина в том, что собственный метод Sort преобразует все элементы в строки перед выполнением сравнения, что может привести к неожиданным результатам при сравнении чисел!

10 сортируется перед 2, потому что 2 > 1 с первой позиции. Метод сортировки не учитывает, что 10 больше 2!

Решение заключается в использовании пользовательской функции сравнения с нашим методом сортировки. Метод sort ищет возвращаемые этой функцией значения, чтобы определить порядок сортировки. Пользовательская функция сравнения позволяет нам сравнивать целые числа без преобразования их в строки. Возвращаемое значение функции определяет способ сортировки элементов массива.

Если вернуть › 0, поменять местами элементы
Если вернуть ‹ 0, не менять местами элементы
Возврат 0 означает, что элементы равны

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

arr.sort(function(a, b){
return a — b
})

Теперь, имея это в виду, мы можем создать пользовательскую функцию сравнения для сортировки номеров версий.

Первый шаг — проверить, равны ли две сравниваемые строки, и в этом случае мы знаем, что нужно вернуть 0, и закончили с этими элементами. Затем разделите каждый номер версии на массивы, используя «.» в качестве точки разделения, чтобы мы могли сравнить каждую из позиций версии по отдельности.

'1.10.4'.split('.') = ['1','10','4']

Теперь мы находим версию с наибольшим количеством элементов версии (это будет длина нашего цикла for), используя Math.max() .

Для фактического сравнения мы перебираем каждую частичную версию по индексу. Нам нужно преобразовать разделы в целые числа с помощью parseInt(), чтобы их можно было вычислить независимо от количества цифр в каждом значении.

Теперь мы можем проверить, первое или второе число больше. Кроме того, если разделы равны, мы проверяем, является ли текущий партиал последним. Если это так, мы знаем, что другая часть будет больше.

Наконец, мы используем нашу функцию сравнения с сортировкой и обращаем результаты, чтобы получить список по убыванию:

Несортированный:

[“1.3.0.9”, “0.2.0”, “3.1.2”, “0.1.6”, “5.0.0”, “3.3.3.3”, “3.3.3.3.3”, “3.10”, “0.2.0”]

Отсортировано:

[“5.0.0”, “3.10”, “3.3.3.3.3”, “3.3.3.3”, “3.1.2”, “1.3.0.9”, “0.2.0”, “0.2.0”, “0.1.6”]

Вот и все!

function comparePartials(a, b) {
if (a === b) {
  return 0;
}
let splitA = a.split('.');
let splitB = b.split('.');
const length = Math.max(splitA.length, splitB.length);
for (let i = 0; i < length; i++) {
//FLIP
if (parseInt(splitA[i]) > parseInt(splitB[i]) ||
  ((splitA[i] === splitB[i]) && isNaN(splitB[i + 1]))) {
  return 1;
}
//DONT FLIP
if (parseInt(splitA[i]) < parseInt(splitB[i]) || 
  ((splitA[i] === splitB[i]) && isNaN(splitA[i + 1]))) {
  return -1;
  }
}
}
// Performing the actual sort
function sortVersions(arr) {
  return arr.sort(comparePartials).reverse()
}