Быстрая сортировка

Алгоритмы сортировки

Описание

Быстрая сортировка (Quick Sort) — это эффективный алгоритм сортировки, использующий стратегию «разделяй и властвуй». Он выбирает опорный элемент (pivot) и разделяет массив на два подмассива: элементы, меньшие или равные опорному, и элементы, большие опорного. Затем подмассивы сортируются рекурсивно.

Зачем это нужно

Быстрая сортировка — один из наиболее широко используемых алгоритмов сортировки на практике. Она является стандартным алгоритмом сортировки во многих языках программирования и стандартных библиотеках. Понимание быстрой сортировки помогает освоить парадигму «разделяй и властвуй», которая лежит в основе многих эффективных алгоритмов.

Визуализация

Начальное состояние: неотсортированный массив

Неотсортировано

Опорный

Сравнение

Обмен

Отсортировано

Шаг 1 из 32

Скорость:

Сложность

Лучший случайO(n log n)

Средний случайO(n log n)

Худший случайO(n²)

Сложность по памятиO(log n)

Пример кода

function quickSort(arr: number[], low = 0, high = arr.length - 1): void {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }
}

function partition(arr: number[], low: number, high: number): number {
  const pivot = arr[high];
  let i = low - 1;

  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  // Place pivot in its final position
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

// Usage example
const unsorted = [38, 27, 43, 3, 9, 82, 10];
const sorted = [...unsorted]; // Copy to avoid mutating original
quickSort(sorted);
console.log(sorted); // [3, 9, 10, 27, 38, 43, 82]

Задачи на LeetCode

#912Sort an Array

Средняя

#215Kth Largest Element in an Array

Средняя

#973K Closest Points to Origin

Средняя

#347Top K Frequent Elements

Средняя