re:re:actable
Урок 023 минуты чтения

Какие сортировки нужно знать?

На этой странице
Кратко

Для собеседований важно понимать bubble/selection/insertion sort как учебные O(n^2) алгоритмы, merge sort как стабильный divide and conquer, quick sort как быстрый average-case алгоритм и особенности Array.prototype.sort() в JavaScript.

Вопрос

Какие алгоритмы сортировки нужно знать и чем они отличаются по сложности и стабильности?

Таблица

АлгоритмAverageWorstПамятьЧто помнить
Bubble sortO(n^2)O(n^2)O(1)учебный
Selection sortO(n^2)O(n^2)O(1)ищет минимум
Insertion sortO(n^2)O(n^2)O(1)хорош на почти sorted
Merge sortO(n log n)O(n log n)O(n)stable, divide and conquer
Quick sortO(n log n)O(n^2)O(log n) averageзависит от pivot

Что значат столбцы таблицы

Stable (стабильная) сортировка не меняет порядок элементов с одинаковым ключом. Пример - сортируем пользователей по возрасту:

до:            Аня 25, Борис 30, Вера 25
стабильно:     Аня 25, Вера 25, Борис 30   (Аня осталась раньше Веры)
нестабильно:   Вера 25, Аня 25, Борис 30   (тоже отсортировано, но порядок равных сломан)

Это важно, когда сортируют в несколько проходов: сначала по имени, потом по возрасту - и ждут, что внутри одного возраста имена останутся по алфавиту. Array.prototype.sort в JavaScript стабилен начиная с ES2019.

In-place - сортировка меняет исходный массив и почти не использует дополнительную память (O(1) или O(log n) на рекурсию). Merge sort в обычной реализации не in-place: ему нужен временный массив O(n).

Память в таблице - дополнительная память помимо самого массива.

Что реально нужно уметь писать?

Минимальный набор:

  • binary search;
  • merge sort;
  • quick sort;
  • insertion sort;
  • JS comparator для sort.

Bubble sort обычно нужен только для объяснения идеи.

Зачем знать сортировки, если есть sort?

На практике в JS чаще используют:

nums.sort((a, b) => a - b)

Но на интервью проверяют:

  • понимание сложности;
  • divide and conquer;
  • mutation;
  • comparator;
  • стабильность;
  • edge cases.

Что отвечать на собеседовании?

Нужно знать простые O(n^2) сортировки для понимания, merge sort как стабильный O(n log n) алгоритм с дополнительной памятью, quick sort как быстрый average-case алгоритм с worst case O(n^2), а также особенности JS sort: он мутирует массив и без comparator сортирует как строки.

Что важно помнить: частые ошибки

  • Сортировать числа через nums.sort() без comparator.
  • Говорить, что quick sort всегда O(n log n).
  • Забывать память merge sort.
  • Не знать, что JS sort мутирует массив.
  • Не понимать stable sort.

Мини-шпаргалка

  • Простые сортировки - O(n^2).
  • Merge sort - O(n log n), memory O(n).
  • Quick sort - average O(n log n), worst O(n^2).
  • JS sort мутирует.
  • Numeric comparator: (a, b) => a - b.
  • toSorted возвращает новый массив.

Документация

Wikipedia: Sorting algorithm, VisuAlgo: Sorting.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам