Как работает сортировка вставками

Сортировка простыми вставками :: Insertion sort

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

Сортировку вставками можно получить, если немного видоизменить гномью сортировку.

Алгоритм

В сортировке вставками последовательно обрабатываются отрезки массива, начиная с первого элемента и затем последовательно расширяя подмассив, вставляя на своё место очередной неотсортированный элемент.

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

Наилучший случай

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

Наихудший случай

Таковым является реверсно упорядоченный массив. Улучшенный вариант сортировки вставками — сортировка Шелла, обходит данную проблему.

Характеристики алгоритма

Название	Сортировка простыми вставками (Insertion sort)
Класс	Сортировки вставками
Устойчивость	Да
Сравнения	Да
Сложность по времени	Худшая	O(n 2 / 2)
	Средняя	O(n 2 / 4)
	Лучшая	O(n)
Сложность по памяти	Общая	O(n)
	Дополнительная	O(1)

Сортировка вставками

Еще одним алгоритмом, разработанным для упорядочивания массивов, является алгоритм Сортировка вставками (Insertion Sort) . Этот алгоритм (как и другие, рассматриваемые на нашем сайте) достаточно прост. Он состоит из двух циклов (один вложен в другой). Первый цикл производит проход по массиву, а второй – перемещение обрабатываемых элементов. Давайте сразу посмотрим, как может выглядеть код такой сортировки, а уже ниже разберем, как он работает.

Сортировка вставками C++
using namespace std ;
const int N = 10 ;
int buff = 0 ; // для хранения перемещаемого значения
int i , j ; // для циклов
/************* Начало сортировки *******************/
for ( i = 1 ; i < N ; i ++ ) buff = a [ i ] ; // запомним обрабатываемый элемент // и начнем перемещение элементов слева от него // пока запомненный не окажется меньше чем перемещаемый for ( j = i - 1 ; j >= 0 && a [ j ] > buff ; j — )
a [ j + 1 ] = a [ j ] ;
a [ j + 1 ] = buff ; // и поставим запомненный на его новое место
/************* Конец сортировки *******************/
for ( int i = 0 ; i < N ; i ++ ) // вывод отсортированного массива cout << a [ i ] << '\t' ; cout << endl ;

Алгоритм Сортировка вставками можно описать следующими позициями:

1. Запомнить во временную переменную ( buff в примере) значение текущего элемента массива;
2. Пока элементы слева от запомненного значения больше чем запомненное – перемещаем их на позицию вправо. Получается, что предыдущий элемент займет ячейку запомненного. А тот, что стоит перед предыдущим – переместится в свою очередь на место предыдущего. И так элементы будут двигаться друг за дружкой.
3. Движение элементов заканчивается, если очередной элемент, который нужно сдвинуть, оказывается по значению меньше, чем тот, что запомнили во временную переменную в начале цикла.
4. Цикл берет следующий элемент, и опять сдвигает все, которые расположены перед ним и большие по значению.

Покажем визуально перемещение значения в массиве из семи элементов во время работы Сортировки вставками :

На первой итерации в переменную-буфер запишется значение из ячейки с индексом 1 и цикл будет проверять этот элемент. Там у нас находится число 2. Оно больше значения, которое записано в нулевой ячейке, поэтому перемещений не будет. Далее в переменную-буфер запишется значение из ячейки с индексом 2 и снова пойдет сравнение со значениями слева и т.д. Только на четвертой итерации внешнего цикла начнется перезапись значений. Тройка сначала поменяется местами с пятеркой, а затем с четверкой.

Таким образом, в процессе Сортировки вставками элемент записанный в buff “просеивается” к началу массива. А в случаях, когда будет найден элемент со значением меньше чем buff или будет достигнуто начало последовательности – просеивание останавливается.

Хорошая визуальная иллюстрация алгоритма Сортировка вставками есть на википедии:

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

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

Предлагаем также посмотреть короткий видоурок по информатике с разбором алгоритма Сортировка вставками :

В мире алгоритмов: Сортировка Вставками

