Введение

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

Почему это важно для интервью:

  • Многие задачи становятся проще после сортировки массива
  • Задачи на два указателя часто требуют предварительной сортировки
  • Задачи на интервалы почти всегда начинаются с сортировки
  • Бинарный поиск требует отсортированный массив
  • Понимание алгоритмов сортировки помогает оценивать сложность решений

Что вы узнаете:

  1. Как использовать встроенные функции сортировки (sorted, sort, Arrays.sort, Collections.sort)
  2. Как распознавать задачи, где нужна предварительная сортировка
  3. Как работают основные алгоритмы сортировки:
    • Квадратичные сортировки: Bubble Sort, Selection Sort, Insertion Sort
    • Эффективные сортировки: Merge Sort, Quick Sort
    • Оптимизированные и специализированные сортировки: Counting Sort, Timsort, Dual-Pivot Quicksort
  4. Когда использовать сортировку, а когда нет

Сортировка на практике

Зачем нужна сортировка на интервью

На собеседованиях вас практически никогда не попросят реализовать алгоритм сортировки (Bubble Sort, Merge Sort, Quick Sort). Но вам наверняка придется использовать встроенные функции сортировки для решения задач.

Что важно знать:

  • Эффективная сортировка работает за O(n log n) времени
  • Сортировка требует O(1) или O(n) дополнительной памяти (зависит от реализации)
  • После сортировки многие задачи становятся проще

Встроенные функции сортировки

Python

Базовая сортировка:

# sorted() - возвращает новый отсортированный список
arr = [3, 1, 4, 1, 5]
sorted_arr = sorted(arr)  # [1, 1, 3, 4, 5]
# arr остаётся [3, 1, 4, 1, 5]

# list.sort() - сортирует список на месте (in-place)
arr = [3, 1, 4, 1, 5]
arr.sort()  # arr теперь [1, 1, 3, 4, 5]

Сортировка с ключом (key):

Параметр key принимает функцию, которая применяется к каждому элементу перед сравнением. Сортировка сравнивает результаты вызова этой функции, а не сами элементы напрямую.

# По длине строки
words = ["banana", "pie", "Washington", "book"]
sorted_words = sorted(words, key=len)  # ["pie", "book", "banana", "Washington"]

# По второму элементу кортежа
pairs = [(1, 5), (3, 2), (2, 8)]
sorted_pairs = sorted(pairs, key=lambda x: x[1])  # [(3, 2), (1, 5), (2, 8)]

# По модулю числа
nums = [-4, -2, 1, 3, -5]
sorted_nums = sorted(nums, key=abs)  # [1, -2, 3, -4, -5]

# По нескольким критериям (сначала по длине, потом лексикографически)
words = ["apple", "pie", "banana", "pear"]
sorted_words = sorted(words, key=lambda x: (len(x), x))
# ["pie", "pear", "apple", "banana"]

Обратная сортировка:

arr = [3, 1, 4, 1, 5]
sorted_arr = sorted(arr, reverse=True)  # [5, 4, 3, 1, 1]

Сортировка символов в строке:

s = "algorithm"
sorted_s = ''.join(sorted(s))  # "aghilmort"

Java

Массивы:

// Сортировка массива примитивов
int[] arr = {3, 1, 4, 1, 5};
Arrays.sort(arr);  // [1, 1, 3, 4, 5]

// Сортировка части массива (от индекса 1 до 4, не включая 4)
Arrays.sort(arr, 1, 4);

// Сортировка массива объектов (String)
String[] words = {"banana", "pie", "Washington", "book"};
Arrays.sort(words);  // ["Washington", "banana", "book", "pie"]

Коллекции:

// Сортировка списка
List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5));
Collections.sort(list);  // [1, 1, 3, 4, 5]

// Обратная сортировка
Collections.sort(list, Collections.reverseOrder());  // [5, 4, 3, 1, 1]

Сортировка с компаратором (Comparator):

// По длине строки
List<String> words = Arrays.asList("banana", "pie", "Washington", "book");
words.sort(Comparator.comparingInt(String::length));
// ["pie", "book", "banana", "Washington"]

