Объясняем известные алгоритмы сортировки на пальцах
В этой серии видео с YouTube предлагаем разобрать самые известные алгоритмы сортировки простыми словами так, чтобы стало понятно даже восьмилетнему.
Итак, самые известные алгоритмы сортировки:
Сортировка пузырьком / Bubble Sort
Один из самых известных алгоритмов сортировки, реализовать который часто просят на технических собеседованиях. В этом алгоритме массив перебирается раз за разом, и каждое следующее значение сравнивается с предыдущим. После первого прохода по массиву самое большое число окажется в конце, а когда первый элемент будет не с чем сравнить, массив будет отсортирован по возрастанию.
Сортировка вставками / Insertion Sort
При сортировке вставками, массив перебирается последовательно. Каждый следующий рассматриваемый элемент размещается так, чтобы оказаться между ближайшим минимальным элементом и ближайшим максимальным.
Сортировка выбором / Selection Sort
Основная мысль этого метода заключается в том, чтобы создать отсортированную последовательность, присоединяя к ней один элемент за другим в правильном порядке.
Алгоритм сортировки выбором состоит из нескольких последовательных шагов. На каждом шаге сортировки текущий элемент массива меняется местами с элементом с наименьшим значением. Таким образом, получается массив значений, отсортированный по возрастанию.
Сортировка слиянием / Merge Sort
Алгоритм сортировки слиянием помогает эффективно упорядочивать списки. Основная задача разбивается на подзадачи меньшего размера, каждая из которых решается отдельно. Затем их решения комбинируются, а результатом их слияния будет решение основной задачи.
Быстрая сортировка / Quick Sort
Один из известных и быстрых алгоритмов сортировки, разработанный в МГУ английским информатиком Чарльзом Хоаром. Его часто называет quicksort или просто qsort – по названию стандартной библиотеки языка C. Является существенно переработанной версией пузырьковой сортировки.
В этой подборке мы рассмотрели одни из наиболее часто используемых алгоритмов сортировки, и если вы готовитесь к собеседованию, этого будет недостаточно. Попробуйте разобраться с вопросами по алгоритмам (и не только) в нашей статье об алгоритмической подготовке к техническому собеседованию.