Быстрая сортировка (Quick Sort): полное руководство по эффективному алгоритму

Почему быстрая сортировка важна?

Быстрая сортировка (Quick Sort) — один из самых эффективных и широко используемых алгоритмов сортировки в программировании:

• 🚀 Средняя временная сложность O(n log n) — одна из лучших среди алгоритмов сортировки
• 💾 Сортировка "на месте" — минимальное использование дополнительной памяти
• 🎯 Отличная производительность на практике — часто быстрее других O(n log n) алгоритмов
• 📚 Используется в стандартных библиотеках многих языков программирования
• 💼 Частый вопрос на технических собеседованиях в топовых компаниях

Что такое быстрая сортировка?

Быстрая сортировка — это алгоритм сортировки, основанный на принципе "разделяй и властвуй" (divide and conquer). Алгоритм был разработан британским ученым Тони Хоаром в 1959 году и до сих пор остается одним из самых популярных методов сортировки.

Принцип работы:

1. Выбор опорного элемента (pivot): Из массива выбирается один элемент, называемый опорным
2. Разделение (partitioning): Массив перераспределяется так, что все элементы меньше опорного оказываются слева от него, а все элементы больше — справа
3. Рекурсивная сортировка: Рекурсивно применяем те же шаги к левой и правой частям массива

Визуализация работы алгоритма:

// Исходный массив: [8, 3, 7, 4, 9, 2, 6, 5]
// Выбираем опорный элемент (например, последний): 5

// После разделения:
// [3, 4, 2] [5] [8, 7, 9, 6]
// меньше 5   ^   больше 5

// Рекурсивно сортируем левую часть [3, 4, 2]:
// опорный = 2: [2] [3, 4]

// Рекурсивно сортируем правую часть [8, 7, 9, 6]:
// опорный = 6: [6] [8, 7, 9]

// Итоговый результат: [2, 3, 4, 5, 6, 7, 8, 9]

Реализации Quick Sort

Решение 1: Классическая реализация (схема Ломуто) 🔍

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    // Получаем индекс опорного элемента после разделения
    const pivotIndex = partition(arr, low, high);

    // Рекурсивно сортируем элементы до и после опорного
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }

  return arr;
}

function partition(arr, low, high) {
  // Выбираем последний элемент как опорный
  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[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  // Ставим опорный элемент на правильную позицию
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];

  return i + 1;
}

// Пример использования
const array = [8, 3, 7, 4, 9, 2, 6, 5];
console.log(quickSort(array)); // [2, 3, 4, 5, 6, 7, 8, 9]

Анализ решения:

✅ Простая и понятная реализация

✅ Хорошо подходит для обучения

✅ Сортировка "на месте" — O(1) дополнительной памяти

❌ Худший случай O(n²) на уже отсортированных массивах

❌ Не самая эффективная схема разделения

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Решение 2: Схема Хоара (оригинальная) 🚀

function quickSortHoare(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = partitionHoare(arr, low, high);

    quickSortHoare(arr, low, pivotIndex);
    quickSortHoare(arr, pivotIndex + 1, high);
  }

  return arr;
}

function partitionHoare(arr, low, high) {
  // Выбираем средний элемент как опорный
  const pivot = arr[Math.floor((low + high) / 2)];

  let i = low - 1;
  let j = high + 1;

  while (true) {
    // Ищем элемент >= pivot слева
    do {
      i++;
    } while (arr[i] < pivot);

    // Ищем элемент <= pivot справа
    do {
      j--;
    } while (arr[j] > pivot);

    // Если указатели встретились, возвращаем j
    if (i >= j) {
      return j;
    }

    // Меняем элементы местами
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
}

// Пример использования
const array = [8, 3, 7, 4, 9, 2, 6, 5];
console.log(quickSortHoare(array)); // [2, 3, 4, 5, 6, 7, 8, 9]

Характеристики:

✅ Меньше обменов в среднем, чем схема Ломуто

✅ Более эффективна на практике

✅ Оригинальная схема автора алгоритма

❌ Более сложная для понимания

❌ Требует внимательности при реализации

Решение 3: Quick Sort с рандомизацией 🎲

function quickSortRandomized(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    // Рандомизируем выбор опорного элемента
    const randomIndex = Math.floor(Math.random() * (high - low + 1)) + low;
    [arr[randomIndex], arr[high]] = [arr[high], arr[randomIndex]];

    const pivotIndex = partition(arr, low, high);

    quickSortRandomized(arr, low, pivotIndex - 1);
    quickSortRandomized(arr, pivotIndex + 1, high);
  }

  return arr;
}

