Объясняем известные алгоритмы сортировки на пальцах

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

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

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

Алгоритм сортировки выбором состоит из нескольких последовательных шагов. На каждом шаге сортировки текущий элемент массива меняется местами с элементом с наименьшим значением. Таким образом, получается массив значений, отсортированный по возрастанию.

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

Один из известных и быстрых алгоритмов сортировки, разработанный в МГУ английским информатиком Чарльзом Хоаром. Его часто называет quicksort или просто qsort – по названию стандартной библиотеки языка C. Является существенно переработанной версией пузырьковой сортировки.

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