В чём разница между устойчивой и неустойчивой сортировками?

Определение устойчивости

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

Почему это важно

Устойчивость критична при сортировке по нескольким критериям. Например, если сначала отсортировать данные по имени, а затем по возрасту, устойчивая сортировка по возрасту сохранит алфавитный порядок среди людей одного возраста. Это позволяет комбинировать сортировки без потери информации.

Примеры алгоритмов

• Устойчивые: сортировка слиянием, пузырьковая, вставками, Timsort (используется в Python и Java).
• Неустойчивые: быстрая сортировка (в типичной реализации), пирамидальная, сортировка выбором.

Пример кода на JavaScript

// Устойчивая сортировка вставками
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

// Неустойчивая быстрая сортировка (простая версия)
function quickSort(arr) {
  if (arr.length <= 1) return arr;
  let pivot = arr[0];
  let left = [], right = [];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }
  return [...quickSort(left), pivot, ...quickSort(right)];
}

В примере быстрой сортировки элементы, равные pivot, могут попасть в правую часть, меняя их порядок относительно друг друга.

Вывод

Устойчивость важна, когда порядок равных элементов имеет значение, например, при сортировке таблиц по нескольким колонкам. Если требуется сохранить исходный порядок, выбирайте устойчивые алгоритмы, такие как сортировка слиянием или встроенные методы сортировки в большинстве языков.