// По второму элементу массива
List<int[]> pairs = Arrays.asList(new int[]{1, 5}, new int[]{3, 2}, new int[]{2, 8});
pairs.sort(Comparator.comparingInt(a -> a[1]));
// [[3, 2], [1, 5], [2, 8]]

// По нескольким критериям
words.sort(Comparator.comparingInt(String::length)
                     .thenComparing(String::compareTo));
// Сначала по длине, потом лексикографически

// Пользовательский компаратор (сортировка строк по длине)
List<String> words = Arrays.asList("banana", "pie", "Washington", "book");
words.sort((a, b) -> {
    // Возвращает отрицательное, если a короче b
    // Возвращает 0, если a и b одинаковой длины
    // Возвращает положительное, если a длиннее b
    return a.length() - b.length();
});
// Результат: ["pie", "book", "banana", "Washington"]

Go

Базовая сортировка:

// Сортировка слайса целых чисел
arr := []int{3, 1, 4, 1, 5}
sort.Ints(arr)  // [1, 1, 3, 4, 5]

// Сортировка строк
words := []string{"banana", "pie", "Washington", "book"}
sort.Strings(words)  // ["Washington", "banana", "book", "pie"]

// Сортировка float64
nums := []float64{3.14, 1.41, 2.71}
sort.Float64s(nums)  // [1.41, 2.71, 3.14]

Проверка, отсортирован ли слайс:

arr := []int{1, 2, 3, 4, 5}
isSorted := sort.IntsAreSorted(arr)  // true

Сортировка с пользовательской функцией:

// По длине строки
words := []string{"banana", "pie", "Washington", "book"}
sort.Slice(words, func(i, j int) bool {
    return len(words[i]) < len(words[j])
})
// ["pie", "book", "banana", "Washington"]

// По второму элементу структуры
type Pair struct {
    first, second int
}
pairs := []Pair{{1, 5}, {3, 2}, {2, 8}}
sort.Slice(pairs, func(i, j int) bool {
    return pairs[i].second < pairs[j].second
})
// [{{3 2} {1 5} {2 8}}]

// Обратная сортировка
sort.Slice(arr, func(i, j int) bool {
    return arr[i] > arr[j]
})

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

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

Квадратичные сортировки (O(n²))

Эти алгоритмы просты для понимания, но неэффективны для больших массивов. Их полезно знать для общего развития, но на практике используются редко.

Bubble Sort (Пузырьковая сортировка)

Идея: многократно проходим по массиву, сравнивая соседние элементы и меняя их местами, если они стоят в неправильном порядке. Большие элементы «всплывают» в конец массива, как пузырьки.

Как работает:

Шаг 1: [5, 2, 8, 1, 9]
       [2, 5, 8, 1, 9]  # сравнили 5 и 2, поменяли
       [2, 5, 8, 1, 9]  # 5 и 8 в порядке
       [2, 5, 1, 8, 9]  # сравнили 8 и 1, поменяли
       [2, 5, 1, 8, 9]  # 8 и 9 в порядке

Шаг 2: [2, 5, 1, 8, 9]
       [2, 5, 1, 8, 9]  # 2 и 5 в порядке
       [2, 1, 5, 8, 9]  # сравнили 5 и 1, поменяли
       [2, 1, 5, 8, 9]  # 5 и 8 в порядке

Шаг 3: [2, 1, 5, 8, 9]
       [1, 2, 5, 8, 9]  # сравнили 2 и 1, поменяли
       [1, 2, 5, 8, 9]  # остальные уже в порядке

Шаг 4: [1, 2, 5, 8, 9]  # готово, массив отсортирован

Алгоритм:

  1. Проходим по массиву n раз (внешний цикл)
  2. На каждой итерации внешнего цикла:
    • Проходим по неотсортированной части массива (внутренний цикл)
    • Сравниваем каждую пару соседних элементов
    • Если элементы стоят в неправильном порядке — меняем их местами
    • Используем флаг swapped: если за проход не было обменов — массив отсортирован, выходим досрочно (это опциональная оптимизация)
  3. После каждой итерации внешнего цикла самый большой элемент «всплывает» в конец
  4. Последние i элементов уже отсортированы, поэтому внутренний цикл сокращается

