Сортировки

Сортировка — фундаментальная операция в Computer Science, и на интервью Senior/Tech Lead важно понимать не просто “как работает QuickSort”, а когда выбрать какой алгоритм и почему. Существует три больших семейства сортировок: comparison-based (сравнение элементов, нижняя граница Ω(n log n) — MergeSort, QuickSort, HeapSort, TimSort), non-comparison (используют специфику данных, могут быть O(n) — Counting, Radix, Bucket), и гибриды (комбинируют подходы для оптимизации реальных сценариев — TimSort, IntroSort).

На практике готовые библиотечные сортировки почти всегда оптимальны: JavaScript (V8 engine) использует TimSort для Array.sort — стабильный, адаптивный алгоритм O(n log n), который блестяще работает на частично отсортированных данных (реальный мир!). Java для примитивов использует Dual-Pivot QuickSort (быстро, но нестабильно), для объектов — TimSort (стабильно). C++ std::sort — IntroSort (гибрид QuickSort + HeapSort + InsertionSort). Понимание этих выборов — ключ к senior-интервью.

Когда применять / Мотивация

На практике готовые библиотечные сортировки почти всегда оптимальны: JavaScript (V8 engine) использует TimSort для Array.sort — стабильный, адаптивный алгоритм O(n log n), который блестяще работает на частично отсортированных данных (реальный мир!). Java для примитивов использует Dual-Pivot QuickSort (быстро, но нестабильно), для объектов — TimSort (стабильно). C++ std::sort — IntroSort (гибрид QuickSort + HeapSort + InsertionSort). Понимание этих выборов — ключ к senior-интервью.

Идея / Как работает

Критические характеристики для выбора: (1) Стабильность — сохраняет относительный порядок равных элементов. Важно для сортировки по нескольким ключам (сначала по имени, потом по возрасту — если нестабильная, порядок имён у людей одного возраста нарушится). (2) In-place — O(1) дополнительной памяти (важно для больших данных). (3) Adaptive — ускоряется на почти отсортированных данных. (4) Cache-friendly — последовательный доступ к памяти (MergeSort лучше HeapSort по cache misses). (5) Worst-case гарантии — QuickSort имеет O(n²) на sorted input без рандомизации, HeapSort гарантирует O(n log n) всегда.

Когда применять non-comparison сортировки: Если диапазон значений мал и известен (целые числа 0..10⁶, символы, разряды), можно использовать Counting Sort за O(n+k), где k — диапазон. Для больших целых чисел — Radix Sort (сортировка по разрядам) за O(d·(n+k)), где d — количество разрядов. Bucket Sort — когда данные равномерно распределены, разбиваем на корзины, сортируем каждую отдельно. Нижняя граница Ω(n log n) для comparison-based сортировок доказывается через теорию информации: нужно различить n! перестановок, что требует log₂(n!) ≈ n log n сравнений.

Алгоритм	Best	Average	Worst	Space	Stable	Примечание
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	✓	Только для обучения
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	✗	Минимум обменов (n-1)
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	✓	Отлично для малых n, adaptive
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	✓	Стабильная, предсказуемая
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	✗	In-place, быстрая на практике
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	✗	In-place, гарантии, но плохой cache
Counting Sort	O(n+k)	O(n+k)	O(n+k)	O(k)	✓	k = диапазон значений
Radix Sort	O(d(n+k))	O(d(n+k))	O(d(n+k))	O(n+k)	✓	d = число разрядов
Tim Sort	O(n)	O(n log n)	O(n log n)	O(n)	✓	Python, Java, JS — адаптивный!

Реализация

Задача: Реализовать QuickSort с Lomuto partition scheme. Массив может содержать дубликаты. Объяснить, почему возникает O(n²) worst-case и как его избежать.

Подход: QuickSort — это divide-and-conquer: выбираем pivot (опорный элемент), разбиваем массив на две части (меньше pivot и больше-равно pivot), рекурсивно сортируем обе части. Lomuto partition — простая схема: pivot берём последний элемент, держим указатель i — граница “уже обработанных меньших элементов”. Идём указателем j слева направо: если a[j] < pivot, меняем местами a[i] и a[j], увеличиваем i. В конце ставим pivot на позицию i. Возвращаем i — pivot уже на своём финальном месте. Проблема O(n²): если массив отсортирован и pivot всегда последний, разбиение будет (n-1, 0), рекурсия вырождается в O(n²). Решения: (1) Случайный pivot — swap(a[random(lo, hi)], a[hi]) перед partition. (2) Median-of-three — pivot = median(a[lo], a[mid], a[hi]). (3) IntroSort — после log n уровней рекурсии переключаемся на HeapSort.

