Что такое quicksort

Что проверяют

Умеете ли вы разложить принцип «разделяй и властвуй» на разбиение и рекурсию, назвать сложность честно, включая худший случай и память под стек, и понимаете ли, что в реальном коде на Java вы вызовете библиотечную сортировку, а не свою.

Как отвечать

Выбираем опорный элемент, за один проход переставляем массив так, что слева от опорного меньшие, справа большие, затем рекурсивно сортируем обе части. В среднем O(n log n), в худшем O(n²), сортировка на месте, но стек рекурсии O(log n), и она не стабильна.

static int partition(int[] a, int low, int high) {
    int pivot = a[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (a[j] < pivot) {
            i++;
            int t = a[i]; a[i] = a[j]; a[j] = t;
        }
    }
    int t = a[i + 1]; a[i + 1] = a[high]; a[high] = t;
    return i + 1;
}

Дальше стоит показать, что вы знаете лечение слабых мест. Худший случай это неудачный опорный: при опорном с края отсортированный вход даёт линейную глубину рекурсии, лечится случайным выбором или медианой трёх. Массу одинаковых значений лечит трёхпутевое разбиение на меньшие, равные и большие. Глубину стека ограничивают, уходя рекурсией в меньшую часть и продолжая циклом по большей.

Сильный финал про Java: Arrays.sort для примитивов это двухопорный quicksort, а для объектов TimSort, потому что там нужна стабильность и сравнения дороги.

Где спотыкаются

Ошибаются в границах разбиения и получают бесконечную рекурсию или потерянный элемент. Ключевая мысль: после разбиения опорный уже стоит на своём окончательном месте, поэтому в рекурсию идут отрезки без него.

Называют память константной. На месте здесь означает отсутствие второго массива, но стек рекурсии в среднем логарифмический, а без случайного опорного и без хвостовой оптимизации на подобранном входе он вырастает линейно и приводит к переполнению стека.

Утверждают, что quicksort всегда быстрее сортировки слиянием, и не могут объяснить, почему в стандартной библиотеке для объектов выбран другой алгоритм. Ответ в гарантии: слияние даёт O(n log n) в худшем случае и сохраняет порядок равных элементов, что важно при сортировке по нескольким полям.