Сортировки в гифках: 8 самых популярных алгоритмов
Краткий гайд пригодится новичкам, расскажет о видах и способах сортировки. Для лучшего усвоения и наглядности процесса каждый вид сопровождается gif-анимацией.
Если хочешь подтянуть свои знания, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:
- углубишься в решение практических задач;
- узнаешь все про сложные алгоритмы, сортировки, сжатие данных и многое другое.
Ты также будешь на связи с преподавателем и другими студентами.
В итоге будешь браться за сложные проекты и повысишь чек за свою работу 🙂
Bubble sort
Сортировка пузырьком или сортировка простыми обменами – один из простейших алгоритмов сортировки. Он применяется
для упорядочивания массивов небольших размеров.
Суть алгоритма в том, что совершается несколько проходов по массиву. При каждом проходе попарно сравниваются два соседних элемента. Если они находятся в верном порядке, то ничего не происходит, в противном случае они меняются местами. В результате первого прохода максимальный элемент окажется в конце, то есть всплывет словно пузырек. Затем все повторяется до того момента пока весь массив не будет отсортирован.
Quick sort
Быстрая сортировка - в целом это один из самых быстрых алгоритмов сортировки массивов, однако на практике он чаще всего применяется с разного рода модификациями. Является примером принципа «разделяй и властвуй».
Идея алгоритма заключается в том, что выбирается опорный элемент, относительно которого будет происходит сортировка. Равные и бОльшие элементы помещаются справа, меньшие – слева. Затем к полученным подмассивам рекурсивно применяются два первых пункта.
Random quick sort
Рандомная быстрая сортировка – то же самое, что и быстрая сортировка, лишь с тем отличием, что опорный элемент выбирается случайно.
Merge sort
Сортировка слиянием – алгоритм, который сортирует такие структуры данных, где доступ к элементам осуществляется последовательно. Эта сортировка происходит следующим образом:
массив разбивается на две примерно равные части, затем каждая из них сортируется. После этого два отсортированных подмассива сливаются в один. Для этого сравниваются два первых элемента в каждом из них и в зависимости от порядка сортировки ставятся в нужной последовательности. Если же один подмассив закончился, то оставшиеся элементы второго записываются после последнего элемента первого.
Selection sort
Сортировка выбором - здесь, чтобы отсортировать массив, находим элемент с минимальным значением, затем сравниваем его со значением первой неотсортированной позиции. Если этот элемент меньше, то он становится новым минимумом и их позиции меняются.
Insertion sort
Сортировка вставками- сортировка, в которой элементы просматриваются по одному и ставятся на место в соответствии с уже упорядоченным массивом.
Counting sort
Сортировка подсчетом – один из базовых алгоритмов, служит основой для многих сортировок, но сам используется только для ознакомления с темой. Его суть в том, чтобы подсчитать сколько раз число встречается в массиве, а затем заполнить массив этими числами в соответствии с количеством.
Radix sort
Поразрядная сортировка — сортировка по разрядам. Существует две разновидности: LSD (least significant digit) и MSD (least significant digit). В первом случае происходит сортировка элементов по младшим разрядам (все оканчивающиеся на 0, затем на 1 и так до 9). После этого они группируются по следующему с конца разряду, пока они не закончатся. В MSD сортировка происходит по старшему разряду.