1

Объясните пожалуйста как и каким образом работает данная сортировка. Так как встретив эту задачу хотелось бы больше осмыслить процесс происходящий за данной сортировкой.

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]
2
  • Если вам дан исчерпывающий ответ, отметьте его как верный (галка напротив выбранного ответа). 7 апр 2016 в 4:40
  • Кстати, результат сортировки для недетерминированных функций полностью зависит от реализации движка JS. Так что в общем случае я бы не был на 100% уверен, что порядок элементов будет случайным. 7 апр 2016 в 14:15

1 ответ 1

5

Вот, для начала, как работает метод Array.prototype.sort([compareFunction]). Он принимает в качестве аргумента необязательный параметр [compareFunction], который представляет из себя функцию, определяющую порядок сортировки.

Например:

function compare(a, b) {
  if (a "меньше" b согласно какому-то критерию) {
    return -1;
  }
  if (a "больше" b согласно какому-то критерию) {
    return 1;
  }
  // a == b
  return 0;
}

Тогда, если compare(a, b) меньше 0, сортировка поставит a по меньшему индексу, чем b, то есть, a идёт первым. И наоборот, если compare(a, b) больше 0, сортировка поставит b по меньшему индексу, чем a.

Таким образом, принимая во внимание, что Math.random() возвращает псевдослучайное число с плавающей точкой в интервале [0; 1), мы получаем диапазон возвращаемых значений функции function compareRandom(a, b) в интервале [-0,5; 0,5). Исходя из этого, у нас шансы (примерно) 50%/50% получения негативного (a < b) значения функции, и такие-же шансы получения позитивного (a > b) значения. И так для каждого элемента, что участвует в сравнении. Соответственно, в вашей ситуации, arr.sort(compareRandom); после каждого вызова отсортирует массив по-разному.

Вывод: после выполнения arr.sort(compareRandom); вы получите один из n! вариантов размещения элементов в массиве, где n - количество элементов массива.

Детальнее про сортировку тут.

7
  • и всё же почему оно работает? Вот пример на С++ ideone.com/EpDw90 тут видно что оно не работает. Насколько я помню операция сравнения должна быть транзитивной и так далее.
    – pavel
    7 апр 2016 в 11:19
  • Интервал [-0,5; 0,49) неверен. Должно быть [-0,5; 0,5). 7 апр 2016 в 11:31
  • @DmitriySimushev, учитывая, что диапазон возвращаемых значений Math.random() находится в интервале от нуля (включая) до единицы (НЕ включая), получаем, что диапазон значений (Math.random() - 0.5) будет равен: от 0 - 0.5= -0.5 (включая) до 0.9(9) - 0.5 = 0.49(9).
    – Nk185
    7 апр 2016 в 12:53
  • @pavel, я не експерт в С++, но разве return rand()&1; возвращает не 0 для любого значения rand() отличного от 1? Попробуйте заменить return rand()&1; на return (rand() > (RAND_MAX / 2)) и все должно заработать. Суть ведь в том, чтобы "компаратор" равновозможно и, в тоже время, случайно сообщал а больше b, или же нет. Только таким образом мы случайно получим один из n! возможных вариантов размещения n-го количества элементов в массиве.
    – Nk185
    7 апр 2016 в 13:26
  • 1
    @Nk185, именно об этом и говорит запись [-0,5; 0,5). Правая граница не включена в диапазон. Записывая диапазон как [-0,5; 0,49) вы теряете один процент значений (если распределение равномерное). Согласитесь -- это не очень-то здорово 7 апр 2016 в 13:47

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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