Перевод простого гайда по алгоритмам сортировки, разобранным по винтикам и разложенным по полочкам!

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

Давайте начнем с азов. Что такое алгоритм? Мы собираемся многое о них узнать, так что должны для начала знать определение, правильно?

Алгоритм — это набор инструкций для машины, что и как ей делать. Другими словами, это руководство к вашему коду. И все. Наиболее часто используемым подмножеством множества алгоритмов являются алгоритмы сортировки, то есть инструкции, как программа или компьютер должны подойти к организации данных.

Зачем разбираться?

Важно четко понять, что есть сортировка, в частности, в терминах информатики, и какое значение она имеет.

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

Если вы читали об алгоритмах сортировки, то без труда заметите, что самыми простыми примерами могут послужить процессы упорядочивания карт, книг и тому подобного.

Сортировки исключительно полезны по двум причинам:

• с точки зрения человеческого восприятия, они делают набор данных намного более читаемым,
• они упрощают реализацию алгоритмов поиска и извлечения определенных значений из наборов данных

Вернувшись к моему примеру, попробуйте представить, как трудно было бы найти определенную страницу в перемешанной кипе из около 200 листов.

Реализация

Что ж, я смею надеяться, что теперь понятие сортировок вышло для читателя на бытовой уровень. Но как это реализуется в компьютерах? Они не жалуются на скорость выполнения операций, да и читаемость в человеческом понимании их волнует мало. Так чем же сортировки могут быть полезны машинам?

В этом случае сортировки также играют важную роль, поскольку данные, которые компьютер, программа или приложение должны обработать, могут быть очень большого объема. Причем это далеко не всегда ограничивается тем, что под термином «объемный» может представить себе человек.

Давайте конкретизируем, что именно мы понимаем под сортировкой с точки зрения информатики. Сортировка — это организация некоторого набора данных одного типа по какому-то принципу.

Здесь нужно выделить два основных момента:

• Можно упорядочить элементы по возрастанию или убыванию абсолютно любого признака, которым они обладают, будь то размер, алфавитный порядок, дата, время — что угодно!
• Можно сортировать только наборы однородных данных, или данных одного типа. Другими словами, мы не можем упорядочить массив, содержащий одновременно слова и числа, потому что нет признака, по которому их можно было бы сравнивать.

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

В данном примере мы имеем небольшой массив неупорядоченных чисел. Представьте, что нам нужно найти, например, число 33, не зная заранее, где оно расположено. Или вообразите более драматичный сценарий: нужно найти число, которого вообще нет в списке! В худшем случае мы бы перебрали каждый элемент до конца, и осознали бы, что искомого нет. Другими словами, эта операция заняла бы линейное время. Но что, если бы в массиве было 100 миллионов чисел? Или миллиард?

Не паникуйте (и держите при себе полотенце). Мы не собираемся сортировать 100 миллионов чисел, успокойтесь. Давайте посмотрим, как выглядит поиск числа в упорядоченном массиве:

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

Именно так компьютер использует сортировки. Бинарный поиск прекрасно справляется с задачами вставки, удаления, чтения и извлечения данных из массива, даже если в нем миллиард элементов.

Классификация алгоритмов

Теперь, когда мы разобрались с определением сортировки и поняли, зачем она нужна, самое время разложить по полочкам различные алгоритмы, которые используются чаще всего.

Давайте детально рассмотрим шесть основных критериев классификации алгоритмов сортировки.

• Временная сложность:
  как много времени занимает выполнение алгоритма относительно объема входных данных.
• Использование памяти:
  Размер дополнительной памяти, которая используется для упорядочивания исходных данных. Существует два типа алгоритмов:
  • In-place: операции производятся непосредственно в памяти, содержащей входные данные;
  • Out-of-place: для операций выделяется отдельный участок памяти.
• Устойчивость:
  Устойчивые алгоритмы подразумевают, что если в массиве есть одинаковые элементы, то после сортировки их порядок остается неизменным. Неустойчивые такого гарантировать не могут.
• Внутренние vs внешние сортировки
  При больших объемах входных данных машине может не хватить оперативной памяти, чтобы вместить их. В этом случае применяются алгоритмы внешней сортировки, при которых сортируемые данные хранятся в дополнительном участке памяти.
• Рекуррентные vs итерационные алгоритмы
  Рекуррентные алгоритмы разбивают входные данные на небольшие части, рекурсивно сортируют их и затем объединяют результат, получая единый упорядоченный массив.
• С компаратором vs без компаратора
  Наконец, возможно классифицировать алгоритмы на основе того, как они упорядочивают элементы.Любой алгоритм, который в процессе сортировки сравнивает два элемента называется сортировкой сравнением. Это подразумевает использование алгоритмом компаратора, чтобы определить, какой из пары элементов должен быть первым.Алгоритмы, не использующие компаратор, называются, соответственно, сортировками без сравнения.