4

Изучаю JavaScript, метод sort() Все в общем-то понятно было, но далее я встретил пример из учебника с методом Math.random() :

Задание:

Используйте функцию sort для того, чтобы «перетрясти» элементы массива в случайном порядке.

Решение(дано в учебнике, но без объяснений):

Функция сортировки должна возвращать случайный результат сравнения. Используйте для этого Math.random.

Обычно Math.random() возвращает результат от 0 до 1. Вычтем 0.5, чтобы область значений стала [-0.5 ... 0.5).

var arr = [1, 2, 3, 4, 5];

function compareRandom(a, b) {
  return Math.random() - 0.5;
}

arr.sort(compareRandom);

alert( arr ); // элементы в случайном порядке, например [3,5,1,2,4]

Долго думал. Я так понимаю действие данной return Math.random() - 0.5; строчки: "универсальный алгоритм сортировки" берет два числа(a и b), далее запускается return Math.random() - 0.5; если число меньше ноля, первым в записи идет a(сортировка поставит a по меньшему индексу), если больше ноля, первым идет в записи b( сортировка поставит b по меньшему индексу). Чтобы было нагляднее, я нарисовал схему(на примере(2, 4)):

введите сюда описание изображения

1). Мой первый вопрос, правильно ли я понимаю работу данной функции. Также хочется узнать доступным языком принцип действия "универсальный алгоритм сортировки".

// ######

На данном этапе изучения JavaScript я понял, что в функции, в скобках передаются значения, и конечно они используются в самой функции, вот пример:

function compareNumeric(a, b) {
  return a - b;
}

var arr = [ 1, 2, 15 ];

arr.sort(compareNumeric);

alert(arr);  // 1, 2, 15

Но в первом примере, в функции, a и b не используются, а сразу идет return, поэтому я попробовал совсем их убрать и записал так:

var arr = [1, 2, 3, 4, 5];

function compareRandom() {
  return Math.random() - 0.5;
}

arr.sort(compareRandom);

alert( arr );

Удивительно, но все работает и так.

2). Мой второй вопрос, в данном случае можно в скобках совсем не указывать a и b? Почему тогда в учебнике запись (a,b)

1
  • Насколько я знаю, в JS можно всегда не указывать параметры функции и брать из аргументов их. Но это неудобно, поэтому и пишут параметры в явном виде чтобы подчеркнуть сколько их будет (по сути это вопрос стиля кода, не более). Принцип вы понимаете правильно, но будьте аккуратный с такими сортировками, в ряде языков получите совсем не то, что вы ожидание, т.к. оператор сравнения должен быть антисимметричным, транзитивным и антирефлексивным.
    – pavel
    19 фев 2017 в 7:02

1 ответ 1

3

"но все работает и так" - где ж работает? Массив ведь не отсортирован. Такая compare функция возвращает случайный результат, в массиве после "сортировки" элементы будут идти в произвольном порядке.

var arr = [1, 2, 3, 4, 5];
var count = 0;
function compareRandom() {
  count++;
  return Math.random() - 0.5;
}

arr.sort(compareRandom);

console.log(count);
console.log( arr );

Обратите внимание на меняющееся значение count. Теоретически, такая "сортировка" может никогда не закончиться, так как два сравнения одной и той же пары чисел могут дать противоположные результаты.

А, по пунктам:

  1. Да, понимаете правильно.
  2. Да, можно не указывать.

var arr = [1, 2, 3, 4, 5];
var count = 0;
function compareNumeric(a, b) {
  count++;
  return a - b;
}

arr.sort(compareNumeric);

console.log(count);
console.log( arr );

Во время нормальной (с compareNumeric) сортировки массива необходимо выполнить определенное количество сравнений пар элементов. В зависимости от начального расположения элементов в массиве, некоторые пары будут сравниваться несколько раз. Логика сортировки базируется на том, что повторные сравнения чисел 2 и 3 возвращают результат, показывающий, что три больше двух. Если у этих повторных сравнений результат - случайный, то как в конце концов дожны располагаться числа 2 и 3 в окончательном отсортированном массиве?

2
  • Да, в учебнике, в задании, как раз и была задача, чтобы элементы массива после сортировки шли в случайном порядке(про это, я добавил в свой вопрос). Про count я не очень понял; то что там счетчик меняется, это мне понятно, но чтобы понять почему он меняется видимо и нужно изучить "универсальный алгоритм сортировки", реализованный внутри самого интерпретатора JavaScript, верно? и видимо это отдельная тема. 20 фев 2017 в 11:45
  • два сравнения одной и той же пары чисел могут дать противоположные результаты - никто не сравнивает одни и те же числа повторно(кроме bogosort), незачем перепроверять алгоритм сравнения. Число сравнений меняется, потому что по сути это разные входы, числам соответствуют разные веса. Перемешайте массив перед сортировкой и проинспектируйте число сравнений во втором сниппете.
    – vp_arth
    21 фев 2017 в 13:53

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.