Задача — разобраться как работает сортировка в JavaScript, насколько она производительна и что с её помощью можно делать.
Метод sort
В JavaScript можно сортировать массивы с помощью метода sort. В качестве единственного необязательного аргумента метод принимает функцию, определяющую правила сортировки. Если sort вызвали без аргументов, то сортировка осуществляется по возрастанию значений элементов. Пример:
var arr = [0, true, 'Вася', 'Петя', 56, NaN, false, 13, 'Коля'];
// Сортируем
arr.sort();
// Вернет [0,13,56,NaN,false,true,Вася,Коля,Петя]
Сортируется массив, в контексте которого вызван метод, так что если вы желаете сохранить исходное состояние — сделайте копию и сортируйте её.
Функции сортировки
Вы можете настраивать сортировку, передавая методу sort специальную функцию. В качестве аргументов функция принимает два значения массива, которые передаст метод sort. Вернуть функция может следующие значения (спасибо за уточнение пользователю alik):
- положительное (1,2,10), если условие сортировки истинно;
- отрицательное (-0.1, -3, -20), если условие сортировки ложно;
- 0, если сравниваемые значения равны.
Пример:
// Функции сортировки
function sIncrease(i, ii) { // По возрастанию
if (i > ii)
return 1;
else if (i < ii)
return -1;
else
return 0;
}
function sDecrease(i, ii) { // По убыванию
if (i > ii)
return -1;
else if (i < ii)
return 1;
else
return 0;
}
function sRand() { // Случайная
return Math.random() > 0.5 ? 1 : -1;
}
arr.sort(sIncrease); // Вернет [1,2,3,4,5,6,7,8,9,10]
arr.sort(sDecrease); // Вернет [10,9,8,7,6,5,4,3,2,1]
arr.sort(sRand); // Вернет случайно отсортированный массив, например [1,10,3,4,8,6,9,2,7,5]
Производительность
На первый взгляд может показаться, что сортировка в JavaScript непроизводительна, и в web-приложениях лучше сортировать данные на server-side. Небольшой эксперимент это опровергает. Будьте осторожны, в циклах на 100.000 элементов браузер может зависнуть!
Сортируем массивы c целочисленными значениями различной длины:
можете зависнуть
Автор, в ходе своих экспериментов на своем PC (Vista, Pentium Dual 2.2Ггц, 2Гб RAM) получил следующие результаты:
| 1000 | 10.000 | 100.000 | |
|---|---|---|---|
| IE 7 | 20-50 ms | 200-650 ms | завис |
| FF 3 | 1-2 ms | 12-30 ms | 150-400 ms |
| Safari 3 | 2-30 ms * | 30-400 ms * | 350-5000 ms * |
| Opera 9.5 | 2-5 ms | 40-75 ms | 500-1000 ms |
| Chrome 1.0 | 1-2 ms | 10-30 ms | 100-300ms |
* В Safari случайная сортировка занимала ровно на порядок больше времени, чем сортировка по возрастанию/убыванию.
За исключением Internet Explorer, который не смог переварить массив на 100.000 элементов, сортировка показала себя вполне производительной операцией.
Многомерный массив
При необходимости можно усложнить функции сортировки. Например, чтобы сортировать многомерные массивы (массивы массивов), или массивы объектов, или любой другой массив с нетривиальными значениями. Пример:
['Nikolay', 34],
['Andrey', 23],
['Stanislav', 20]
];
// Функции сортировки
function sName(i, ii) { // По имени (возрастание)
if (i[0] > ii[0])
return 1;
else if (i[0] < ii[0])
return -1;
else
return 0;
}
function sAge(i, ii) { // По возрасту (возрастание)
if (i[1] > ii[1])
return 1;
else if (i[1] < ii[1])
return -1;
else
return 0;
}
multi.sort(sName); // Вернет [[Andrey,23],[Nikolay,34],[Stanislav,20]]
multi.sort(sAge); // Вернет [[Stanislav,20],[Andrey,23],[Nikolay,34]]
Отдельная страница со всеми примерами.
Итого мы
- Разобрали как работает сортировка в JavaScript.
- Научились писать функции сортировки.
- Осознали что сортировка достаточно производительна, чтобы использовать её в своих приложениях на стороне клиента, снизив нагрузку на сервер.
Если вам есть что спросить или добавить — прошу в комменты.
Насчет алгоритма ничего конкретного сказать не могу, необходимо читать документацию.
Вполне возможно что различные производители браузеров используют разные алгоритмы, на это косвенно указывает увеличенное на порядок время случайной сортировки в Safari.
Более подробно о сортировке Хоара в Википедии:
http://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0
Именно так, результат и получается непредсказуемым, как и требовалось. Именно за счёт этого, кстати, происходит ощутимый рост времени выполнения сортировки. Транзитивность, как видно, не является требованием функции сравнения для сортировки, хотя, разумеется, необходима для непротиворечивой модели (и получения реального результата).
1. проверяет равномерность распределения каждого элемента
2. отсутствие корреляции в расположении элементов (расстояние между соседними элементами должно стать случайным после сортировки).
И так, чтобы можно было проверить в разных браузерах.
По вашей ссылке в Википедии есть реализация алгоритма на JavaScript. Такой вызов qsort приводит к бесконечной рекурсии:
В Chrome, кстати, нативная сортировка реализована на JavaScript (как и некоторые другие функции), поэтому код можно подсмотреть, вставив в адресную строку javascript: alert([].sort.toString()); void(0);
Про лексикографическую сортировку знаю, получим [1,10,2,20]. Пожалуй стоит упомянуть в статье.