Сортировки в гифках: 8 самых популярных алгоритмов

3
21828

Краткий гайд пригодится новичкам, расскажет о видах и способах сортировки. Для лучшего усвоения и наглядности процесса каждый вид сопровождается 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 сортировка происходит по старшему разряду.




3 Комментарии