function quickSort(arr, lo = 0, hi = arr.length - 1) {
    if (lo >= hi) return;

    // ОПЦИОНАЛЬНО: рандомизация pivot для защиты от O(n²)
    const randomIdx = lo + Math.floor(Math.random() * (hi - lo + 1));
    [arr[randomIdx], arr[hi]] = [arr[hi], arr[randomIdx]];

    const pivotIndex = partition(arr, lo, hi);
    quickSort(arr, lo, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, hi);
  }

  function partition(arr, lo, hi) {
    const pivot = arr[hi];
    let i = lo; // граница "меньших" элементов

    for (let j = lo; j < hi; j++) {
      if (arr[j] < pivot) {
        // Нашли элемент меньше pivot — добавляем в левую часть
        [arr[i], arr[j]] = [arr[j], arr[i]];
        i++;
      }
    }

    // Ставим pivot на финальную позицию
    [arr[i], arr[hi]] = [arr[hi], arr[i]];
    return i;
  }

  // Демонстрация
  const arr = [3, 6, 8, 10, 1, 2, 1];
  quickSort(arr);
  console.log(arr); // [1, 1, 2, 3, 6, 8, 10]

  // Для сравнения: MergeSort (стабильная)
  function mergeSort(arr) {
    if (arr.length <= 1) return arr;

    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    return merge(left, right);
  }

  function merge(left, right) {
    const result = [];
    let i = 0, j = 0;

    while (i < left.length && j < right.length) {
      // <= для стабильности (не меняем порядок равных)
      if (left[i] <= right[j]) {
        result.push(left[i++]);
      } else {
        result.push(right[j++]);
      }
    }

    return result.concat(left.slice(i), right.slice(j));
  }

  // QuickSelect — бонус: k-й наименьший элемент за O(n) в среднем
  function quickSelect(arr, k) {
    // k — 1-indexed (k=1 для минимума)
    let lo = 0, hi = arr.length - 1;

    while (true) {
      const pivotIndex = partition(arr, lo, hi);

      if (pivotIndex === k - 1) return arr[pivotIndex];
      if (pivotIndex < k - 1) {
        lo = pivotIndex + 1; // ищем в правой части
      } else {
        hi = pivotIndex - 1; // ищем в левой части
      }
    }
  }

  const nums = [3, 2, 1, 5, 6, 4];
  console.log(quickSelect(nums, 2)); // 2-й наименьший = 2
  console.log(quickSelect(nums, 4)); // 4-й наименьший = 4

Трассировка

Трассировка partition([3, 6, 8, 10, 1, 2, 1], 0, 6):

  Массив: [3, 6, 8, 10, 1, 2, 1], lo=0, hi=6
  pivot = arr[6] = 1
  i = 0 (граница "меньших")

  j=0: arr[0]=3, 3 >= 1, пропускаем
    [3, 6, 8, 10, 1, 2, 1], i=0

  j=1: arr[1]=6, 6 >= 1, пропускаем
    [3, 6, 8, 10, 1, 2, 1], i=0

  j=2: arr[2]=8, 8 >= 1, пропускаем
    [3, 6, 8, 10, 1, 2, 1], i=0

  j=3: arr[3]=10, 10 >= 1, пропускаем
    [3, 6, 8, 10, 1, 2, 1], i=0

  j=4: arr[4]=1, 1 < 1? Нет (равно), пропускаем
    [3, 6, 8, 10, 1, 2, 1], i=0

  j=5: arr[5]=2, 2 >= 1, пропускаем
    [3, 6, 8, 10, 1, 2, 1], i=0

  Цикл завершён. Теперь ставим pivot на место i:
  swap(arr[0], arr[6]): [1, 6, 8, 10, 1, 2, 3]
  Возвращаем i=0

  Pivot=1 теперь на финальной позиции 0. НО: второй 1 справа от pivot!
  Это показывает, что QuickSort НЕСТАБИЛЕН — дубликаты могут поменяться местами.

  Рекурсивные вызовы:
    quickSort([1, 6, 8, 10, 1, 2, 3], 0, -1) → lo > hi, возврат
    quickSort([1, 6, 8, 10, 1, 2, 3], 1, 6) → сортируем правую часть

  Следующий partition([6, 8, 10, 1, 2, 3], 1, 6) с pivot=3:
  i=1, j пробегает 1..5:
    j=1: 6>=3, skip
    j=2: 8>=3, skip
    j=3: 10>=3, skip
    j=4: 1<3, swap(arr[1], arr[4]) → [1, 1, 10, 6, 8, 2, 3], i=2
    j=5: 2<3, swap(arr[2], arr[5]) → [1, 1, 2, 6, 8, 10, 3], i=3
  swap(arr[3], arr[6]) → [1, 1, 2, 3, 8, 10, 6]
  return i=3

  И так далее... В итоге массив отсортируется.

Сложность

Анализ сложности: Time: Средний случай O(n log n) — на каждом уровне рекурсии обрабатываем O(n) элементов, глубина рекурсии log n (при сбалансированных разбиениях). Лучший случай O(n log n) — pivot всегда медиана. Худший случай O(n²) — pivot всегда минимум или максимум (массив отсортирован, и мы берём последний элемент), разбиение (0, n-1) → рекурсия глубиной n. Рандомизация делает вероятность худшего случая пренебрежимо малой. QuickSelect имеет O(n) средний случай — доказывается через рекуррентное соотношение T(n) = T(n/2) + O(n) (обрабатываем только одну половину). Space: O(log n) для стека рекурсии в среднем случае, O(n) в худшем (можно оптимизировать до O(log n) worst-case, всегда рекурсивно обрабатывая меньшую часть). MergeSort — O(n) дополнительной памяти для merge-буфера.

