Array.prototype.sort()

Метод sort() (сортувати) примірників Array сортує елементи масиву на місці й повертає посилання на той самий масив, уже відсортований. Усталений порядок сортування — в порядку зростання, заснований на перетворенні елементів на рядки, а потім порівнянні їхніх послідовностей значень кодових одиниць UTF-16.

Складність алгоритму сортування щодо використання часу та місця в пам'яті – ніяк не гарантується і залежить від реалізації.

Щоб відсортувати елементи в масиві, не змінюючи вихідний масив, слід використовувати toSorted().

Спробуйте його в дії

Синтаксис

sort()
sort(compareFn)

Параметри

compareFn Необов'язкове

Функція, що визначає порядок елементів. Вона викликається з наступними аргументами:

a

Перший елемент для порівняння. Ніколи не буває undefined.

b

Другий елемент для порівняння. Ніколи не буває undefined.

Ця функція повинна повертати число, що означає наступне:

• Від'ємне значення вказує, що a має стояти до b.
• Додатне значення вказує, що a має стояти після b.
• Нуль або NaN вказує, що a і b вважаються рівними.

Щоб закарбувати це в пам'яті, запам'ятайте, що (a, b) => a - b сортує числа в порядку зростання.

Коли цей параметр відсутній, то елементи масиву перетворюються на рядки, а потім сортуються відповідно до значення кодової точки Unicode кожного символу.

Повернене значення

Посилання на вихідний масив, уже відсортований. Зауважте, що масив сортується на місці: ніяких додаткових копій не створюється.

Опис

Якщо compareFn передано не було, то всі елементи масиву, котрі не є undefined, сортуються шляхом перетворення їх на рядки та порівняння цих рядків у порядку кодів UTF-16. Наприклад, "банан" йде перед "вишнею". У разі сортування чисел – 9 йде перед 80, але через те, що числа перетворюються на рядки перед сортуванням, "80" йде перед "9" – згідно з послідовністю кодів Unicode. Всі елементи, які є undefined, складаються в кінець масиву.

Метод sort() зберігає порожні комірки. Якщо вихідний масив є розрідженим, то порожні комірки складаються в кінець масиву, завжди після усіх undefined.

Примітка: В UTF-16 символи Unicode після \uFFFF кодуються як сурогатні пари кодів з проміжку \uD800 - \uDFFF. Під час порівняння значення кожного коду такої пари враховується окремо. Таким чином, символ, сформований сурогатною парою \uD855\uDE51, під час сортування опиниться перед символом \uFF3A.

Якщо було передано функцію порівняння compareFn, то всі елементи масиву, котрі не є undefined, сортуються відповідно до поверненого значення функції порівняння (всі елементи, рівні undefined, складаються в кінець масиву без викликання compareFn).

Отже, функція порівняння має наступну форму:

function compareFn(a, b) {
  if (a менше за b за якимось критерієм упорядкування) {
    return -1;
  } else if (a більше b за тим самим критерієм упорядкування) {
    return 1;
  }
  // a має дорівнювати b
  return 0;
}

Більш формально кажучи, очікується, що компаратор для відповідного сортування матиме наступні властивості:

• Чистоту: Компаратор не змінює об'єкти, що порівнюються, чи будь-який зовнішній стан. (Це важливо, адже немає гарантій того, коли і як компаратор буде викликаний, тож будь-який конкретний виклик не повинен породжувати видимих зовні ефектів.)
• Стабільність: Компаратор повертає однаковий результат для кожної пари елементів.
• Рефлексивність: compareFn(a, a) === 0.
• Антисиметричність: compareFn(a, b) === 0 і compareFn(b, a) === 0 повинні або обидвоє бути нулями, або мати протилежні знаки.
• Транзитивність: Якщо і compareFn(a, b), і compareFn(b, c) водночас є або додатними значеннями, або нулями, або від'ємними, то compareFn(a, c) матиме такий самий знак, як і попередні двоє.

Компаратор, що відповідає обмеженням вище, обов'язково в деяких випадках повертатиме 1, 0 і -1, або ж він постійно повертатиме 0. Наприклад, якщо компаратор повертає лише 1 і 0, або ж якщо повертає лише 0 і -1, він не зможе надійно сортувати, бо антисиметричність буде порушена. Компаратор, що завжди повертає 0, призведе до того, що масив узагалі не зміниться, але буде в цьому надійним.

Усталений лексикографічний компаратор відповідає усім вищеописаним обмеженням.

Щоб порівнювати числа, а не рядки, функція порівняння може віднімати b від a. Наступна функція відсортує масив у порядку зростання (якщо він не містить NaN):

function compareNumbers(a, b) {
  return a - b;
}

Метод sort() є узагальненим. Він лишень очікує, що значення this матиме властивість length, а також властивості з цілочисловими ключами.

Приклади