Сложность:

  • Временная: O(n²) в худшем и среднем случае, O(n) в лучшем (когда массив уже отсортирован)
  • Пространственная: O(1) — сортировка in-place

Когда использовать: практически никогда на интервью. Знать для общего понимания алгоритмов сортировки.

Selection Sort (Сортировка выбором)

Идея: на каждой итерации находим минимальный элемент в неотсортированной части массива и ставим его в конец отсортированной части.

Как работает:

[5, 2, 8, 1, 9]
 ^  ^  ^  ^  ^  ищем минимум (1), меняем с первым
[1, 2, 8, 5, 9]
    ^  ^  ^  ^  ищем минимум (2), уже на месте
[1, 2, 8, 5, 9]
       ^  ^  ^  ищем минимум (5), меняем с третьим
[1, 2, 5, 8, 9]
          ^  ^  ищем минимум (8), уже на месте
[1, 2, 5, 8, 9]  готово

Алгоритм:

  1. Массив условно делится на две части: отсортированную (слева) и неотсортированную (справа)
  2. Проходим по массиву n-1 раз (внешний цикл):
    • Изначально отсортированная часть пуста, неотсортированная — весь массив
  3. На каждой итерации внешнего цикла:
    • Находим минимальный элемент в неотсортированной части (внутренний цикл)
    • Меняем его местами с первым элементом неотсортированной части
    • Граница между отсортированной и неотсортированной частью сдвигается вправо
  4. После n-1 итераций весь массив отсортирован

Сложность:

  • Временная: O(n²) во всех случаях (всегда проходим по всему массиву)
  • Пространственная: O(1) — сортировка in-place

Отличие от bubble sort: Selection sort делает меньше обменов (максимум n-1), но всегда проходит весь массив. Bubble sort может остановиться раньше, если массив уже отсортирован.

Когда использовать: редко. Может быть полезна, если операция обмена очень дорогая.

Insertion Sort (Сортировка вставками)

Идея: строим отсортированную часть массива постепенно, вставляя каждый следующий элемент на правильное место. Похоже на то, как вы сортируете карты в руке.

Как работает:

[5, 2, 8, 1, 9]
[5] [2, 8, 1, 9]  # 5 уже «отсортирована»
    ^
[2, 5] [8, 1, 9]  # вставили 2 перед 5
       ^
[2, 5, 8] [1, 9]  # вставили 8 после 5
          ^
[1, 2, 5, 8] [9]  # вставили 1 в начало
             ^
[1, 2, 5, 8, 9]   # вставили 9 в конец

Алгоритм:

  1. Массив условно делится на две части: отсортированную (слева) и неотсортированную (справа)
  2. Изначально первый элемент считается отсортированным, остальные — неотсортированными
  3. Проходим по неотсортированной части (начиная со второго элемента):
    • Берем текущий элемент (ключ) из неотсортированной части
    • Сравниваем его с элементами отсортированной части справа налево
    • Сдвигаем элементы отсортированной части вправо, пока не найдем правильное место для ключа
    • Вставляем ключ на найденное место
  4. После обработки всех элементов массив полностью отсортирован

Сложность:

  • Временная: O(n²) в худшем случае, O(n) в лучшем (почти отсортированный массив)
  • Пространственная: O(1) — сортировка in-place

Когда эффективна:

  • Массив почти отсортирован
  • Массив маленький (до 10-20 элементов)
  • Добавление новых элементов в уже отсортированный массив

Применение: Insertion sort используется в Timsort (гибридный алгоритм в Python) для маленьких подмассивов.

Эффективные сортировки (O(n log n) и лучше)

Эти алгоритмы используются на практике и лежат в основе встроенных функций сортировки в большинстве языков программирования.

Merge Sort (Сортировка слиянием)

Идея: разделяем массив на две половины, рекурсивно сортируем каждую половину, затем сливаем два отсортированных массива в один.

Примечание: Merge Sort — это классический пример подхода Divide and Conquer («Разделяй и властвуй»): задача делится на подзадачи, каждая решается рекурсивно, а результаты объединяются на шаге слияния.

Как работает:

