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

Ваш ответ

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

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