Створення, вивід і сортування масиву

Наступний приклад створює чотири масиви, далі показує вихідний масив, а потім — відсортовані масиви. Числові масиви сортуються спочатку без функції сортування, а потім із нею.

const stringArray = ["Кит синій", "Горбатий кит", "Білуга"];
const numberArray = [40, 1, 5, 200];
const numericStringArray = ["80", "9", "700"];
const mixedNumericArray = ["80", "9", "700", 40, 1, 5, 200];

function compareNumbers(a, b) {
  return a - b;
}

stringArray.join(); // 'Кит синій,Горбатий кит,Білуга'
stringArray.sort(); // ['Білуга', 'Горбатий кит', 'Кит синій']

numberArray.join(); // '40,1,5,200'
numberArray.sort(); // [1, 200, 40, 5]
numberArray.sort(compareNumbers); // [1, 5, 40, 200]

numericStringArray.join(); // '80,9,700'
numericStringArray.sort(); // ['700', '80', '9']
numericStringArray.sort(compareNumbers); // ['9', '80', '700']

mixedNumericArray.join(); // '80,9,700,40,1,5,200'
mixedNumericArray.sort(); // [1, 200, 40, 5, '700', '80', '9']
mixedNumericArray.sort(compareNumbers); // [1, 5, '9', 40, '80', 200, '700']

Сортування масиву об'єктів

Масив об'єктів можна сортувати шляхом порівняння значень однієї з їхніх властивостей.

const items = [
  { name: "Edward", value: 21 },
  { name: "Sharpe", value: 37 },
  { name: "And", value: 45 },
  { name: "The", value: -12 },
  { name: "Magnetic", value: 13 },
  { name: "Zeros", value: 37 },
];

// сортувати за властивістю value
items.sort((a, b) => a.value - b.value);

// сортувати за властивістю name
items.sort((a, b) => {
  const nameA = a.name.toUpperCase(); // ігноруємо малі та великі літери
  const nameB = b.name.toUpperCase(); // ігноруємо малі та великі літери
  if (nameA < nameB) {
    return -1;
  }
  if (nameA > nameB) {
    return 1;
  }

  // значення полів name однакові
  return 0;
});

Сортування не-ASCII символів

Для сортування рядків з не-ASCII символами, наприклад, рядків з діакритичними знаками (e, é, è, a, ä, та ін.) чи рядків з інших мов, не англійської, використовуйте String.prototype.localeCompare(). Ця функція дає змогу порівнювати такі символи так, щоб вони опинилися у вірній послідовності.

const items = ["réservé", "premier", "communiqué", "café", "adieu", "éclair"];
items.sort((a, b) => a.localeCompare(b));

// items містить ['adieu', 'café', 'communiqué', 'éclair', 'premier', 'réservé']

Сортування з map

Функція порівняння compareFn може закликатися декілька разів на один елемент масиву. Залежно від природи compareFn, це може призвести до високих накладних витрат. Чим більше роботи виконує функція compareFn, і чим більше елементів треба відсортувати, тим ефективніше буде застосувати для сортування map(). Ідея полягає в тому, щоб перебрати масив один раз, аби витягнути значення для сортування у тимчасовий масив, потім відсортувати тимчасовий масив, і далі ітерувати тимчасовий масив іще раз, для отримання правильної послідовності.

// масив, який треба відсортувати
const data = ["Григорій", "Анна", "Василь", "Богдан"];

// тимчасовий масив містить об'єкти з позицією елемента в оригінальному масиві і значенням для сортування
const mapped = data.map((v, i) => {
  return { i, value: someSlowOperation(v) };
});

// сортуємо тимчасовий масив, що містить уже обраховані значення
mapped.sort((a, b) => {
  if (a.value > b.value) {
    return 1;
  }
  if (a.value < b.value) {
    return -1;
  }
  return 0;
});

const result = mapped.map((v) => data[v.i]);

Існує бібліотека з відкритим кодом mapsort, котра реалізовує такий підхід.

sort() повертає посилання на той самий масив

Метод sort() повертає посилання на вихідний масив, тож внесення змін до поверненого масиву змінить також вихідний масив.

const numbers = [3, 1, 4, 1, 5];
const sorted = numbers.sort((a, b) => a - b);
// numbers і sorted – рівні [1, 1, 3, 4, 5]
sorted[0] = 10;
console.log(numbers[0]); // 10

Якщо потрібно, аби sort() не змінював вихідний масив, а повертав поверхнево скопійований масив, як інші методи (наприклад, map()), то слід використати метод toSorted(). Інший варіант – перед викликом sort() створити поверхневу копію, використовуючи синтаксис розгортання чи Array.from().

const numbers = [3, 1, 4, 1, 5];
// [...numbers] створює поверхневу копію, тож sort() не міняє вихідного масиву
const sorted = [...numbers].sort((a, b) => a - b);
sorted[0] = 10;
console.log(numbers[0]); // 3