[5, 2, 8, 1, 9]
       |
   [5, 2]  [8, 1, 9]      # делим пополам
    |         |
 [5] [2]   [8] [1, 9]     # продолжаем делить
              |
           [8] [1] [9]    # дошли до одного элемента
              |
           [8] [1, 9]     # сливаем [1] и [9]
    |         |
 [2, 5]   [1, 8, 9]       # сливаем половины
       |
[1, 2, 5, 8, 9]           # финальное слияние

Сложность:

  • Временная: O(n log n) во всех случаях
  • Пространственная: O(n) — требуется дополнительная память для временных массивов

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

  • Стабильная сортировка (сохраняет порядок равных элементов — подробнее ниже)
  • Гарантированная O(n log n) сложность
  • Подходит для внешней сортировки (когда данные не помещаются в памяти)

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

Quick Sort (Быстрая сортировка)

Идея: выбираем опорный элемент (pivot), переставляем массив так, чтобы все элементы меньше pivot были слева, а все больше — справа. Затем рекурсивно сортируем левую и правую части.

Примечание: Quick Sort также использует подход Divide and Conquer («Разделяй и властвуй»), но с несколько изменённым подходом. В отличие от Merge Sort, где вся работа происходит на этапе слияния (combine), в Quick Sort основная работа выполняется на этапе разделения (divide) через операцию partition, а этап combine фактически отсутствует — элементы уже на своих местах.

Как работает:

[5, 2, 8, 1, 9]  выбираем pivot = 5
 ^
[2, 1, 5, 8, 9]  элементы < 5 слева, >= 5 справа
       ^
[1, 2] 5 [8, 9]  рекурсивно сортируем части
   ^       ^
[1, 2, 5, 8, 9]  готово

Реализация:

Python

def quick_sort(arr):
    # Базовый случай
    if len(arr) <= 1:
        return arr

    # Выбираем pivot (обычно средний элемент)
    pivot = arr[len(arr) // 2]

    # Разделяем на три части: меньше, равно, больше pivot
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    # Рекурсивно сортируем и объединяем
    return quick_sort(left) + middle + quick_sort(right)

# Версия in-place (более эффективная по памяти)
def quick_sort_inplace(arr, low, high):
    if low < high:
        # Находим позицию pivot после разделения
        pi = partition(arr, low, high)

        # Рекурсивно сортируем части
        quick_sort_inplace(arr, low, pi - 1)
        quick_sort_inplace(arr, pi + 1, high)

def partition(arr, low, high):
    pivot = arr[high]  # Берём последний элемент как pivot
    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

Java

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        // Рекурсивно сортируем части
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

private static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            // Меняем местами
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // Ставим pivot на правильное место
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;
}

Go

func quickSort(arr []int, low, high int) {
    if low < high {
        pi := partition(arr, low, high)

        // Рекурсивно сортируем части
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
    }
}

func partition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low - 1

    for 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
}

Выбор pivot элемента:

  • Первый/последний элемент — простой, но плох для почти отсортированных массивов (O(n²))
  • Средний элемент — хороший баланс
  • Случайный элемент — защита от худшего случая
  • Медиана из трёх — выбираем медиану из первого, среднего и последнего элемента

Сложность:

  • Временная: O(n log n) в среднем случае, O(n²) в худшем (когда pivot всегда минимум/максимум)
  • Пространственная: O(log n) для стека рекурсии

Почему называется «быстрой»:

  • На практике работает быстрее merge sort из-за меньшего количества операций
  • Хорошая кэш-локальность (работает с соседними элементами)
  • Сортировка in-place (не требует дополнительной памяти для данных)

Применение: стандартная сортировка в большинстве библиотек (с оптимизациями для предотвращения худшего случая).

Оптимизированные и специализированные сортировки

Counting Sort (Сортировка подсчётом)

Ключевая идея: подсчитываем частоту каждого значения, затем восстанавливаем отсортированный массив.

Пример:

Массив: [4, 2, 2, 8, 3, 3, 1]

Подсчитываем частоты:
count[1]=1, count[2]=2, count[3]=2, count[4]=1, count[8]=1

Восстанавливаем: [1, 2, 2, 3, 3, 4, 8]

Сложность: O(n + k), где k — диапазон значений

