Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Що таке «ключ» при сортуванні?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

## Коротка відповідь

**Ключ при сортуванні** - це значення (або набір значень), що видобувається з елемента і за яким алгоритм порівнює елементи та визначає їхній порядок. Ключем може бути поле об'єкта, обчислюваний вираз або кортеж із кількох полів.

## Детальний розбір

Ключ сортування (sort key) - це «проєкція» елемента на порівнюване значення. Замість прямого порівняння об'єктів ми порівнюємо їхні ключі. Це спрощує логіку, пришвидшує сортування при дорогих обчисленнях і робить поведінку передбачуваною.

- Простий ключ: одне поле або одне обчислене значення (наприклад, user.age, рядок у нижньому регістрі, timestamp дати).
- Складений ключ: набір полів з лексикографічним порівнянням (наприклад, (lastName, firstName, id)).
- Обчислюваний ключ: результат функції (наприклад, довжина рядка, нормалізована форма, розпарсена дата, натуральний порядок з урахуванням чисел).
- Правила для null/undefined/NaN: явно задавайте, куди їх розміщувати (на початок/у кінець).

## Ключ проти компаратора

Є два підходи: надати компаратор (функцію, що повертає -1/0/1) або надати функцію-видобувач ключа (key selector). Python прямо підтримує параметр key=, а в JavaScript зазвичай пишуть компаратор, але зручно будувати компаратор із key-функції. Компаратор порівнює елементи сам, key-функція лише повертає значення, за яким піде порівняння.

## Видобування ключа (key selector) і комбінування ключів

- Один ключ: перетворюємо об'єкт на порівнюване значення і сортуємо за ним.
- Кілька ключів: з'єднуємо кілька компараторів у ланцюжок; якщо за першим ключем рівність - переходимо до наступного.
- Decorate-Sort-Undecorate (перетворення Шварца): заздалегідь обчислюємо дорогі ключі, сортуємо за ними, потім «розпаковуємо» вихідні елементи.

## Приклади (JavaScript)

```
// Універсальні помічники для сортування за ключами
function compareBy(keyFn, { order = 'asc', nulls = 'last', collator } = {}) {
  return (a, b) => {
    let ka = keyFn(a);
    let kb = keyFn(b);

const isNilA = ka === null || ka === undefined;
    const isNilB = kb === null || kb === undefined;
    if (isNilA || isNilB) {
      if (isNilA && isNilB) return 0;
      return isNilA ? (nulls === 'first' ? -1 : 1) : (nulls === 'first' ? 1 : -1);
    }

const isNaNA = typeof ka === 'number' && Number.isNaN(ka);
    const isNaNB = typeof kb === 'number' && Number.isNaN(kb);
    if (isNaNA || isNaNB) {
      if (isNaNA && isNaNB) return 0;
      return isNaNA ? 1 : -1; // Поміщаємо NaN у кінець
    }

if (collator && typeof ka === 'string' && typeof kb === 'string') {
      const r = collator.compare(ka, kb);
      return order === 'asc' ? r : -r;
    }

if (ka < kb) return order === 'asc' ? -1 : 1;
    if (ka > kb) return order === 'asc' ? 1 : -1;
    return 0;
  };
}

function compareByMany(...comparators) {
  return (a, b) => {
    for (const cmp of comparators) {
      const r = cmp(a, b);
      if (r !== 0) return r;
    }
    return 0;
  };
}

// Дані
const users = [
  { id: 3, firstName: 'Oleh', lastName: 'green', age: 19 },
  { id: 1, firstName: 'Maria', lastName: 'Adams', age: 25 },
  { id: 2, firstName: 'MARIA', lastName: 'clark', age: 25 },
  { id: 4, firstName: 'Bob', lastName: null, age: undefined },
];

// 1) За одним ключем (числовим)
const byAgeAsc = users.slice().sort(compareBy(u => u.age, { order: 'asc', nulls: 'last' }));

// 2) За рядком, без урахування регістру і з урахуванням чисел (natural sort)
const collator = new Intl.Collator('en', { sensitivity: 'base', numeric: true });
const byLastInsensitive = users.slice().sort(compareBy(u => u.lastName, { collator, nulls: 'last' }));

// 3) Складений ключ: lastName, потім firstName, потім id
const byLast = compareBy(u => u.lastName, { collator, nulls: 'last' });
const byFirst = compareBy(u => u.firstName, { collator, nulls: 'last' });
const byIdAsc = compareBy(u => u.id);
const byFullNameThenId = users.slice().sort(compareByMany(byLast, byFirst, byIdAsc));

// 4) Змішаний напрямок: дата за спаданням, потім ім'я за зростанням
const orders = [
  { createdAt: '2024-05-01', name: 'zeta' },
  { createdAt: '2024-05-03', name: 'alpha' },
  { createdAt: '2024-05-03', name: 'bravo' },
];
const byDateDesc = compareBy(o => Date.parse(o.createdAt), { order: 'desc' });
const byNameAsc = compareBy(o => o.name, { collator: new Intl.Collator('en', { sensitivity: 'base' }) });
const ordersSorted = orders.slice().sort(compareByMany(byDateDesc, byNameAsc));

// 5) Decorate-Sort-Undecorate (перетворення Шварца) для дорогого ключа
const files = [
  { path: '/a/file9.txt' },
  { path: '/b/file10.txt' },
  { path: '/c/file2.txt' },
];
const natCollator = new Intl.Collator('en', { numeric: true, sensitivity: 'base' });
const sortedFiles = files
  .map(f => ({ f, k: f.path }))         // видобуваємо ключ один раз
  .sort((x, y) => natCollator.compare(x.k, y.k))
  .map(({ f }) => f);

console.log({ byAgeAsc, byLastInsensitive, byFullNameThenId, ordersSorted, sortedFiles });
```

