Coursera Learner working on a presentation with Coursera logo and
Coursera Learner working on a presentation with Coursera logo and

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

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

Основы работы сортировки вставкой

Ниже описаны три этапа, которые дадут вам представление о том, как работает сортировка вставкой:

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

Характеристики сортировки вставкой

Хотя этот алгоритм сортировки по месту имеет широкий спектр характеристик, есть три важных, с которыми должен ознакомиться каждый.

  1. Во-первых, алгоритм сортировки вставкой невероятно прост. Некоторые даже сказали бы, что он самый простой из всех существующих благодаря своей простой реализации.
  2. Если вы программист, который регулярно имеет дело с небольшими значениями данных, использование этого алгоритма будет весьма кстати.
  3. Природа алгоритма сортировки вставкой довольно адаптивна, что делает его идеальным для частично отсортированных наборов данных.

Общие вопросы, задаваемые о сортировке вставкой

Здесь приведен список кратких ответов на часто задаваемые вопросы об алгоритмах сортировки вставкой.

Что такое граничные случаи алгоритма сортировки вставкой?

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

Стабильны ли алгоритмы сортировки вставкой?

Алгоритмы сортировки вставкой невероятно стабильны, особенно если сравнивать их с другими алгоритмами.

Когда лучше всего использовать алгоритм сортировки вставкой?

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

Какого подхода придерживается сортировка вставкой?

Алгоритм сортировки вставкой использует инкрементный подход, поэтому он невероятно популярен среди программистов, сортирующих массивы.

Двоичная сортировка вставкой с пояснениями

Программисты могут использовать двоичный поиск для уменьшения количества сравнений, присутствующих в обычной сортировке вставкой. Сортировка с двоичной вставкой использует поиск для нахождения идеального места для вставки выбранного элемента на каждой итерации. Когда речь идет об обычной вставке, сортировка использует O(i) (на каждой итерации) при наихудшем сценарии.
Мы можем использовать бинарное исследование для уменьшения этого значения: O(logi). Однако, несмотря на это, время работы алгоритма в худшем случае составляет около O(n^2). Это связано с количеством обменов, необходимых для каждой вставки.

Шаги для реализации сортировки вставками в связанных списках

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

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

Основные применения сортировки вставкой

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

Временные сложности сортировки вставкой

Здесь рассматриваются временные сложности, с которыми вы можете столкнуться при сортировке вставкой.

Наихудшая сложность O (n2) – Worst Case Complexity O (n2)
Представьте, что имеется массив, расположенный в порядке возрастания, который необходимо отсортировать в порядке убывания. Подобный случай приводит к наихудшей сложности. В такой ситуации вам придется сравнивать каждый элемент с другими элементами, чтобы обеспечить (n-1) сравнений для каждого n-го элемента.

Общее количество сравнений будет равно n*(n-1) ~ n2.

Сложность среднего случая O(n) – Average Case Complexity O(n)
Этот тип сложности часто имеет место, когда элементы массива перемешаны, то есть они не расположены ни в порядке убывания, ни в порядке возрастания.

Пространственная сложность – Space Complexity
Пространственная сложность становится равной 0(1) всякий раз, когда происходит внедрение дополнительной переменной.

Сложность в лучшем случае – Best Case Complexity
Когда массив не требует сортировки, количество повторений внешнего цикла равно n. С другой стороны, внутренний цикл остается неактивным и не выполняет никаких операций. Это означает, что количество сравнений будет равно n, что приводит к линейной сложности.

Анализ временной сложности

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

Несортированный массив требует элемента для проведения сравнений с другими элементами, то есть каждый элемент из n сравнивается с другими n элементами. Также было бы полезно проанализировать другие подобные алгоритмы, такие как Quick Sort, Merge Sort или Selection Sort, и оценить их соответствующую сложность.