Сортировка вставками — это простой алгоритм сортировки , который создает окончательный отсортированный массив (или список) по одному элементу за раз путем сравнения . Для больших списков он гораздо менее эффективен, чем более продвинутые алгоритмы, такие как быстрая сортировка , пирамидальная сортировка или сортировка слиянием . Однако сортировка вставками дает несколько преимуществ:
Когда люди вручную сортируют карты в бриджевой раздаче, большинство из них используют метод, похожий на сортировку вставками. [2]
Сортировка вставкой выполняет итерацию , потребляя один входной элемент при каждом повторении, и увеличивает отсортированный выходной список. На каждой итерации сортировка вставкой удаляет один элемент из входных данных, находит место, которому он принадлежит, в отсортированном списке и вставляет его туда. Это повторяется до тех пор, пока не останется ни одного входного элемента.
Сортировка обычно выполняется на месте, путем итерации массива и увеличения отсортированного списка за ним. В каждой позиции массива он сравнивает это значение с наибольшим значением в отсортированном списке (которое оказывается рядом с ним в предыдущей проверенной позиции массива). Если больше, он оставляет элемент на месте и переходит к следующему. Если меньше, он находит правильную позицию в отсортированном списке, сдвигает все большие значения вверх, чтобы освободить место, и вставляет в эту правильную позицию.
Результирующий массив после k итераций имеет свойство сортировки первых k + 1 записей («+1», потому что первая запись пропускается). На каждой итерации первая оставшаяся запись входных данных удаляется и вставляется в результат в правильной позиции, расширяя таким образом результат:
становится
при этом каждый элемент больше x копируется вправо при сравнении с x .
Самый распространенный вариант сортировки вставками, работающий с массивами, можно описать следующим образом:
Далее следует псевдокод полного алгоритма, где массивы начинаются с нуля : [1]
я ← 1 , пока я < длина (A) j ← я в то время как j > 0 и A[j-1] > A[j] меняйте местами A[j] и A[j-1] j ← j - 1 закончиться, пока я ← я + 1закончиться, пока
Внешний цикл проходит по всем элементам, кроме первого, поскольку префикс одного элемента A[0:1]сортируется тривиально, поэтому инвариант сортировки первых iзаписей истинен с самого начала. Внутренний цикл перемещает элемент A[i]на правильное место, так что после цикла i+1сортируются первые элементы. Обратите внимание, что and-оператор в тесте должен использовать короткую оценку , в противном случае тест может привести к ошибке границ массива , когда j=0он попытается оценить A[j-1] > A[j](т.е. доступ A[-1]не удастся).
После расширения swapоперации на месте as x ← A[j]; A[j] ← A[j-1]; A[j-1] ← x(где x— временная переменная) можно создать немного более быструю версию, которая перемещается A[i]на свою позицию за один раз и выполняет только одно присваивание во внутреннем теле цикла: [1]
я ← 1 , пока я < длина (A) х ← А[я] j ← я в то время как j > 0 и A[j-1] > x А[j] ← А[j-1] j ← j - 1 закончиться, пока A[j] ← x [3] я ← я + 1закончиться, пока
Новый внутренний цикл сдвигает элементы вправо, освобождая место для x = A[i].
Алгоритм также может быть реализован рекурсивным способом. Рекурсия просто заменяет внешний цикл, вызывая себя и сохраняя в стеке последовательно меньшие значения n до тех пор, пока n не станет равным 0, после чего функция затем возвращается вверх по цепочке вызовов для выполнения кода после каждого рекурсивного вызова, начиная с n , равного 1, с n увеличивается на 1, когда каждый экземпляр функции возвращается к предыдущему экземпляру. Первоначальный вызов будет InsertionSortR(A, length(A)-1) .
функция InsertionSortR (массив A, int n), если n > 0 вставкаСортR(A, n-1) х ← А[n] j ← n-1 в то время как j >= 0 и A[j] > x А[j+1] ← А[j] j ← j-1 закончиться, пока А[j+1] ← х конец, если функция завершения
Это не делает код короче, но и не уменьшает время выполнения, но увеличивает дополнительное потребление памяти с O(1) до O(N) (на самом глубоком уровне рекурсии стек содержит N ссылок на Aмассив , каждому из которых соответствует значение переменной nот N до 1).
В лучшем случае входными данными является уже отсортированный массив. В этом случае сортировка вставками имеет линейное время выполнения (т. е. O( n )). Во время каждой итерации первый оставшийся элемент входных данных сравнивается только с самым правым элементом отсортированного подраздела массива.
Простейший входной сигнал в худшем случае — это массив, отсортированный в обратном порядке. Набор всех входных данных для наихудшего случая состоит из всех массивов, где каждый элемент является наименьшим или вторым по величине из элементов перед ним. В этих случаях каждая итерация внутреннего цикла будет сканировать и сдвигать весь отсортированный подраздел массива перед вставкой следующего элемента. Это дает сортировке вставками квадратичное время выполнения (т. е. O( n 2 )).
Средний случай также является квадратичным, [4] что делает сортировку вставками непрактичной для сортировки больших массивов. Однако сортировка вставками — один из самых быстрых алгоритмов сортировки очень маленьких массивов, даже быстрее, чем быстрая сортировка ; действительно, хорошие реализации быстрой сортировки используют сортировку вставкой для массивов, меньших определенного порога, даже когда они возникают как подзадачи; точный порог должен быть определен экспериментально и зависит от машины, но обычно составляет около десяти.
Пример: В следующей таблице показаны шаги сортировки последовательности {3, 7, 4, 9, 5, 2, 6, 1}. На каждом этапе подчеркивается рассматриваемый ключ. Ключ, который был перемещен (или оставлен на месте, поскольку он был самым большим из рассмотренных) на предыдущем шаге, отмечен звездочкой.
3 7 4 9 5 2 6 13* 7 4 9 5 2 6 13 7* 4 9 5 2 6 13 4* 7 9 5 2 6 13 4 7 9* 5 2 6 13 4 5* 7 9 2 6 12* 3 4 5 7 9 6 12 3 4 5 6* 7 9 11* 2 3 4 5 6 7 9
Сортировка вставкой очень похожа на сортировку выбором . Как и при сортировке выбором, после прохождения k через массив первые k элементов располагаются в отсортированном порядке. Однако фундаментальное различие между этими двумя алгоритмами заключается в том, что сортировка вставкой сканирует назад от текущего ключа, а сортировка выбором — вперед. В результате при сортировке выбором первые k элементов становятся k наименьшими элементами несортированных входных данных, а при сортировке вставками они являются просто первыми k элементами входных данных.
Основное преимущество сортировки вставкой перед сортировкой выбором состоит в том, что сортировка выбором всегда должна сканировать все оставшиеся элементы, чтобы найти самый маленький элемент в неотсортированной части списка, тогда как сортировка вставкой требует только одного сравнения, когда ( k + 1)-st элемент больше k -го элемента; когда это часто так (например, если входной массив уже отсортирован или частично отсортирован), сортировка вставкой явно более эффективна по сравнению с сортировкой выбором. В среднем (при условии, что ранг ( k + 1)-го элемента является случайным), сортировка вставкой потребует сравнения и сдвига половины предыдущих k элементов, а это означает, что сортировка вставкой будет выполнять примерно вдвое меньше сравнений, чем сортировка выбором. средний.
В худшем случае сортировки вставкой (когда входной массив подвергается обратной сортировке) сортировка вставкой выполняет столько же сравнений, сколько и сортировка выбором. Однако недостатком сортировки вставкой по сравнению с сортировкой выбором является то, что она требует большего количества операций записи, поскольку на каждой итерации вставка ( k + 1)-го элемента в отсортированную часть массива требует множества перестановок элементов для смещения всех элементов. следующих элементов, тогда как для каждой итерации сортировки выбором требуется только одна замена. В общем, сортировка вставкой будет записывать в массив O( n 2 ) раз, тогда как сортировка выбором будет записывать только O( n ) раз. По этой причине сортировка выбором может быть предпочтительнее в тех случаях, когда запись в память значительно дороже, чем чтение, например, в EEPROM или флэш-памяти .
В то время как некоторые алгоритмы «разделяй и властвуй», такие как быстрая сортировка и сортировка слиянием , превосходят сортировку вставкой для больших массивов, нерекурсивные алгоритмы сортировки, такие как сортировка вставкой или сортировка выбором, обычно работают быстрее для очень маленьких массивов (точный размер зависит от среды и реализации, но обычно составляет от 7 до 50 элементов). Следовательно, полезной оптимизацией при реализации этих алгоритмов является гибридный подход, использующий более простой алгоритм, когда массив разделен на небольшой размер. [1]
DL Shell внесла существенные улучшения в алгоритм; модифицированная версия называется сортировкой Шелла . Алгоритм сортировки сравнивает элементы, разделенные расстоянием, которое уменьшается с каждым проходом. Сортировка Шелла значительно улучшила время выполнения в практической работе: два простых варианта требуют времени выполнения O( n 3/2 ) и O( n 4/3 ). [5] [6]
Если стоимость сравнений превышает стоимость замен, как, например, в случае со строковыми ключами, хранящимися по ссылке или при взаимодействии с человеком (например, при выборе одного из пары, отображаемой рядом), то использование двоичной сортировки вставкой может дать результат лучшая производительность. [7] Двоичная сортировка вставкой использует двоичный поиск для определения правильного места для вставки новых элементов и, следовательно, в худшем случае выполняет сравнения ⌈log 2 n ⌉. Когда каждый элемент в массиве ищется и вставляется, это O( n log n ). [7] Алгоритм в целом по-прежнему имеет время работы в среднем O( n 2 ) из-за серии свопов, необходимых для каждой вставки. [7]
Количество перестановок можно уменьшить, вычислив положение нескольких элементов перед их перемещением. Например, если целевая позиция двух элементов вычисляется до того, как они будут перемещены в правильное положение, количество перестановок может быть уменьшено примерно на 25% для случайных данных. В крайнем случае этот вариант работает аналогично сортировке слиянием .
Вариант под названием « Двоичная сортировка слиянием» использует двоичную сортировку вставкой для сортировки групп из 32 элементов, за которой следует окончательная сортировка с использованием сортировки слиянием . Он сочетает в себе скорость сортировки вставкой для небольших наборов данных со скоростью сортировки слиянием для больших наборов данных. [8]
Чтобы избежать необходимости делать серию свопов для каждой вставки, входные данные могут храниться в связанном списке , что позволяет вставлять элементы в список или из него за постоянное время, когда позиция в списке известна. Однако поиск в связанном списке требует последовательного перехода по ссылкам к нужной позиции: связанный список не имеет произвольного доступа, поэтому в нем нельзя использовать более быстрый метод, например бинарный поиск. Следовательно, время, необходимое для поиска, равно O( n ) , а время сортировки — O( n2 ). Если используется более сложная структура данных (например, куча или двоичное дерево ), время, необходимое для поиска и вставки, может быть значительно сокращено; в этом суть сортировки кучи и сортировки двоичного дерева .
В 2006 году Бендер, Мартин Фарах-Колтон и Мостейро опубликовали новый вариант сортировки вставками, названный библиотечной сортировкой или сортировкой вставкой с пробелами , который оставляет небольшое количество неиспользуемых пробелов (то есть «пробелов»), разбросанных по всему массиву. Преимущество состоит в том, что вставкам нужно только сдвигать элементы до тех пор, пока не будет достигнут пробел. Авторы показывают, что этот алгоритм сортировки работает с высокой вероятностью за время O( n log n ). [9]
Если используется список пропуска , время вставки сокращается до O(log n ), и замены не требуются, поскольку список пропуска реализован в структуре связанного списка. Окончательное время выполнения вставки будет равно O( n log n ).
Если элементы хранятся в связанном списке, то список можно отсортировать с дополнительным пространством O (1). Алгоритм начинается с изначально пустого (и, следовательно, тривиально отсортированного) списка. Входные элементы удаляются из списка по одному, а затем вставляются в нужное место в отсортированном списке. Когда входной список пуст, отсортированный список имеет желаемый результат.
структура LIST * SortList1 ( структура LIST * pList ) { // ноль или один элемент в списке if ( pList == NULL || pList -> pNext == NULL ) вернуть список ; // заголовок — первый элемент результирующего отсортированного списка структура LIST * head = NULL ; в то время как ( pList != NULL ) { структура LIST * текущий = pList ; pList = pList -> pNext ; if ( head == NULL || current -> iValue < head -> iValue ) { // вставляем в заголовок отсортированного списка // или как первый элемент в пустом отсортированном списке текущий -> pNext = голова ; голова = текущий ; } еще { // вставляем текущий элемент в правильную позицию в непустом отсортированном списке структура LIST * p = head ; в то время как ( п != NULL ) { if ( p -> pNext == NULL || // последний элемент отсортированного списка current -> iValue < p -> pNext -> iValue ) // середина списка { // вставляем в середину отсортированного списка или в качестве последнего элемента текущий -> pNext = p -> pNext ; p -> pNext = текущий ; перерыв ; // сделанный } р = р -> pNext ; } } } вернуть голову ; }Приведенный ниже алгоритм использует конечный указатель [10] для вставки в отсортированный список. Более простой рекурсивный метод каждый раз перестраивает список (вместо объединения) и может использовать стековое пространство O( n ).
структура LIST { структура LIST * pNext ; int iValue ; }; struct LIST * SortList ( struct LIST * pList ) { // ноль или один элемент в списке if ( ! pList || ! pList -> pNext ) return pList ; /* создаем отсортированный массив из пустого списка */ struct LIST * pSorted = NULL ; /* удаляем элементы из входного списка один за другим, пока он не станет пустым */ while ( pList != NULL ) { /* запоминаем заголовок */ struct LIST * pHead = pList ; /* конечный указатель для эффективного соединения */ struct LIST ** ppTrail = & pSorted ; /* вытащить список из головы */ pList = pList -> pNext ; /* вставляем голову в отсортированный список в нужном месте */ while ( ! ( * ppTrail == NULL || pHead -> iValue < ( * ppTrail ) -> iValue )) { /* здесь находится голова? */ /* нет — продолжить список */ ppTrail = & ( * ppTrail ) -> pNext ; } pHead -> pNext = * ppTrail ; * ppTrail = pHead ; } вернуть pSorted ; } 
