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

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

Итак, самые известные алгоритмы сортировки:

Сортировка пузырьком / Bubble Sort

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

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

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

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

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

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

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

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

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

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

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