function partition(arr, low, high) {
  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]];
    }
  }

  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

// Пример использования
const array = [8, 3, 7, 4, 9, 2, 6, 5];
console.log(quickSortRandomized(array)); // [2, 3, 4, 5, 6, 7, 8, 9]

Преимущества:

✅ Вероятность худшего случая O(n²) крайне мала

✅ Защита от "вредных" входных данных

✅ Математическое ожидание всегда O(n log n)

❌ Непредсказуемость времени выполнения

Решение 4: Трехчастное разделение (Dutch National Flag) 🇳🇱

function quickSort3Way(arr, low = 0, high = arr.length - 1) {
  if (low >= high) return arr;

  // Трехчастное разделение
  let lt = low;      // arr[low..lt-1] < pivot
  let gt = high;     // arr[gt+1..high] > pivot
  let i = low + 1;   // arr[lt..i-1] == pivot

  const pivot = arr[low];

  while (i <= gt) {
    if (arr[i] < pivot) {
      [arr[lt], arr[i]] = [arr[i], arr[lt]];
      lt++;
      i++;
    } else if (arr[i] > pivot) {
      [arr[i], arr[gt]] = [arr[gt], arr[i]];
      gt--;
    } else {
      i++;
    }
  }

  // Рекурсивно сортируем левую и правую части
  quickSort3Way(arr, low, lt - 1);
  quickSort3Way(arr, gt + 1, high);

  return arr;
}

// Пример использования — особенно эффективен для массивов с дубликатами
const array = [3, 5, 2, 5, 3, 1, 5, 2, 3];
console.log(quickSort3Way(array)); // [1, 2, 2, 3, 3, 3, 5, 5, 5]

Особенности:

✅ Оптимален для массивов с множеством дубликатов

✅ Линейная сложность O(n) для массивов с малым числом уникальных элементов

✅ Элегантное решение задачи "голландского флага"

❌ Дополнительные накладные расходы для массивов без дубликатов

Решение 5: Итеративная реализация Quick Sort 📚

function quickSortIterative(arr) {
  const stack = [];

  // Добавляем начальный диапазон в стек
  stack.push(0);
  stack.push(arr.length - 1);

  while (stack.length > 0) {
    // Извлекаем high и low из стека
    const high = stack.pop();
    const low = stack.pop();

    if (low < high) {
      // Выполняем разделение
      const pivotIndex = partition(arr, low, high);

      // Добавляем левый подмассив в стек
      stack.push(low);
      stack.push(pivotIndex - 1);

      // Добавляем правый подмассив в стек
      stack.push(pivotIndex + 1);
      stack.push(high);
    }
  }

  return arr;
}

function partition(arr, low, high) {
  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]];
    }
  }

  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

// Пример использования
const array = [8, 3, 7, 4, 9, 2, 6, 5];
console.log(quickSortIterative(array)); // [2, 3, 4, 5, 6, 7, 8, 9]

Преимущества:

✅ Нет риска переполнения стека вызовов

✅ Подходит для очень больших массивов

✅ Легче контролировать использование памяти

❌ Менее интуитивный код

Реализация на Python

def quick_sort(arr: list, low: int = 0, high: int = None) -> list:
    """
    Быстрая сортировка массива

    Args:
        arr: Массив для сортировки
        low: Начальный индекс
        high: Конечный индекс

    Returns:
        Отсортированный массив
    """
    if high is None:
        high = len(arr) - 1

    if low < high:
        # Получаем индекс опорного элемента
        pivot_index = partition(arr, low, high)

        # Рекурсивно сортируем подмассивы
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)

    return arr