## Приклад (Python)

```
users = [
    {"id": 3, "first": "Oleh", "last": "green", "age": 19},
    {"id": 1, "first": "Maria", "last": "Adams", "age": 25},
    {"id": 2, "first": "MARIA", "last": "clark", "age": 25},
    {"id": 4, "first": "Bob", "last": None, "age": None},
]

# За одним ключем (None в кінець)
sorted_by_age = sorted(users, key=lambda u: (u["age"] is None, u["age"]))

# Складений ключ (лексикографічно): last, first, id
sorted_by_name = sorted(
    users,
    key=lambda u: (
        (u["last"] or "").casefold(),
        (u["first"] or "").casefold(),
        u["id"],
    ),
)

# Змішаний напрямок: спадання за датою, зростання за іменем
orders = [
    {"created_at": "2024-05-01", "name": "zeta"},
    {"created_at": "2024-05-03", "name": "alpha"},
    {"created_at": "2024-05-03", "name": "bravo"},
]
from datetime import datetime

def ts(s):
    return int(datetime.fromisoformat(s).timestamp())

sorted_orders = sorted(
    orders,
    key=lambda o: (-ts(o["created_at"]), o["name"].casefold())
)

print(sorted_by_age)
print(sorted_by_name)
print(sorted_orders)
```

## Стабільність сортування і ключ

Стабільне сортування зберігає відносний порядок елементів з однаковим ключем. Це важливо при багатокрокових сортуваннях: можна спочатку відсортувати за вторинним ключем, потім за первинним - результат буде як сортування за складеним ключем. У сучасних реалізаціях JavaScript Array.prototype.sort є стабільним, Python sorted - теж.

## Підводні камені та рекомендації

- Числа vs рядки: '10' > '2' як рядки. Для «натурального» сортування рядків із числами використовуйте Intl.Collator(numeric: true) або розбір чисел.
- Регістр і локаль: використовуйте casefold()/toLowerCase() або Intl.Collator із потрібними налаштуваннями чутливості.
- null/undefined/NaN: визначте явні правила їхньої позиції (first/last). Різні рушії за умовчанням поводяться по-різному.
- Продуктивність: якщо ключ дорогий (парсинг дати, I/O, обчислення), застосовуйте «прикрашання-сортування-розпакування» (DSU), щоб не обчислювати ключ багаторазово.
- Пам'ять vs швидкість: DSU додає алокації, але знижує кількість обчислень ключа і порівнянь.
- Кастомні порядки: для сортування за заздалегідь визначеним списком (статуси) використовуйте відображення в індекс (map[status] → число) як ключ.
- Складені ключі: не склеюйте поля в один рядок без надійного роздільника - використовуйте послідовність компараторів або кортежі (у Python).

## Термінологічні зауваження

- «Ключ сортування» - це не обов'язково «первинний ключ» БД. Первинний ключ унікальний і ідентифікує запис, а ключ сортування - будь-який вираз для впорядкування.
- У БД роль ключа сортування відіграє вираз у ORDER BY (поле, функція, кілька полів із напрямком для кожного).

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати1061 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.