Когда применима:

  • Ограниченный диапазон значений (например, 0-100, возраст 0-120)
  • Целые числа
  • Пример: Sort Colors (LeetCode 75) — сортировка массива из 0, 1, 2

Когда НЕ использовать:

  • Большой диапазон значений при малом количестве элементов
  • Нецелые числа

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

Timsort

Ключевая идея: гибридный алгоритм, который комбинирует Merge Sort и Insertion Sort, используя преимущества обоих.

Как работает:

  • Делит массив на небольшие блоки (runs)
  • Сортирует маленькие блоки через Insertion Sort (быстро для малых данных)
  • Объединяет блоки через Merge Sort

Сложность: O(n log n) в среднем и худшем случае, O(n) в лучшем (почти отсортированные данные)

Применение:

  • Стандартная сортировка в Python (sorted(), .sort())
  • Стандартная сортировка объектов в Java (Arrays.sort() для объектов)

Почему эффективен: оптимизирован для реальных данных, которые часто частично отсортированы.

На собеседованиях не нужно знать детали реализации Timsort — достаточно понимать, что это гибридный алгоритм с O(n log n) и что он используется в Python/Java.

Dual-Pivot Quicksort

Ключевая идея: модификация Quick Sort, которая использует два опорных элемента (pivot) вместо одного.

Как работает:

  • Выбирает два опорных элемента: меньший и больший
  • Делит массив на три части: элементы < меньшего pivot, элементы между pivots, элементы > большего pivot
  • Рекурсивно сортирует каждую часть

Сложность: O(n log n) в среднем случае, O(n²) в худшем (как обычный Quick Sort)

Применение: cтандартная сортировка примитивов в Java (Arrays.sort() для int, double, и т.д.)

Почему эффективен: на практике работает быстрее классического Quick Sort благодаря меньшему количеству сравнений и лучшей кэш-локальности.

На собеседованиях не нужно знать детали реализации Dual-Pivot Quicksort — достаточно понимать, что это оптимизированная версия Quick Sort, используемая в Java для примитивов.

Стабильная vs нестабильная сортировка

Стабильная сортировка сохраняет относительный порядок равных элементов.

Пример:

Исходный массив: [(3, "a"), (1, "b"), (3, "c"), (2, "d")]
Сортируем по первому элементу:

Стабильная:   [(1, "b"), (2, "d"), (3, "a"), (3, "c")]  # (3,"a") перед (3,"c")
Нестабильная: [(1, "b"), (2, "d"), (3, "c"), (3, "a")]  # порядок может измениться

Когда важна стабильность:

  • Сортировка по нескольким критериям последовательно
  • Сохранение порядка при равных значениях важно для логики

Пример использования стабильности:

# Сортируем людей сначала по возрасту, потом по имени
people = [("Alice", 30), ("Bob", 25), ("Charlie", 30), ("David", 25)]

# Сначала сортируем по имени
people.sort(key=lambda x: x[0])
# [("Alice", 30), ("Bob", 25), ("Charlie", 30), ("David", 25)]

# Потом сортируем по возрасту (стабильная сортировка сохранит порядок имен!)
people.sort(key=lambda x: x[1])
# [("Bob", 25), ("David", 25), ("Alice", 30), ("Charlie", 30)]
# Bob перед David, Alice перед Charlie - порядок имен сохранился

Встроенные сортировки:

  • Python: стабильная (Timsort)
  • Java: стабильная для объектов (Timsort), нестабильная для примитивов (Dual-Pivot Quicksort)
  • Go: нестабильная (quicksort с оптимизациями) — используйте sort.SliceStable() для стабильной сортировки

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

Алгоритм Лучший случай Средний случай Худший случай Память Стабильная
Bubble Sort O(n) O(n²) O(n²) O(1) Да
Selection Sort O(n²) O(n²) O(n²) O(1) Нет
Insertion Sort O(n) O(n²) O(n²) O(1) Да
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) Нет
Counting Sort O(n + k) O(n + k) O(n + k) O(k) Да
Timsort O(n) O(n log n) O(n log n) O(n) Да
Dual-Pivot Quicksort O(n log n) O(n log n) O(n²) O(log n) Нет

