Стабильность сортировок

Стабильная сортировка (stable sort) — алгоритм сортировки, гарантирующий сохранение исходного относительного порядка элементов с одинаковыми ключами сортировки.

Зачем нужно

При сортировке объектов по одному полю стабильность сохраняет предыдущий порядок по другому полю. Например, если список сотрудников сначала отсортировать по городу, а затем стабильно — по имени, то внутри каждого имени порядок по городу сохранится. Нестабильная сортировка разрушает этот вторичный порядок.

Где используется

  • Многоуровневая сортировка: сначала по дате, потом по имени
  • Radix Sort требует стабильного субалгоритма (Counting Sort)
  • UI-таблицы: сортировка по колонке без потери порядка по предыдущей
  • База данных: сортировка результатов запроса

Основной контент

Определение на примере

const students = [
  { name: 'Алиса', grade: 85 },
  { name: 'Боб',   grade: 92 },
  { name: 'Алиса', grade: 78 }, // вторая Алиса
  { name: 'Боб',   grade: 88 },
];

// Стабильная сортировка по grade:
// [78-Алиса, 85-Алиса, 88-Боб, 92-Боб]
// Порядок двух Алис (85 перед 78) и двух Бобов (92 перед 88)
// соответствует их исходному порядку в массиве

// Нестабильная сортировка может дать:
// [78-Алиса, 85-Алиса, 92-Боб, 88-Боб] ← Бобы поменялись

Стабильные vs нестабильные алгоритмы

Алгоритм Стабильный Примечание
Bubble Sort Да При строгом >
Insertion Sort Да По умолчанию
Merge Sort Да При <= в условии слияния
Counting Sort Да В версии с prefix sum, обход с конца
Tim Sort Да Python, Java
Selection Sort Нет Swap нарушает порядок
Heap Sort Нет Heap property нарушает порядок
Quick Sort Нет Стандартная реализация

Как сделать нестабильную сортировку «стабильной»

// Добавить индекс как вторичный ключ сравнения
function stableSort(arr, compareFn) {
  return arr
    .map((item, index) => ({ item, index }))  // прикрепить индекс
    .sort((a, b) => {
      const cmp = compareFn(a.item, b.item);
      return cmp !== 0 ? cmp : a.index - b.index; // при равенстве — по индексу
    })
    .map(({ item }) => item);
}

const data = [
  { name: 'Боб', grade: 85 },
  { name: 'Алиса', grade: 85 },
];
console.log(stableSort(data, (a, b) => a.grade - b.grade));
// Боб остаётся перед Алисой (исходный порядок)

Array.prototype.sort() в JavaScript

До ES2019 спецификация не гарантировала стабильность Array.sort(). Начиная с ES2019 (и V8 7.0+) сортировка обязана быть стабильной.

// Современный JS (Node.js >= 11, Chrome >= 70): стабильная!
const arr = [{ v: 1, k: 'b' }, { v: 1, k: 'a' }];
arr.sort((a, b) => a.v - b.v);
// Гарантированно: [{v:1, k:'b'}, {v:1, k:'a'}] — порядок сохранён

Частые ошибки

  • Использовать нестабильный Quick Sort там, где нужна стабильность — порядок равных элементов непредсказуем.
  • Не использовать трюк с индексом для гарантии стабильности при использовании нестабильных нативных сортировок в старых средах.
  • Считать, что стабильная сортировка всегда медленнее — Merge Sort O(n log n) и стабильна.
  • Путать stable sort со stable algorithm: стабильность относится только к порядку равных элементов.

Связанные темы

Ресурсы