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

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

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

Популярные алгоритмы

• Пузырьковая сортировка (Bubble Sort): Проходит по массиву, сравнивая соседние элементы и меняя их местами, если они не в порядке. Сложность O(n²), неэффективна для больших данных.
• Быстрая сортировка (Quick Sort): Выбирает опорный элемент, делит массив на части меньше и больше опорного, рекурсивно сортирует их. Средняя сложность O(n log n), но в худшем случае O(n²).
• Сортировка слиянием (Merge Sort): Делит массив пополам, рекурсивно сортирует каждую половину, затем сливает их. Всегда O(n log n), требует O(n) дополнительной памяти.
• Сортировка вставками (Insertion Sort): Строит отсортированный массив, вставляя каждый новый элемент на правильное место. Эффективна для малых или почти отсортированных данных (O(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)];
}

console.log(quickSort([3, 6, 8, 10, 1, 2, 1])); // [1, 1, 2, 3, 6, 8, 10]

Вывод

Выбор алгоритма сортировки зависит от контекста: для небольших массивов подойдут простые алгоритмы (вставками), для больших — быстрая или слиянием. Понимание их сложности помогает писать эффективный код.