Частые задачи на сортировку

Классические задачи, где сортировка необходима или является одним из стандартных решений:

1. Поиск нескольких чисел с заданной суммой (3Sum, 4Sum)

Ключевая идея: сортировка + two pointers (два указателя)

Задача: дан массив целых чисел. Найти все уникальные тройки чисел, которые в сумме дают 0.

Пример:

  • Вход: [-1, 0, 1, 2, -1, -4]
  • Выход: [[-1, -1, 2], [-1, 0, 1]]

Алгоритм:

  1. Сортируем массив по возрастанию
  2. Перебираем массив, фиксируя первый элемент тройки (индекс i)
  3. Для каждого фиксированного элемента:
    • Ставим два указателя: left на элемент после i, right на конец массива
    • Вычисляем сумму трёх элементов: nums[i] + nums[left] + nums[right]
    • Если сумма равна 0: добавляем тройку в результат, сдвигаем оба указателя
    • Если сумма меньше 0: сдвигаем left вправо (увеличиваем сумму)
    • Если сумма больше 0: сдвигаем right влево (уменьшаем сумму)
  4. Важно: пропускаем дубликаты на всех уровнях (для i, left и right)

Сложность: O(n²) времени, O(1) памяти (не считая результата)

Примечание: все задачи типа nSum (3Sum, 4Sum, и т.д.) решаются через сортировку + two pointers. Однако для задачи 2Sum рекомендуется использовать HashMap.

2. Слияние перекрывающихся интервалов (Merge Intervals)

Ключевая идея: сортировка по началу интервала, затем линейный проход

Задача: дан массив интервалов, где каждый интервал представлен как [start, end]. Объединить все перекрывающиеся интервалы и вернуть массив неперекрывающихся интервалов.

Пример:

  • Вход: [[1, 3], [2, 6], [8, 10], [15, 18]]
  • Выход: [[1, 6], [8, 10], [15, 18]]

Алгоритм: ключевая идея — сортируем интервалы по началу, затем проходим линейно, объединяя перекрывающиеся интервалы.

Сложность: O(n log n) по времени (сортировка), O(n) по памяти

3. Группировка анаграмм (Group Anagrams)

Ключевая идея: сортировка символов каждого слова + HashMap для группировки

Задача: дан массив строк. Сгруппировать все анаграммы вместе. Анаграммы — это слова, состоящие из одинаковых букв в разном порядке.

Пример:

  • Вход: ["eat", "tea", "tan", "ate", "nat", "bat"]
  • Выход: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Решение: ключевая идея — сортируем символы каждого слова и используем отсортированную строку как ключ в HashMap. Все анаграммы после сортировки символов дают одинаковую строку ("eat", "tea", "ate" → "aet"), поэтому группируются вместе.

Сложность: O(n × k log k), где n — количество слов, k — средняя длина слова

Важно для интервью:

  • Three Sum и Merge Intervals — сортировка является стандартным и ожидаемым решением
  • Group Anagrams — сортировка это классический подход; если интервьюер спросит про оптимизацию, можно упомянуть альтернативу через подсчет частот символов (O(n × k) вместо O(n × k log k))

Когда НЕ нужно сортировать:

Python

# Two Sum с HashMap: O(n) - лучше, чем сортировка O(n log n)
def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

# Проверка на анаграмму с HashMap: O(n) - эффективнее сортировки
def is_anagram(s, t):
    if len(s) != len(t):
        return False
    count = {}
    for char in s:
        count[char] = count.get(char, 0) + 1
    for char in t:
        if char not in count or count[char] == 0:
            return False
        count[char] -= 1
    return True

# Можно и через сортировку, но это O(n log n):
def is_anagram_sorting(s, t):
    return sorted(s) == sorted(t)  # Проще, но медленнее

# Поиск дубликатов с HashSet: O(n) - эффективнее сортировки
def find_duplicates(arr):
    seen = set()
    duplicates = []
    for num in arr:
        if num in seen:
            duplicates.append(num)
        else:
            seen.add(num)
    return duplicates