От автора
Данная статья рассматривает один из алгоритмов сортировки массивов. Она предназначена для новичков или же для тех кто по каким-то причинам не знаком с данным алгоритмом. Исправления и поправки только приветствуются:)

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

Словесное описание алгоритма звучит довольно сложно, но на деле это самая простая в реализации сортировка. Каждый из нас, не зависимо от рода деятельности, применял алгоритм сортировки, просто не осознавал это:) Например когда сортировали купюры в кошельке — берем 100 рублей и смотрим — идут 10, 50 и 500 рублёвые купюры. Вот как раз между 50 и 500 и вставляем нашу сотню:) Или приведу пример из всех книжек — игра в карточного «Дурака». Когда мы тянем карту из колоды, смотрим на наши разложенные по возрастанию карты и в зависимости от достоинства вытянутой карты помещаем карту в соответствующее место. Для большей наглядности приведу анимацию из википедии.

Реализация
Прежде чем приступить к реализации определимся с форматом входных данных — для примера это будет массив целочисленных (int) значений. Нумерация элементов массива начинается с 0 и заканчивается n-1. Сам алгоритм реализуем на языке C++. Итак приступим…
Основной цикл алгоритма начинается не с 0-го элемента а с 1-го, потому что элемент до 1-го элемента будет нашей отсортированной последовательностью (помним что массив состоящий из одного элемента является отсортированным) и уже относительно этого элемента с номером 0 мы будем вставлять все остальные. Собственно код:

for(int i=1;i0 && x[j-1]>x[j];j--) // пока j>0 и элемент j-1 > j, x-массив int swap(x[j-1],x[j]); // меняем местами элементы j и j-1 

Реализация сортировки очень проста, всего 3 строчки. Функция swap меняет местами элементы x[j-1] и x[j]. Вложенный цикл ищет место для вставки. Рекомендую запомнить этот алгоритм, чтобы в случае необходимости написать сортировку не позориться сортировкой пузырьком:)

Анализ производительности
Сортировка вставками имеет сложность n 2 , количество сравнений вычисляется по формуле n*(n-1)/2. Для доказательства был написан следующий код:

void Sort(int* arr,int n)< int counter=0; for(int i=1;i0 && arr[j-1]>arr[j];j--) < counter++; int tmp=arr[j-1]; arr[j-1]=arr[j]; arr[j]=tmp; >> cout

Количество перестановок для 100 элементов:

Итак при n=100 количество перестановок равно 4950, а не 10000 если бы мы высчитывали по формуле n 2 . Имейте это ввиду при выборе алгоритма сортировки.

Эффективность
Сортировка вставками наиболее эффективна когда массив уже частично отсортирован и когда элементов массива не много. Если же элементов меньше 10 то данный алгоритм является лучшим. Не зря в быстрой сортировке (оптимизация Боба Седжвика) используется алгоритм сортировки вставками как вспомогательный, но об этом алгоритме мы поговорим позже…

• алгоритм сортировки
• сортировка вставками
• C++

Сортировки вставками

Самое слабое место в этом подходе — вставка элемента в отсортированную часть массива. На самом деле это непросто и на какие только ухищрения не приходится идти, чтобы выполнить этот шаг.

Сортировка простыми вставками

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

def insertion(data): for i in range(len(data)): j = i - 1 key = data[i] while data[j] > key and j >= 0: data[j + 1] = data[j] j -= 1 data[j + 1] = key return data

На примере простых вставок показательно смотрится главное преимущество большинства (но не всех!) сортировок вставками, а именно — очень быстрая обработка почти упорядоченных массивов:

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

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

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

Сортировка простыми вставками с бинарным поиском

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

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

def insertion_binary(data): for i in range(len(data)): key = data[i] lo, hi = 0, i - 1 while lo < hi: mid = lo + (hi - lo) // 2 if key < data[mid]: hi = mid else: lo = mid + 1 for j in range(i, lo + 1, -1): data[j] = data[j - 1] data[lo] = key return data

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

