Какие алгоритмы сортировки знаете?

Основные алгоритмы сортировки

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

Простые алгоритмы (O(n²))

• Пузырьковая сортировка: последовательно сравнивает соседние элементы и меняет их местами, если они не в порядке. Проста, но неэффективна для больших массивов.
• Сортировка вставками: строит отсортированный массив, вставляя каждый новый элемент на правильное место. Хорошо работает на почти отсортированных данных.
• Сортировка выбором: находит минимальный элемент и ставит его в начало, повторяя для оставшейся части.

Быстрые алгоритмы (O(n log n))

• Быстрая сортировка (Quicksort): выбирает опорный элемент, делит массив на части меньше и больше опорного, рекурсивно сортирует их. В среднем O(n log n), но в худшем случае O(n²). Неустойчива.
• Сортировка слиянием (Mergesort): делит массив пополам, рекурсивно сортирует каждую половину, затем сливает их. Всегда O(n log n), стабильна, требует дополнительной памяти O(n).
• Пирамидальная сортировка (Heapsort): строит кучу из массива, затем извлекает максимальный элемент и помещает в конец. O(n log n), нестабильна.

Пример кода (быстрая сортировка на JavaScript)

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[0];
  const left = [];
  const 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)];
}

Вывод

Выбор алгоритма сортировки зависит от контекста: для небольших массивов подойдут простые методы, для больших — быстрая или слиянием. Сортировка слиянием предпочтительна при необходимости стабильности, а быстрая — при ограниченной памяти (in-place).