Хорошо. Плохой заголовок. Я попытался найти гифку, на которой Эл Гор танцует, и пришел к выводу, что он не танцует.

Многие из нас проводят день и, не задумываясь, сортируют всякие вещи. Ты заметил свою пижаму в ванной? Положите его обратно в ящик, где он принадлежит. Цветные карандаши не в правильном порядке, чтобы отобразить красивую радугу? Работайте над этим и сделайте свою жизнь счастливее. Деньги в кошельке испортились после бурной ночи? Бороться с похмельем и устроить его. M&M в куче кеглей? Это преступление.

Дело в том, что нам, людям, легко разобраться во всем, потому что это естественно. Мы не думаем об этом слишком долго. Когда вы в последний раз смотрели на один носок и не могли понять, у какого несчастливого носка не было S.O.? Плохой пример — слишком много одиночных носков, но вы поняли. Давайте поговорим о компьютерах. Что делает компьютер?

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

Простые сортировки

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

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

Эффективные сортировки

Сортировка слиянием — это алгоритм типа "разделяй и властвуй". Он берет массив и делит длину массива на два. Затем он берет массивы и снова разбивает каждый из них на два. Это продолжается до тех пор, пока в каждом массиве не останется хотя бы один элемент. После этого он начинает объединять массивы по два за раз, сортируя их. Он заканчивается, когда есть один массив, содержащий исходное количество элементов в первом массиве. Этот алгоритм сортировки можно масштабировать до больших списков, но вы видите, насколько он может быть неэффективным, когда некоторые элементы в массиве уже отсортированы.

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

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

Пузырьковая сортировка и варианты

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

Сортировка гребешком похожа на пузырьковую сортировку, но немного более эффективна. Принцип работы этого алгоритма заключается в наличии большого коэффициента зазора и уменьшении размера при каждом проходе массива. При пузырьковой сортировке сравниваемые элементы располагаются рядом друг с другом, поэтому коэффициент зазора равен 1. Напротив, при сортировке гребенкой мы начинаем с большего размера зазора и уменьшаем его с помощью коэффициента зазора. При каждом проходе массив будет сортироваться (последний проход — пузырьковая сортировка).

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