Sorting array values in javascript

Несколько полезных кейсов при работе с массивами в JavaScript

Очень часто на тостере вижу вопросы вида «Как отсортировать массив в JavaScript по определенному правилу?», «Как сделать с массивом в JavaScript <действие>?» и т.д.

Под катом собраны некоторые манипуляции над массивами.

Преобразование массиво-подобного объекта в массив

В es2015 была добавлена замечательная функция Array.from, которая умеет преобразовывать в массив все, что похоже на массив. Принцип ее работы следующий:

1. Если в передаваемом объекте в свойстве [Symbol.iterator] есть функция, она будет использована как генератор для наполнения массива
2. Если в передаваемом объекте есть свойство length, то массив будет составлен из целочисленных индексов объекта от 0 до (object.length — 1)
3. В других случаях она вернет пустой массив

Из стандартных объектов массиво-подобными считаются строки (разбиваются посимвольно), генераторы, объекты класса Set, arguments и некоторые другие

Сумма и произведение массива

var arr = [1, 2, 3, 4, 5]; var sum = arr.reduce((a, b) => a + b, 0); // 15 var prod = arr.reduce((a, b) => a * b, 1); // 120 

Но с суммой нужно быть аккуратнее, если в массиве встретится не числовое значение, то оно будет преобразовано в строку, и начиная с него пойдет конкатенация строк, чтобы этого избежать можно использовать более безопасный вариант:

var sum = arr.reduce((a, b) => a + (+b || 0), 0); 

Поиск в массиве и фильтрация массива

Многие знают о таком замечательном методе как indexOf, который ищет в массиве переданное в первом аргументе значение по точному соответствию (value === element) и возвращает индекс первого совпадения или -1 если ничего не найдено. Так же вторым аргументом можно передать индекс, с которого нужно начать поиск.

Есть похожий на него метод lastIndexOf, работающий аналогично, только поиск производится с конца массива. Но бывают ситуации, когда поиск по точному соответствию не подходит, для этих случаев существуют методы find и findIndex работают они похожим образом, вызывая для каждого элемента функцию, переданную в первом аргументе с параметрами (element, index, array). Поиск осуществляется до тех пор, пока функция не вернет true. find возвращает сам найденный элемент или undefined если ничего не найдено, а findIndex его индекс или -1 соответственно.

Пример, найдем в массиве первый элемент, который больше 5:

var arr = [1, 4, 2, 8, 2, 9, 7]; var elem = arr.find(e => e > 5); // 8 var index = arr.findIndex(e => e > 5); // 3 

Еще одна частая задача, это фильтрация массива. Для этих целей существует метод filter, который возвращает новый массив, состоящий только из тех элементов, для которых функция переданная в первом аргументе вернула true:

var arr = [1, 4, 2, 8, 2, 9, 7]; var filtredArr = arr.filter(e => e > 5); // [8, 9, 7] 

Так же иногда бывает нужно просто проверить элементы массива на соответствие некоторому условию, для этого существуют методы some и every, как и предыдущие методы они работают с функцией переданной в первом аргументе:

some возвращает true, если хотя бы для одного аргумента функция вернула true, и false в противном случае
every возвращает false, если хотя бы для одного аргумента функция вернула false, и true в противном случае

Обе останавливают поиск, когда искомое значение найдено. Это можно использовать несколько нестандартно, как известно метод forEach перебирает все элементы массива, но его работу невозможно прервать, однако это становится возможным благодаря методу some:

