Всё только о JavaScript

/ Статьи / Массивы в JavaScript

Инверсия массива

Для изменения порядка элементов в массиве на противоположный используется метод reverse. Этот метод изменяет порядок элементов в исходном массиве и возвращает ссылку на самого себя.

var a = [1, 2, 3, 4, 5];
a.reverse();
alert(a);    // 5,4,3,2,1

При этом пропуски в массиве сохраняются.

var a = [];
a[1] = 1;
a[2] = 2;
alert(a + ' : ' + [0 in a, 1 in a, 2 in a]);   // ,1,2 : false,true,true
a.reverse();
alert(a + ' : ' + [0 in a, 1 in a, 2 in a]);   // 2,1, : true,true,false

Сортировка элементов

Метод sort сортирует элементы массива, изменяя порядок элементов в исходном массиве. sort принимает единственным аргументом функцию, сравнивающую элементы массива. Если функция сравнения не задана, то элементы сортируются в лексикографическом порядке.

var a = ['d', 'b', 'a', 'e', 'c'];
a.sort();
alert(a);  // a,b,c,d,e

Даже если отсортировать массив, состоящий только из чисел, они всё равно будут отсортированы как строки, а не как числа.

var a = [4, 2, 10, 5, 30];
a.sort();
alert(a);  // 10,2,30,4,5

Чтобы отсортировать массив чисел, необходимо передать методу sort функцию сравнения двух чисел. Функция, передаваемая методу sort, поочерёдно вызывается для различных пар элементов массива, и должна вернуть отрицательное число, если первый аргумент меньше второго, положительное число, если первый аргумент больше второго, и 0, если они равны. Таким образом код, сортирующий массив чисел будет выглядеть следующим образом.

var a = [4, 2, 10, 5, 30];
a.sort(function(a, b) { return a - b; });
alert(a);  // 2,4,5,10,30

С помощью callback-функции массивы можно сортировать по любому критерию. Например, отсортировать массив объектов по значению какого-либо свойства, или даже нескольких свойств.

var a = [
    {x: 4, y: 2},
    {x: 3, y: 5},
    {x: 1, y: 5},
    {x: 3, y: 2},
    {x: 4, y: 1}
];
a.sort(function(a, b) {
    // Сортируем по полю x, если оно одинаковое, то по полю y
    return (a.x - b.x) || (a.y - b.y);
});
alert(a.map(function(a) { return 'x = ' + a.x + ', y = ' + a.y }).join('\n'));
// x = 1, y = 5
// x = 3, y = 2
// x = 3, y = 5
// x = 4, y = 1
// x = 4, y = 2

Callback-функция обязательно должна возвращать число, в противном случае Internet Explorer выбросит ошибку, а остальные браузеры просто не отсортируют массив.

Пропуски в массиве, равно как и элементы массива, равные undefined при сортировке не учитываются вовсе. Данные элементы просто оказываются в конце массива.

var a = [];
a[1] = 1;
a[3] = undefined;
alert(a);       // ,1,,
a.sort(function(a, b) {
    alert([a, b]);
    // Функция не будет вызвана ни разу, в массиве только один значащий элемент
    return 0;
});
alert(a);       // 1,,,

Чтобы отсортировать массив в обратном лексикографическом порядке, достаточно после вызова sort без аргументов вызвать метод reverse. Для остальных типов сортировки придётся видоизменять callback-функцию.

var a = [4, 2, 10, 5, 30];
a.sort(function(a, b) { return b - a; });
alert(a);  // 30,10,5,4,2

Перемешивание элементов

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

Array.prototype.shuffle = function() {
    return this.sort(function() {
        return 0.5 - Math.random();
    });
};

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

Array.prototype.shuffle = function() {
    return this.sort(function() {
        return 0.5 - Math.random();
    });
};

var N = 10000, a = [], i;
for (i = 0; i < 10; i++) {
    a[i] = 0;
}
for (i = 0; i < N; i++) {
    a[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9].shuffle()[0]]++;
}
alert(a);

В Firefox результат теста будет сильно похож на 1860,1841,1223,704,633,613,409,255,1226,1236, т.е. чаще всего под нулевым индексом перемешанного массива будет нулевой же индекс исходного массива, а реже всего — седьмой.

В IE и Safari результаты совсем другие, но не лучше: 471,890,855,1362,1090,1088,844,1252,1084,1064, тут нулевой индекс исходного массива будет гораздо реже оказываться под нулевым индексом в отсортированном массиве.

В Opera разброс гораздо больше, но упорядоченнее: 2810,2861,1391,233,206,914,946,459,86,94. В Chrome похожая ситуация, но ещё хуже: 2868,2930,1962,1076,574,291,164,82,33,20.

Вывод — использовать такое перемешивание очень неэффективно. Гораздо лучше перебрать все элементы и поменять их на произвольный с большим или равным индексом. Только перебирать элементы будем с конца массива, чтобы взятие случайного числа было проще.

Array.prototype.shuffle = function() {
    for (var i = this.length - 1; i > 0; i--) {
        var num = Math.floor(Math.random() * (i + 1));
        var d = this[num];
        this[num] = this[i];
        this[i] = d;
    }
    return this;
}

Предыдущий тест для такого способа будет давать для каждого индекса 1000 плюс-минус 40 повторений, что является, несомненно, более хорошим результатом. Более того, данный способ быстрее предыдущего в разных браузерах на 40-70%.