def partition(arr: list, low: int, high: int) -> int:
    """
    Разделение массива относительно опорного элемента

    Args:
        arr: Массив для разделения
        low: Начальный индекс
        high: Конечный индекс

    Returns:
        Индекс опорного элемента после разделения
    """
    # Выбираем последний элемент как опорный
    pivot = arr[high]

    # Индекс меньшего элемента
    i = low - 1

    for j in range(low, high):
        # Если текущий элемент меньше или равен опорному
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    # Ставим опорный элемент на правильную позицию
    arr[i + 1], arr[high] = arr[high], arr[i + 1]

    return i + 1


# Пример использования
array = [8, 3, 7, 4, 9, 2, 6, 5]
print(quick_sort(array))  # [2, 3, 4, 5, 6, 7, 8, 9]

Python: Quick Sort с медианой трех

import random

def quick_sort_median(arr: list, low: int = 0, high: int = None) -> list:
    """Quick Sort с выбором медианы из трех элементов"""
    if high is None:
        high = len(arr) - 1

    if low < high:
        # Выбираем медиану из первого, среднего и последнего элементов
        mid = (low + high) // 2

        # Сортируем три элемента
        if arr[low] > arr[mid]:
            arr[low], arr[mid] = arr[mid], arr[low]
        if arr[low] > arr[high]:
            arr[low], arr[high] = arr[high], arr[low]
        if arr[mid] > arr[high]:
            arr[mid], arr[high] = arr[high], arr[mid]

        # Ставим медиану перед последним элементом
        arr[mid], arr[high - 1] = arr[high - 1], arr[mid]

        # Разделяем с использованием медианы как опорного
        pivot_index = partition_median(arr, low, high)

        quick_sort_median(arr, low, pivot_index - 1)
        quick_sort_median(arr, pivot_index + 1, high)

    return arr


def partition_median(arr: list, low: int, high: int) -> int:
    """Разделение с медианой в позиции high - 1"""
    pivot = arr[high - 1]
    i = low
    j = high - 2

    while True:
        while arr[i] < pivot:
            i += 1
        while j > low and arr[j] > pivot:
            j -= 1

        if i >= j:
            break

        arr[i], arr[j] = arr[j], arr[i]
        i += 1
        j -= 1

    arr[i], arr[high - 1] = arr[high - 1], arr[i]
    return i


# Пример использования
array = [8, 3, 7, 4, 9, 2, 6, 5]
print(quick_sort_median(array))  # [2, 3, 4, 5, 6, 7, 8, 9]

Временная и пространственная сложность

Временная сложность:

Пространственная сложность:

• O(log n) в среднем — для стека рекурсии
• O(n) в худшем случае — при несбалансированном разделении
• O(1) дополнительной памяти — сортировка выполняется "на месте"

Детальный анализ:

// Лучший случай — O(n log n)
// Глубина рекурсии: log n
// На каждом уровне: n сравнений
// Итого: n * log n

// Худший случай — O(n²)
// Пример: отсортированный массив [1, 2, 3, 4, 5]
// С опорным = последний элемент:
// Уровень 1: n сравнений, разделение на [1,2,3,4] и []
// Уровень 2: n-1 сравнений, разделение на [1,2,3] и []
// ...
// Итого: n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²)

Сравнение с другими алгоритмами сортировки

Почему Quick Sort часто предпочтительнее?

1. Кэш-эффективность: Quick Sort работает с локальными данными, что улучшает использование кэша процессора
2. Меньше обменов: В среднем требуется меньше операций перемещения данных
3. Tail-call оптимизация: Возможность оптимизации хвостовой рекурсии

Стратегии выбора опорного элемента

1. Первый элемент

const pivot = arr[low];
// ❌ Плохо для отсортированных массивов

2. Последний элемент

const pivot = arr[high];
// ❌ Плохо для отсортированных массивов

3. Случайный элемент

const randomIndex = Math.floor(Math.random() * (high - low + 1)) + low;
const pivot = arr[randomIndex];
// ✅ Хорошая защита от худшего случая

4. Медиана трех

const mid = Math.floor((low + high) / 2);
// Находим медиану из arr[low], arr[mid], arr[high]
// ✅ Отличный баланс между простотой и эффективностью

5. Медиана медиан (Introselect)

// Гарантирует O(n log n) в худшем случае
// Используется в интроспективной сортировке
// ✅ Теоретически оптимально, но накладные расходы

Оптимизации Quick Sort

