Що таке «ключ» при сортуванні?

АлгоритмиJunior~2 хв читання

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

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

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

Ключ сортування (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 (поле, функція, кілька полів із напрямком для кожного).

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

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.