Па́рная сортировка простыми вставками

Модификация простых вставок, разработанная в тайных лабораториях корпорации Oracle. Эта сортировка входит в пакет JDK, является составной частью Dual-Pivot Quicksort. Используется для сортировки малых массивов (до 47 элементов) и сортировки небольших участков крупных массивов.

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

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

На среднюю сложность по времени это не влияет (она так и остаётся равной однако па́рные вставки работают чуть быстрее чем обычные.

Алгоритмы я иллюстрирую на Python, но тут приведу первоисточник (видоизменённый в целях читабельности) на Java:

for (int k = left; ++left //Вставляем больший элемент из пары while (a1 < a[--k]) < a[k + 2] = a[k]; >a[++k + 1] = a1; //Вставляем меньший элемент из пары while (a2 < a[--k]) < a[k + 1] = a[k]; >a[k + 1] = a2; > //Граничный случай, если в массиве нечётное количество элементов //Для последнего элемента применяем сортировку простыми вставками int last = a[right]; while (last < a[--right]) < a[right + 1] = a[right]; >a[right + 1] = last;

Сортировка Шелла

В этом алгоритме очень остроумный подход в определении того, какую именно часть массива считать отсортированной. В простых вставках все просто: от текущего элемента всё что слева — уже отсортировано, всё что справа — ещё не отсортировано. В отличие от простых вставок сортировка Шелла не пытается слева от элемента сразу формировать строго отсортированную часть массива. Она создаёт слева от элемента почти отсортированную часть массива и делает это достаточно быстро.

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

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

def shell(data): inc = len(data) // 2 while inc: for i, el in enumerate(data): while i >= inc and data[i - inc] > el: data[i] = data[i - inc] i -= inc data[i] = el inc = 1 if inc == 2 else int(inc * 5.0 / 11) return data

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

Про сортировку Шелла написано несколько хабрастатей, поэтому не будем перегружаться информацией и двигаемся дальше.

Сортировка деревом

Сортировка деревом за счёт дополнительной памяти быстро решает вопрос с добавлением очередного элемента в отсортированную часть массива. Причём в роли отсортированной части массива выступает бинарное дерево. Дерево формируется буквально на лету при переборе элементов.

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

Основная загвоздка сортировок вставками (затраты на вставку элемента на своё место в отсортированной части массива) здесь решена, построение происходит вполне оперативно. Во всяком случае для освобождения точки вставки не нужно медленно передвигать караваны элементов как в предыдущих алгоритмах. Казалось бы, вот она, наилучшая из сортировок вставками. Но есть проблема.

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

Рандомный массив со значениями от 1 до 10. Элементы в таком порядке генерируют несбалансированное двоичное дерево:

Дерево мало построить, его ещё нужно обойти. Чем больше несбалансированности — тем сильнее будет буксовать алгоритм по обходу дерева. Тут как скажут звёзды, рандомный массив может породить как уродливую корягу (что более вероятно) так и древовидный фрактал.

Значения элементов те же, но порядок другой. Генерируется сбалансированное двоичное дерево:

На прекрасной сакуре
Не хватает лепестка:
Бинарное дерево из десятки.

Проблему несбалансированных деревьев решает сортировка выворачиванием, которая использует особую разновидность бинарного дерева поиска — splay tree. Это замечательное древо-трансформер, которое после каждой операции перестраивается в сбалансированное состояние. Про это будет отдельная статья. К тому времени подготовлю и реализации на Python как для Tree Sort, так и для Splay sort.

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

Статьи серии:

• Excel-приложение AlgoLab.xlsm
• Сортировки обменами
• Сортировки вставками
  • Сортировка библиотекаря
  • Пасьянсная сортировка
  • Сортировка «Ханойская башня»
  • Сортировка выворачиванием
  • Сортировка таблицей Юнга
  Похожие публикации:

  1. Camera extensions proxy что это
  2. Индекс в великобритании как выглядит
  3. Как из статического массива сделать динамический с
  4. Как разобрать ssd без винтов