# То же самое можно сделать с сортировкой, но это O(n log n):
def find_duplicates_sorting(arr):
    arr.sort()  # O(n log n)
    duplicates = []
    for i in range(1, len(arr)):
        if arr[i] == arr[i-1]:
            duplicates.append(arr[i])
    return duplicates
# Вывод: если можно за O(n) с HashMap — не сортируйте!

# Проверка отсортированности массива: O(n)
def is_sorted(arr):
    for i in range(1, len(arr)):
        if arr[i] < arr[i-1]:
            return False
    return True

# Можно и через сортировку, но это O(n log n):
def is_sorted_with_sorting(arr):
    return sorted(arr) == arr  # Проще, но медленнее

Java

// Two Sum с HashMap: O(n) - лучше, чем сортировка O(n log n)
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (seen.containsKey(complement)) {
            return new int[]{seen.get(complement), i};
        }
        seen.put(nums[i], i);
    }
    return new int[]{};
}

// Проверка на анаграмму с HashMap: O(n) - эффективнее сортировки
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    Map<Character, Integer> count = new HashMap<>();
    for (char c : s.toCharArray()) {
        count.put(c, count.getOrDefault(c, 0) + 1);
    }
    for (char c : t.toCharArray()) {
        if (!count.containsKey(c) || count.get(c) == 0) {
            return false;
        }
        count.put(c, count.get(c) - 1);
    }
    return true;
}

// Можно и через сортировку, но это O(n log n):
public boolean isAnagramSorting(String s, String t) {
    char[] sChars = s.toCharArray();
    char[] tChars = t.toCharArray();
    Arrays.sort(sChars);
    Arrays.sort(tChars);
    return Arrays.equals(sChars, tChars);  // Проще, но медленнее
}

// Поиск дубликатов с HashSet: O(n) - эффективнее сортировки
public List<Integer> findDuplicates(int[] arr) {
    Set<Integer> seen = new HashSet<>();
    List<Integer> duplicates = new ArrayList<>();
    for (int num : arr) {
        if (seen.contains(num)) {
            duplicates.add(num);
        } else {
            seen.add(num);
        }
    }
    return duplicates;
}

// То же самое можно сделать с сортировкой, но это O(n log n):
public List<Integer> findDuplicatesSorting(int[] arr) {
    Arrays.sort(arr);  // O(n log n)
    List<Integer> duplicates = new ArrayList<>();
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] == arr[i-1]) {
            duplicates.add(arr[i]);
        }
    }
    return duplicates;
}
// Вывод: если можно за O(n) с HashMap — не сортируйте!

// Проверка отсортированности массива: O(n)
public boolean isSorted(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < arr[i-1]) {
            return false;
        }
    }
    return true;
}

// Можно и через сортировку, но это O(n log n):
public boolean isSortedWithSorting(int[] arr) {
    int[] sorted = arr.clone();
    Arrays.sort(sorted);
    return Arrays.equals(arr, sorted);  // Проще, но медленнее
}

Go

// Two Sum с HashMap: O(n) - лучше, чем сортировка O(n log n)
func twoSum(nums []int, target int) []int {
    seen := make(map[int]int)
    for i, num := range nums {
        complement := target - num
        if j, found := seen[complement]; found {
            return []int{j, i}
        }
        seen[num] = i
    }
    return []int{}
}

// Проверка на анаграмму с HashMap: O(n) - эффективнее сортировки
func isAnagram(s, t string) bool {
    if len(s) != len(t) {
        return false
    }
    count := make(map[rune]int)
    for _, char := range s {
        count[char]++
    }
    for _, char := range t {
        count[char]--
        if count[char] < 0 {
            return false
        }
    }
    return true
}

// Можно и через сортировку, но это O(n log n):
func isAnagramSorting(s, t string) bool {
    sRunes := []rune(s)
    tRunes := []rune(t)
    sort.Slice(sRunes, func(i, j int) bool { return sRunes[i] < sRunes[j] })
    sort.Slice(tRunes, func(i, j int) bool { return tRunes[i] < tRunes[j] })
    return string(sRunes) == string(tRunes)  // Проще, но медленнее
}