Стабільність сортування

Починаючи з версії 10 (тобто ECMAScript 2019), специфікація постулює, що Array.prototype.sort дає стабільне сортування.

Для прикладу, скажімо, є список студентів з їхніми оцінками. Зауважте, що цей список вже відсортований за іменами в алфавітному порядку:

const students = [
  { name: "Артур", grade: 13 },
  { name: "Олексій", grade: 15 },
  { name: "Рустем", grade: 15 },
  { name: "Самійло", grade: 14 },
];

Після сортування цього масиву за полем grade у порядку зростання маємо:

students.sort((firstItem, secondItem) => firstItem.grade - secondItem.grade);

Змінна з масивом students далі матиме наступне значення:

[
  { name: "Артур", grade: 13 },
  { name: "Самійло", grade: 14 },
  { name: "Олексій", grade: 15 }, // збережено первісне сортування для однакових оцінок (стабільне сортування)
  { name: "Рустем", grade: 15 }, // збережено первісне сортування для однакових оцінок (стабільне сортування)
];

Важливо зауважити, що студенти, які мають однакові оцінки (для прикладу, Олексій та Рустем), залишаться в тому ж порядку, що й перед сортуванням. Це те, що гарантує алгоритм стабільного сортування.

До версії 10 (тобто ECMAScript 2019) стабільність сортування не гарантувалась, тобто могла трапитись наступна ситуація:

[
  { name: "Артур", grade: 13 },
  { name: "Самійло", grade: 14 },
  { name: "Рустем", grade: 15 }, // первісне сортування не збережено
  { name: "Олексій", grade: 15 }, // первісне сортування не збережено
];

Сортування з погано сформованим компаратором

Якщо функція порівняння не задовольняє кожному з правил: чистоти, стабільності, рефлексивності, антисиметричності або транзитивності, як це пояснено в описі, то поведінка програми не є чітко визначеною.

Для прикладу – погляньте на такий код:

const arr = [3, 1, 4, 1, 5, 9];
const compareFn = (a, b) => (a > b ? 1 : 0);
arr.sort(compareFn);

Тут функція compare є погано сформованою, тому що не задовольняє правилу антисиметричності: якщо a > b, вона повертає 1; однак якщо поміняти a й b місцями, вона замість від'ємного значення повертає 0. Таким чином, результівний масив буде різним на різних рушіях. Наприклад, V8 (що використовується Chrome, Node.js тощо) та JavaScriptCore (використовується Safari) не сортуватимуть масив узагалі й повернуть [3, 1, 4, 1, 5, 9], натомість SpiderMonkey (використовується Firefox) поверне масив, відсортований в порядку зростання: [1, 1, 3, 4, 5, 9].

А проте, якщо трохи змінити функцію compareFn, щоб вона повертала або -1, або 0:

const arr = [3, 1, 4, 1, 5, 9];
const compareFn = (a, b) => (a > b ? -1 : 0);
arr.sort(compareFn);

Тоді V8 і JavaScriptCore відсортують масив у порядку спадання: [9, 5, 4, 3, 1, 1], натомість SpiderMonkey поверне його як є: [3, 1, 4, 1, 5, 9].

У зв'язку з цією неузгодженістю реалізацій краще завжди формувати компаратори як слід, виконуючи усі п'ять вимог.

Використання sort() на розріджених масивах

Порожні комірки складаються в кінець масиву.

console.log(["a", "c", , "b"].sort()); // ['a', 'b', 'c', порожньо]
console.log([, undefined, "a", "b"].sort()); // ["a", "b", undefined, порожньо]

Виклик sort() на об'єктах-немасивах

Метод sort() зчитує з this властивість length. Потім він збирає всі наявні цілочислові властивості в діапазоні від 0 до length - 1, сортує їх і записує назад. Якщо в діапазоні є пропущені властивості, то відповідні властивості в кінці послідовності видаляються, як ніби відсутні властивості сортувалися в кінець.

const arrayLike = {
  length: 3,
  unrelated: "foo",
  0: 5,
  2: 4,
};
console.log(Array.prototype.sort.call(arrayLike));
// { '0': 4, '1': 5, length: 3, unrelated: 'foo' }

Специфікації

Сумісність із браузерами

Дивіться також

• Поліфіл для Array.prototype.sort з сучасною поведінкою (включно зі стабільним сортуванням) у core-js
• Посібник Колекції з індексами
• Array
• Array.prototype.reverse()
• Array.prototype.toSorted()
• String.prototype.localeCompare()
• TypedArray.prototype.sort()
• Сортування штук у V8 – переклад на Друкарні (2023) статті з v8.dev (2018)
• Стабільний Array.prototype.sort на v8.dev (2019)
• Стабільність Array.prototype.sort stability від Матіаса Байненса