How To Shuffle an Array in JavaScript
Working with code it is inevitable that you will need to work with arrays. And as programmers we do all kinds of things to array’s. We split them, join them, iterate over them, etc… .
It is very possible that you find yourself in a situation where you need to shuffle an array, like a deck of cards. I was once confronted with that situation one fateful day.
I was working on my first small project in JavaScript that I assigned to myself as I was self teaching. I thought, “Cool, no problem I’ll just use the shuffle method.” Without looking into it at all I tried this (spoiler: it didn’t work):
Once I saw that didn’t work I thought, “Ok Javascript must give their shuffle method some weird name,” so I started googling for it and looking in the documentation, and that’s when everything I thought I knew about programming came crashing down around me (maybe that’s a tad dramatic).
Javascript had no shuffle method.
How could this be? I was just coming from learning Ruby and Python, and they both had built in shuffle methods! How could a language as popular and powerful as Javascript not had something so basic built into it?
Once I gathered myself, I consulted with the most popular StackOverflow answer, which pointed me to something called the Fisher-Yates Shuffle.
The Fisher-Yates Shuffle is an algorithm used to shuffle a sequence. It is a simple yet powerful tool that when given any sequence (in this case an array), will return a random ordering of the same sequence.
What the algorithm does simply is, it picks a random element from your array and swaps that element with the last untouched element in the array.
In it’s Javascript implementation, the algorithm looks like this:
Breaking it down line by line:
It starts with a for loop with an iterator value that is less than the length of the by 1, and will count down from that number to 0.
This will pick a random index between 0 and the current value of i.
Math.random() will generate a random number between 0 & 1, and then we add (i + 1) to make it between our desired range of 0 and our current value of i. Finally Math.floor() will round it down to a whole number instead of a decimal.
The final piece of the puzzle is:
This line will swap whatever element is at our currently randomized index of j, with the index at the value of i.
An Example
Here we can see an example where we will console.log all iterations of the function, given an array from 0–6. Here are the results:
As we can see in the second column, our value of i starts out as one less than the length of the array, (length of array is 6, so i starts out as 5) and it counts down until 0. We also see that j, is always a random number between 0 and the current value of i.
In the first iteration, j is selected to be 1. So we swap the value at array[1], which in this case is 2, with the value at array[5], which is 6. We can see that in our first logging of the new array that the 2 and the 6 are indeed switched.
In the next iteration, j is selected to be 3, and i has decreased by one to a value of 4. So we move the value at array[3] which is 4, with the value at array[4] which is 5, and we can indeed see in the next iteration that 4 and 5 have switched places.
This is a quick way to get a good randomized shuffle of a JavaScript array.
How to shuffle an array in JavaScript
In this article we’ll take a look at a couple of ways to shuffle an array in JavaScript.
Custom sort
The first and simplest way to shuffle an array in JavaScript is to provide a custom function to a .sort() .
Exit fullscreen mode
As the function we pass to .sort() is looking for either a positive or negative number to either move the item ‘up’ or ‘down’ in the array, each item has a chance of being moved in either direction giving us a shuffled array of items.
This works for a rough-and-ready approach but might not give you a truly random shuffle.
If you do a bit of research in to the above technique (check out this article), you’ll see that using the custom sort function is flawed (although I can’t give you a definitive answer as to why that is!).
If you need to shuffle an array and have a truly random distribution of items, you need to implement the Fisher-Yates algorithm.
The Fisher-Yates algorith
Luckily for us, it’s not too complicated:
Exit fullscreen mode
As you can see it’s just a case of looping through the array (from the end to the start) and picking a random item from the array and swapping it with the item in the current iteration.
You can use the above function to shuffle an array in JavaScript and get a random result each time.
Пятничный JS: случайное перемешивание
Перед моими студентами регулярно встаёт задача случайного перемешивания массива. За её решением они, как правило, лезут в гугл. И гугл им подсказывает следующее:
Здесь и далее будем называть этот метод случайной сортировкой. Сегодня я решил написать о том, какие преимущества и недостатки есть у такого подхода.
Как это вообще работает?
Метод sort у джаваскриптовых массивов в качестве аргумента принимает функцию-компаратор. Эта функция должна принимать два элемента массива и возвращать число. Если число положительное, алгоритм сортировки считает, что первый элемент больше; если отрицательное — значит, первый элемент меньше; если же компаратор возвращает нуль, то в рамках данной сортировки элементы как бы равны. Если под видом компаратора передать функцию, которая будет возвращать положительное или отрицательное число случайным образом, то массив окажется отсортирован в «случайном» порядке.
Преимущества
Такое перемешивание очень быстро пишется. Я честно пытался придумать какое-нибудь ещё преимущество, но мне не удалось.
Недостатки
Этот параграф будет несколько длиннее, потому я разобью его на подпараграфы.
Несоответствие спецификации
В переводе с технического английского на русский разговорный это означает, что если компаратор не отвечает некоторым очевидным требованиям (ниже в спецификации разъясняется, что, в частности, он должен для одних и тех же аргументов всегда возвращать одно и то же значение), то порядок сортировки зависит от реализации конкретного джаваскриптового движка. То есть, фактически, не определён. Разработчик браузера имеет, например, полное право сделать так, что при обнаружении того, что компаратор «ненастоящий», возвращается исходный массив без каких-либо перестановок. И это будет полностью соответствовать спецификации. То, что во всех существующих браузерах приведённый метод даёт нечто похожее на случайное перемешивание — не более чем счастливое совпадение.
Временна́я сложность
Корректный алгоритм перемешивания (см. ниже) имеет временную сложность O(n). Попросту говоря, это означает примерно следующее: если длина массива увеличится в 10 раз, то продолжительность его перемешивания также увеличится в 10 раз.
Самые быстрые алгоритмы сортировки имеют временную сложность O(n*log(n)). Это означает, что при увеличении длины массива в 10 раз продолжительность его перемешивания увеличится более чем в 10 раз.
В сумме эти два факта значат вот что: для достаточно большого массива перемешивание случайной сортировкой будет работать медленнее, чем «правильное» перемешивание (даже если для маленьких массивов это было не так). И чем больше массив, тем больше разница во времени выполнения.
Почему я сделал оговорку в скобках? Потому что Array#sort выполняется нативным кодом, и за счёт этого на небольших массивах потенциально может оказаться быстрее. У него может оказаться меньше константный множитель, сказал бы человек, знакомый с О-нотацией.
Ненастоящая случайность
Те, кто хотя бы поверхностно знаком с теорией вероятностей, знают, что случайность случайности рознь. Монетка может выпасть орлом или решкой, кубик может выпасть шестёркой или не шестёркой. И там, и там имеют место случайные события, однако в первом случае события равновероятны, а во втором нет.
Перемешивание массива называется истинно случайным, если все возможные перестановки его элементов имеют одинаковую вероятность. Именно этим свойством случайная сортировка не обладает, и я покажу это на практике.
Я набросал следующую страничку. На ней находятся две диаграммы, одна соответствует случайному перемешиванию, вторая — случайной сортировке. Впрочем, вы сейчас видите не диаграммы, а квадратики, разбитые на клеточки различных оттенков серого. Чтобы они стали диаграммами, нужна легенда — объяснение, что эти клеточки и их цвета означают. Всё очень просто. Мы несколько раз (в данном случае несколько = 10000) берём массив чисел от 0 до n (в данном случае n = 32) и случайно перемешиваем тем или иным алгоритмом. Затем мы вычисляем частоты, с которыми то или иное число оказывается на том или ином месте. Соответственно, цвет клетки в строке номер i и столбце номер j показывает, насколько часто число i оказывается на месте j. Чёрный цвет означает, что оно там не оказывается никогда, белый — что оно там оказывается вдвое или более чаще, чем положено. Если число попадает на указанное место с теоретически предсказанной частотой 1/n, клетка будет иметь цвет hsl(0, 0%, 50%) — оттенок серого, расположенный в точности посередине между чёрным и белым.
Если вы используете свежую версию браузера Chrome, вы видите, что в квадрате справа много белых или почти белых клеток, расположенных по определённой закономерности. Это означает, что при случайной сортировке определённые элементы имеют тенденцию оказываться в определённых местах. Плохо ли это? Зависит от того, для чего вы используете перемешивание. Если для каких-то косметических эффектов, то, возможно, ничего страшного. Если вам важно, чтобы пользователь не мог предсказать, какой элемент окажется на каком месте, или если закономерности в перемешивании каким-то образом заметны визуально — то плохо. И упаси вас Гермес использовать такое перемешивание для чего-то, связанного с криптографией.
Что удивительно, если вы используете Firefox, то для вас оба квадрата примерно одинаково серые. Это происходит оттого, что в разных браузерах используются различные алгоритмы сортировки (если интересно, вот моя статья на эту тему). В таком случае, если хотите удивиться ещё раз, допишите в адресной строке ?size=8 (вот готовая ссылка для ленивых). Firefox по-разному сортирует большие и маленькие массивы, сюрприз!
Upd: товарищ mk2 заметил, что равномерно-серым квадрат в Firefox будет только при размере, равном степени двойки. Нужно больше таких внимательных товарищей, товарищи!
Upd2: товарищи Stalker_RED и yaZva не поленились (в отличие от меня) сделать скрины в различных браузерах.
Напоследок добавлю, что вот эти мои диаграммы с пятьюдесятью оттенками серого — не критерий, а признак. Из того, что квадрат получился не серый, следует, что сортировка не равномерна, однако неверно обратное. Контрпример — циклический сдвиг на случайную величину. Частоты попадания элементов на места будут совершенно одинаковы, однако ни о какой истинной случайности перемешивания, разумеется, не может быть и речи.
Upd3: в этой ветке обсуждается, почему случайная сортировка не даёт равномерную случайность в Firefox (причём даже в том случае, если по диаграмме кажется, что даёт).
Как правильно?
Истинные джедаи используют одну из вариаций алгоритма Фишера-Йетса. Для своей демки я реализовал его так:
Суть алгоритма, если перевести с JS на русский, следующая: берём последний элемент и меняем его местами со случайно выбранным элементом не правее его (в том числе, возможно, и с ним самим). Затем повторяем ту же операцию для предпоследнего элемента, потом для предпредпоследнего и так далее. Вуаля! (этим словом с JS на русский переводится «return arr;»).
Настало время безумия
Кто-то из читателей ждал этого целую статью, остальные, в принципе, могут этот параграф не дочитывать. Я задался вопросом: можно ли написать такую функцию compare, что arr.sort(compare) даст истинно случайную перестановку? Ответ: можно, но с определёнными оговорками. Первая — функцию надо перед каждой сортировкой создавать заново. Вторая — в массиве не должно быть одинаковых элементов. Итак, узрите:
Это работает следующим образом: при создании компаратор через замыкание получает доступ к массиву cache. Каждый раз, когда ему передаются аргументы, он кладёт их в cache на случайные места (если их там ещё нет), а затем считает, что тот элемент, который в cache стоит правее, будет больше. То есть по сути в массиве cache постепенно строится тот случайный порядок, в котором элементы должны стоять, а метод sort постепенно приводит исходный массив в соответствии с этим порядком. Если же в нём окажутся равные элементы (равные с точки зрения оператора ===, если мы сортируем объекты — то всё хорошо, даже если у них одинаковое содержание.
На этом всё. Спасибо за чтение, надеюсь, вам было познавательно, и особенно надеюсь, что я убедил вас не использовать случайную сортировку почти никогда. Приятного грядущего вечера.
How to randomize (shuffle) a JavaScript array?
The de-facto unbiased shuffle algorithm is the Fisher-Yates (aka Knuth) Shuffle.
You can see a great visualization here (and the original post linked to this)
Here’s a JavaScript implementation of the Durstenfeld shuffle, an optimized version of Fisher-Yates:
It picks a random element for each original array element, and excludes it from the next draw, like picking randomly from a deck of cards.
This clever exclusion swaps the picked element with the current one, then picks the next random element from the remainder, looping backwards for optimal efficiency, ensuring the random pick is simplified (it can always start at 0), and thereby skipping the final element.
Algorithm runtime is O(n) . Note that the shuffle is done in-place so if you don’t want to modify the original array, first make a copy of it with .slice(0) .
EDIT: Updating to ES6 / ECMAScript 2015
The new ES6 allows us to assign two variables at once. This is especially handy when we want to swap the values of two variables, as we can do it in one line of code. Here is a shorter form of the same function, using this feature.