// Поиск дубликатов с HashSet: O(n) - эффективнее сортировки
func findDuplicates(arr []int) []int {
    seen := make(map[int]bool)
    duplicates := []int{}
    for _, num := range arr {
        if seen[num] {
            duplicates = append(duplicates, num)
        } else {
            seen[num] = true
        }
    }
    return duplicates
}

// То же самое можно сделать с сортировкой, но это O(n log n):
func findDuplicatesSorting(arr []int) []int {
    arrCopy := make([]int, len(arr))
    copy(arrCopy, arr)
    sort.Ints(arrCopy)  // O(n log n)
    duplicates := []int{}
    for i := 1; i < len(arrCopy); i++ {
        if arrCopy[i] == arrCopy[i-1] {
            duplicates = append(duplicates, arrCopy[i])
        }
    }
    return duplicates
}
// Вывод: если можно за O(n) с HashMap — не сортируйте!

// Проверка отсортированности массива: O(n)
func isSorted(arr []int) bool {
    for i := 1; i < len(arr); i++ {
        if arr[i] < arr[i-1] {
            return false
        }
    }
    return true
}

// Можно и через сортировку, но это O(n log n):
func isSortedWithSorting(arr []int) bool {
    arrCopy := make([]int, len(arr))
    copy(arrCopy, arr)
    sort.Ints(arrCopy)
    for i := range arr {
        if arr[i] != arrCopy[i] {
            return false
        }
    }
    return true  // Проще, но медленнее
}

Правило: сортируйте, только если это действительно упрощает задачу или требуется по условию.

Заключение

Что мы изучили

В этой статье мы изучили:

  1. Встроенные функции сортировки:

    • Python: sorted(), list.sort() с параметром key
    • Java: Arrays.sort(), Collections.sort() с Comparator
    • Go: sort.Slice(), sort.Sort() с пользовательскими функциями

  2. Квадратичные сортировки O(n²):

    • Bubble Sort, Selection Sort, Insertion Sort
    • Просты в реализации, но медленны для больших данных

  3. Эффективные сортировки O(n log n):

    • Merge Sort: стабильная, гарантированная O(n log n), требует O(n) памяти
    • Quick Sort: быстрая на практике, in-place, в среднем O(n log n)

  4. Оптимизированные сортировки:

    • Counting Sort: O(n + k) для ограниченного диапазона
    • Timsort и Dual-Pivot Quicksort: гибридные алгоритмы в Python и Java

  5. Когда использовать сортировку:

    • Задачи на два указателя, интервалы, поиск дубликатов
    • Бинарный поиск требует отсортированный массив

Что важно знать

Обязательно:

  • Уметь использовать встроенную сортировку языка
  • Знать, как сортировать с кастомным компаратором (по нескольким критериям)
  • Понимать, что эффективная сортировка работает за O(n log n)
  • Знать Merge Sort и Quick Sort как примеры Divide and Conquer
  • Распознавать задачи, где сортировка упрощает решение

Хорошо знать (но не критично):

  • Insertion Sort для малых массивов
  • Counting Sort для специальных случаев
  • Различие между стабильной и нестабильной сортировкой
  • Timsort и Dual-Pivot Quicksort (что используется в вашем языке)

Не обязательно:

  • Реализация Bubble Sort и Selection Sort (учебные алгоритмы)
  • Математические доказательства корректности
  • Все возможные оптимизации Quick Sort

Практические рекомендации

На собеседовании:

  • «Отсортируйте массив» — используйте встроенную функцию
  • «Реализуйте сортировку» — спросите про требования (стабильность, память, размер данных)
  • «Как бы вы отсортировали это?» — обсудите трейд-оффы (компромиссы по времени, памяти и стабильности)
  • Умейте объяснить, почему выбрали конкретный алгоритм

Частые задачи с сортировкой:

  • Сортировка с кастомным компаратором (по нескольким критериям)
  • Задачи на интервалы (сортировка + жадный алгоритм)
  • Поиск k-го элемента
  • Группировка и агрегация данных

Что делать дальше

  • Решите несколько задач на сортировку с кастомным компаратором (по нескольким критериям)
  • Реализуйте Merge Sort самостоятельно для полного понимания Divide and Conquer
  • Тренируйтесь распознавать задачи, где помогает предварительная сортировка