Типичные ошибки на интервью: (1) Забыть, что QuickSort нестабилен. (2) Не знать, что QuickSort имеет O(n²) worst-case без рандомизации (sorted или reverse sorted input при naive pivot выборе). (3) Утверждать, что HeapSort лучше MergeSort — на практике HeapSort медленнее из-за плохой cache locality. (4) Не понимать разницу между Lomuto и Hoare partition schemes в QuickSort (Hoare эффективнее, но сложнее реализовать корректно). (5) Забыть про InsertionSort для маленьких подмассивов (n < 10-20) — это стандартная оптимизация в реальных реализациях.

Типичные ошибки и подводные камни

(1) “Почему Python/JavaScript используют TimSort, а не QuickSort?” — TimSort стабилен, адаптивен (O(n) на уже отсортированных данных), имеет гарантированный O(n log n) worst-case. QuickSort нестабилен и имеет O(n²) worst-case. (2) “Когда использовать HeapSort?” — Когда нужны worst-case гарантии O(n log n) + in-place O(1) память, и не важна cache locality (embedded systems, hard real-time). (3) “Как сортировать миллиард целых чисел с малым диапазоном?” — Counting Sort за O(n+k), если k ≤ 10⁶. Radix Sort, если числа большие. (4) “Что такое Dual-Pivot QuickSort?” — Выбираем два pivot’а, делим массив на три части (

p2). Java использует для примитивов — меньше swaps, лучше на практике. (5) “Реализуй stable QuickSort” — Нельзя сделать in-place и stable одновременно. Можно O(n) памятью: разбиваем на три списка (меньше, равно, больше), конкатенируем — но это уже не QuickSort, а 3-way partitioning.

Follow-up вопросы интервьюера

1. Как улучшить QuickSort для массивов с большим количеством дубликатов? — Использовать 3-way partition (Dutch National Flag): делим на три части (< pivot, = pivot, > pivot). Элементы равные pivot уже отсортированы, не участвуют в рекурсии. Сложность O(n log k), где k — количество уникальных элементов. Реализация: два указателя lt и gt, элементы в [lt..gt] равны pivot.
2. Почему MergeSort не используется в C++ std::sort? — MergeSort требует O(n) дополнительной памяти. IntroSort (hybrid QuickSort + HeapSort + InsertionSort) работает in-place с O(log n) памятью, даёт те же гарантии O(n log n), но быстрее на практике благодаря хорошей cache locality QuickSort.
3. Как работает TimSort? — Ищет “runs” — уже отсортированные (возрастающие или убывающие) подпоследовательности, дополняет их до минимальной длины (32-64) InsertionSort’ом, затем мержит runs через MergeSort с умной стратегией (поддерживает stack runs и мержит согласно инвариантам для баланса). Adaptive: O(n) на отсортированных данных, O(n log n) на случайных. Stable.
4. Реализуй Counting Sort для массива с диапазоном [0, k]. — Создаём count[k+1], подсчитываем частоты, делаем prefix sum (count[i] += count[i-1]) — теперь count[i] = количество элементов ≤ i. Проходим массив справа налево, ставим arr[i] на позицию count[arr[i]]-1, уменьшаем count[arr[i]]. Справа налево — для стабильности.
5. Когда Radix Sort предпочтительнее Comparison sorts? — Для целых чисел с ограниченным количеством разрядов (например, 32-bit integers → d=4 байта, 256 возможных значений на разряд, Radix LSD за O(4(n+256)) = O(n)). Также для строк фиксированной длины. На практике константы велики, поэтому Radix выигрывает только на больших n > 100K и когда comparison дорогой.
6. Как отсортировать связный список in-place за O(n log n)? — MergeSort для списков работает in-place (O(1) дополнительной памяти, не считая O(log n) для стека): находим середину за O(n) через fast/slow pointers, рекурсивно сортируем половинки, мержим за O(n) переставляя указатели. Суммарно O(n log n) время, O(log n) стек. QuickSort для списков плох — поиск pivot’а дорогой, партиционирование неэффективно.

Чеклист на собес

• Знаю наизусть Time/Space/Stable/In-place для всех ключевых сортировок: merge, quick, heap, insertion, counting, radix.
• Понимаю, что V8 Array.prototype.sort использует TimSort (стабильная, гибрид merge+insertion).
• Quicksort: средний O(n log n), худший O(n²). Использую randomized pivot или median-of-three для защиты.
• Mergesort: гарантированный O(n log n), стабильный, но не in-place — O(n) доп. памяти.
• Heapsort: O(n log n), in-place, не стабильный — выбираю когда важна гарантия и память.
• Counting/Radix: O(n+k) или O(d·n), но требуют ограниченного диапазона значений.
• Quickselect: O(n) средне для k-го по порядку — частая follow-up задача.
• Помню, что «стабильность» = равные элементы сохраняют исходный порядок (важно для multi-key sort).