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