1. Переход на Insertion Sort для малых массивов

function optimizedQuickSort(arr, low = 0, high = arr.length - 1) {
  const INSERTION_THRESHOLD = 10;

  if (high - low < INSERTION_THRESHOLD) {
    // Insertion Sort для малых массивов
    for (let i = low + 1; i <= high; i++) {
      const key = arr[i];
      let j = i - 1;
      while (j >= low && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
      }
      arr[j + 1] = key;
    }
    return arr;
  }

  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    optimizedQuickSort(arr, low, pivotIndex - 1);
    optimizedQuickSort(arr, pivotIndex + 1, high);
  }

  return arr;
}

2. Оптимизация хвостовой рекурсии

function quickSortTailOptimized(arr, low = 0, high = arr.length - 1) {
  while (low < high) {
    const pivotIndex = partition(arr, low, high);

    // Рекурсивно сортируем меньшую часть
    if (pivotIndex - low < high - pivotIndex) {
      quickSortTailOptimized(arr, low, pivotIndex - 1);
      low = pivotIndex + 1;
    } else {
      quickSortTailOptimized(arr, pivotIndex + 1, high);
      high = pivotIndex - 1;
    }
  }

  return arr;
}

3. Интроспективная сортировка (Introsort)

function introsort(arr) {
  const maxDepth = Math.floor(2 * Math.log2(arr.length));
  introsortHelper(arr, 0, arr.length - 1, maxDepth);
  return arr;
}

function introsortHelper(arr, low, high, depthLimit) {
  const size = high - low + 1;

  if (size < 16) {
    // Insertion Sort для малых массивов
    insertionSort(arr, low, high);
    return;
  }

  if (depthLimit === 0) {
    // Переключаемся на Heap Sort при превышении глубины
    heapSort(arr, low, high);
    return;
  }

  const pivotIndex = partition(arr, low, high);
  introsortHelper(arr, low, pivotIndex - 1, depthLimit - 1);
  introsortHelper(arr, pivotIndex + 1, high, depthLimit - 1);
}

Распространенные ошибки при реализации

1. 🤦‍♂️ Неправильные границы рекурсии: Забыть условие low < high

2. 😅 Бесконечная рекурсия: Неправильное обновление индексов в разделении

3. 🐛 Переполнение стека: Отсутствие оптимизации хвостовой рекурсии для больших массивов

4. 😕 Плохой выбор опорного: Использование первого/последнего элемента без рандомизации

5. 🔄 Нестабильность: Ожидание сохранения порядка равных элементов

Практические применения Quick Sort

Стандартные библиотеки

• C: qsort() в стандартной библиотеке
• Java: Arrays.sort() для примитивных типов (Dual-Pivot Quick Sort)
• Python: list.sort() и sorted() используют Timsort (гибрид)
• JavaScript: V8 использует Timsort для Array.sort()

Когда использовать Quick Sort?

✅ Используйте когда:

• Нужна высокая средняя производительность
• Работаете с большими массивами в памяти
• Не критична стабильность сортировки
• Есть возможность рандомизации

❌ Не используйте когда:

• Требуется стабильная сортировка
• Гарантирован худший случай (отсортированные данные)
• Работаете со связными списками
• Критично O(n log n) в худшем случае

Интересные факты о Quick Sort

1. 📅 Алгоритм был изобретен Тони Хоаром в 1959 году, когда ему было 25 лет
2. 🏆 Quick Sort считается одним из 10 самых важных алгоритмов XX века
3. 🔬 Название "Quick Sort" было выбрано из-за высокой скорости на практике
4. 💡 Хоар придумал алгоритм, работая над машинным переводом в МГУ

Заключение

Быстрая сортировка — это мощный и элегантный алгоритм, который:

• 🏎️ Обеспечивает отличную производительность O(n log n) в среднем случае
• 💾 Эффективно использует память благодаря сортировке "на месте"
• 🔧 Легко оптимизируется под конкретные условия
• 📚 Служит основой для понимания принципа "разделяй и властвуй"
• 🎯 Широко применяется в стандартных библиотеках языков программирования

Понимание Quick Sort и его вариаций — необходимый навык для любого разработчика, готовящегося к техническим собеседованиям или работающего с задачами оптимизации производительности.