var arr = [1, 4, 2, 8, 2, 9, 7]; arr.some(function(element, index) < console.log(index + ': ' + element); if(element === 8) < return true; //прерываем выполнение >>); /* В консоли увидим: 0: 1 1: 4 2: 2 3: 8 */ 

Сортировка массивов

Для сортировки массива используется метод sort. По умолчанию все элементы сортируются как строки по возрастанию кодов utf-16. Стандартное поведение можно изменить передав первым аргументом функцию-компаратор. Компаратор — это такая функция, которая получает на вход два аргумента (a, b) и должна вернуть: -1, если a идет раньше чем b; 1, если a идет позже чем b; 0, если порядок не важен, то есть аргументы равны. Метод sort довольно лоялен к компаратору и принимает на выходе любые значения меньше 0 как -1, а значения больше 0 как 1.

Важно! Метод sort, хотя и возвращает результат, все операции проводит над исходным массивом. Если необходимо оставить исходный массив без изменений, можно воспользоваться следующим приемом:

var sortedArr = arr.slice().sort(); 

Так как метод slice без аргументов возвращает клон массива, метод sort будет работать с этим клоном и в результате его вернет.

Простая сортировка, сравнение элементов как числа

arr.sort((a, b) => a - b); //по возрастанию arr.sort((a, b) => b - a); //по убыванию 

Типобезопасная сортировка

arr.sort((a, b) => (a < b && -1) || (a >b && 1) || 0); //по возрастанию arr.sort((a, b) => (a < b && 1) || (a >b && -1) || 0); //по убыванию 

Сортировка массива объектов по их свойствам

Более частая ситуация возникает, когда нужно отсортировать массив однотипных объектов по их свойству, а то и нескольким свойствам сразу, для этого удобно иметь функцию, которая создавала бы нам компаратор на любой случай жизни:

function compare(field, order) < var len = arguments.length; if(len === 0) < return (a, b) =>(a < b && -1) || (a >b && 1) || 0; > if(len === 1) < switch(typeof field) < case 'number': return field < 0 ? ((a, b) =>(a < b && 1) || (a >b && -1) || 0) : ((a, b) => (a < b && -1) || (a >b && 1) || 0); case 'string': return (a, b) => (a[field] < b[field] && -1) || (a[field] >b[field] && 1) || 0; > > if(len === 2 && typeof order === 'number') < return order < 0 ? ((a, b) =>(a[field] < b[field] && 1) || (a[field] >b[field] && -1) || 0) : ((a, b) => (a[field] < b[field] && -1) || (a[field] >b[field] && 1) || 0); > var fields, orders; if(typeof field === 'object') < fields = Object.getOwnPropertyNames(field); orders = fields.map(key =>fieldSorting array values in javascript); len = fields.length; > else < fields = new Array(len); orders = new Array(len); for(let i = len; i--;) < fields[i] = arguments[i]; orders[i] = 1; >> return (a, b) => < for(let i = 0; i < len; i++) < if(a[fields[i]] < b[fields[i]]) return orders[i]; if(a[fields[i]] >b[fields[i]]) return -orders[i]; > return 0; >; > //Использование arr.sort(compare()); //Обычная типобезопасная сортировка по возрастанию arr.sort(compare(-1)); //Обычная типобезопасная сортировка по убыванию arr.sort(compare('field')); //Сортировка по свойству field по возрастанию arr.sort(compare('field', -1)); //Сортировка по свойству field по убыванию /* Сортировка сначала по полю field1 при совпадении по полю field2, а если и оно совпало, то по полю field3 все по возрастанию */ arr.sort(compare('field1', 'field2', 'field3')); /* Сортировка сначала по полю field1 по возрастанию при совпадении по полю field2 по убыванию */ arr.sort(compare(< field1 : 1, field2 : -1 >)); 

Сортировка подсчетом

Хотя метод sort работает достаточно быстро, на очень больших массивах его скорости может оказаться недостаточно, благо есть метод сортировки который показывает большую производительность при соблюдении 2х условий, а именно — массив достаточно большой (больше 100.000 элементов) и в массиве много повторяющихся значений. Называется он сортировкой подсчетом. Я представлю пример его реализации для сортировки по возрастанию массива из числовых элементов:

function sortCounts(arr) < var counts = arr.reduce((result, value) => < if(typeof result[value] === 'undefined') < result[value] = 0; >return ++result[value], result; >, <>); var values = Object.getOwnPropertyNames(counts).sort((a, b) => a - b); var start = 0; for(let value of values) < let end = counts[value] + start; arr.fill(+value, start, end); start = end; >> 

Источник

JavaScript Sorting Arrays

The reverse() method reverses the elements in an array.

You can use it to sort an array in descending order:

Example

Numeric Sort

By default, the sort() function sorts values as strings.

This works well for strings («Apple» comes before «Banana»).

However, if numbers are sorted as strings, «25» is bigger than «100», because «2» is bigger than «1».

Because of this, the sort() method will produce incorrect result when sorting numbers.

You can fix this by providing a compare function:

Example

Use the same trick to sort an array descending:

Example

The Compare Function

The purpose of the compare function is to define an alternative sort order.

The compare function should return a negative, zero, or positive value, depending on the arguments:

When the sort() function compares two values, it sends the values to the compare function, and sorts the values according to the returned (negative, zero, positive) value.

If the result is negative, a is sorted before b .

If the result is positive, b is sorted before a .

If the result is 0, no changes are done with the sort order of the two values.

The compare function compares all the values in the array, two values at a time (a, b) .

When comparing 40 and 100, the sort() method calls the compare function(40, 100).

The function calculates 40 — 100 (a — b) , and since the result is negative (-60), the sort function will sort 40 as a value lower than 100.

You can use this code snippet to experiment with numerically and alphabetically sorting:

const points = [40, 100, 1, 5, 25, 10];
document.getElementById(«demo»).innerHTML = points;

function myFunction1() points.sort();
document.getElementById(«demo»).innerHTML = points;
>

function myFunction2() points.sort(function(a, b));
document.getElementById(«demo»).innerHTML = points;
>

Sorting an Array in Random Order

Example

The Fisher Yates Method

The above example, array.sort(), is not accurate. It will favor some numbers over the others.

The most popular correct method, is called the Fisher Yates shuffle, and was introduced in data science as early as 1938!

In JavaScript the method can be translated to this:

Example

const points = [40, 100, 1, 5, 25, 10];

for (let i = points.length -1; i > 0; i—) let j = Math.floor(Math.random() * (i+1));
let k = points[i];
points[i] = points[j];
points[j] = k;
>

Find the Highest (or Lowest) Array Value

There are no built-in functions for finding the max or min value in an array.

However, after you have sorted an array, you can use the index to obtain the highest and lowest values.

Example

const points = [40, 100, 1, 5, 25, 10];
points.sort(function(a, b));
// now points[0] contains the lowest value
// and points[points.length-1] contains the highest value

Example

const points = [40, 100, 1, 5, 25, 10];
points.sort(function(a, b));
// now points[0] contains the highest value
// and points[points.length-1] contains the lowest value

Sorting a whole array is a very inefficient method if you only want to find the highest (or lowest) value.

Using Math.max() on an Array

You can use Math.max.apply to find the highest number in an array:

Example

Math.max.apply(null, [1, 2, 3]) is equivalent to Math.max(1, 2, 3) .

Using Math.min() on an Array

You can use Math.min.apply to find the lowest number in an array:

Example

Math.min.apply(null, [1, 2, 3]) is equivalent to Math.min(1, 2, 3) .

My Min / Max JavaScript Methods

The fastest solution is to use a «home made» method.

This function loops through an array comparing each value with the highest value found:

Example (Find Max)

function myArrayMax(arr) <
let len = arr.length;
let max = -Infinity;
while (len—) <
if (arr[len] > max) <
max = arr[len];
>
>
return max;
>

This function loops through an array comparing each value with the lowest value found:

Example (Find Min)

function myArrayMin(arr) <
let len = arr.length;
let min = Infinity;
while (len—) <
if (arr[len] < min) <
min = arr[len];
>
>
return min;
>

Sorting Object Arrays

JavaScript arrays often contain objects:

Example

Even if objects have properties of different data types, the sort() method can be used to sort the array.

The solution is to write a compare function to compare the property values:

Example

Comparing string properties is a little more complex:

Example

cars.sort(function(a, b) <
let x = a.type.toLowerCase();
let y = b.type.toLowerCase();
if (x < y)
if (x > y)
return 0;
>);

Stable Array sort()

ES2019 revised the Array sort() method.

Before 2019, the specification allowed unstable sorting algorithms such as QuickSort.

After ES2019, browsers must use a stable sorting algorithm:

When sorting elements on a value, the elements must keep their relative position to other elements with the same value.

Example

In the example above, when sorting on price, the result is not allowed to come out with the names in an other relative position like this:

Complete Array Reference

For a complete Array reference, go to our:

The reference contains descriptions and examples of all Array properties and methods.

Источник