Войти
 Анимация вставки сортировки | |
| Класс | Алгоритм сортировки |
|---|---|
| Структура данных | Массив |
| Худший случай производительность | О (n) сравнений и свопов |
| Лучший случай производительность | O (n) сравнений, O (1) свопов |
| Средняя производительность | О (n) сравнений и свопов |
| Худшая -case сложность пространства | О (n) всего, O (1) вспомогательное |
Сортировка вставкой - это простой алгоритм сортировки, который строит окончательный отсортированный массив (или список) по одному элементу за раз. Он гораздо менее эффективен для больших списков, чем более сложные алгоритмы, такие как quicksort, heapsort или сортировка слиянием. Однако сортировка вставкой дает несколько преимуществ:
Когда люди вручную сортируют карты в руке моста, большинство используют метод, аналогичный сортировке вставкой.
Графический пример сортировки вставками. Частично отсортированный список (черный) изначально содержит только первый элемент в списке. На каждой итерации один элемент (красный) удаляется из входных данных «еще не проверено на порядок» и вставляется на месте в отсортированный список. Сортировка вставкой выполняет итерацию, потребляя один входной элемент при каждом повторении, и увеличение отсортированного списка вывода. На каждой итерации сортировка вставкой удаляет один элемент из входных данных, находит место, которому он принадлежит в отсортированном списке, и вставляет его туда. Он повторяется до тех пор, пока не останется никаких элементов ввода.
Сортировка обычно выполняется на месте путем повторения массива и увеличения отсортированного списка за ним. В каждой позиции массива он проверяет значение там на соответствие наибольшему значению в отсортированном списке (которое оказывается рядом с ним в предыдущей проверенной позиции массива). Если больше, он оставляет элемент на месте и переходит к следующему. Если меньше, он находит правильную позицию в отсортированном списке, сдвигает все большие значения вверх, чтобы освободить место, и вставляет в эту правильную позицию.
Результирующий массив после k итераций имеет свойство сортировки первых k + 1 записей («+1», потому что первая запись пропускается). На каждой итерации первая оставшаяся запись ввода удаляется и вставляется в результат в правильной позиции, таким образом расширяя результат:
становится
с каждым элементом больше x, скопированным вправо при сравнении с Икс.
Наиболее распространенный вариант сортировки вставкой, который работает с массивами, можно описать следующим образом:
Далее следует псевдокод полного алгоритма, где массивы отсчитываются от нуля :
i ← 1, а i < length(A) j ← i пока j>0 и A [j-1]>A [j] меняют местами A [j] и A [j-1] j ← j - 1 end while i ← i + 1 end while
Внешний цикл выполняется по всем элементам, кроме первого, потому что одноэлементный префикс A [0: 1]сортируется тривиально, поэтому инвариант о том, что сортируются первые записи i, истинен с самого начала. Внутренний цикл перемещает элемент A [i]в его правильное место, чтобы после цикла были отсортированы первые элементы i + 1. Обратите внимание, что и-оператор в тесте должен использовать оценку короткого замыкания, иначе тест может привести к ошибке границ массива, когда j = 0и он пытается оценить A [j-1]>A [j](т. е. доступ к A [-1]не выполняется).
После развертывания операции swapна месте как x ← A [j]; A [j] ← A [j-1]; A [j-1] ← x(где x- временная переменная), может быть создана немного более быстрая версия, которая перемещает A [i]на свою позицию в одном go и выполняет только одно присвоение в теле внутреннего цикла:
i ← 1 while i < length(A) x ← A[i] j ← i - 1 while j>= 0 и A [j ]>x A [j + 1] ← A [j] j ← j - 1 end while A [j + 1] ← xi ← i + 1 end while
Новый внутренний цикл сдвигает элементы вправо, чтобы освободить место для x = A [i].
. Алгоритм также может быть реализован рекурсивным способом. Рекурсия просто заменяет внешний цикл, вызывая себя и сохраняя последовательно меньшие значения n в стеке до тех пор, пока n не станет равным 0, где функция затем возвращает резервную копию цепочки вызовов для выполнения кода после каждого рекурсивного вызова, начиная с n, равного 1, с увеличением n на 1, когда каждый экземпляр функции возвращается к предыдущему экземпляру. Первоначальным вызовом будет insertSortR (A, length (A) -1).
function insertSortR (array A, int n) if n>0 insertSortR (A, n-1) x ← A [n] j ← n-1 while j>= 0 и A [j]>x A [j + 1] ← A [j] j ← j-1 end while A [j + 1] ← x end if end function
Это не делает код короче, а также не сокращает время выполнения, но увеличивает потребление дополнительной памяти с O (1) до O ( N) (на самом глубоком уровне рекурсии стек содержит N ссылок на массив A, каждая с сопутствующим значением переменной nот N до 1).
Вход для наилучшего случая - это уже отсортированный массив. В этом случае сортировка вставкой имеет линейное время выполнения (то есть O (n)). Во время каждой итерации первый оставшийся элемент ввода сравнивается только с крайним правым элементом отсортированной части массива.
Простейший вход в худшем случае - это массив, отсортированный в обратном порядке. Набор всех входных параметров наихудшего случая состоит из всех массивов, где каждый элемент является наименьшим или вторым наименьшим из элементов перед ним. В этих случаях каждая итерация внутреннего цикла будет сканировать и сдвигать всю отсортированную часть массива перед вставкой следующего элемента. Это дает сортировке вставки квадратичное время выполнения (то есть O (n)).
Средний случай также является квадратичным, что делает сортировку вставкой непрактичной для сортировки больших массивов. Однако сортировка вставкой - один из самых быстрых алгоритмов сортировки очень маленьких массивов, даже быстрее, чем quicksort ; действительно, хорошие реализации quicksort используют сортировку вставкой для массивов меньше определенного порога, также когда возникают как подзадачи; точный порог должен быть определен экспериментально и зависит от машины, но обычно составляет около десяти.
Пример: В следующей таблице показаны шаги для сортировки последовательности {3, 7, 4, 9, 5, 2, 6, 1}. На каждом этапе рассматриваемый ключ подчеркнут. Ключ, который был перемещен (или оставлен на месте, потому что он считался самым большим) на предыдущем шаге, отмечен звездочкой.
37 4 9 5 2 6 1 3 * 7 4 9 5 2 6 1 3 7 * 4 9 5 2 6 1 3 4 * 7 9 5 2 6 1 3 4 7 9 * 5 2 6 1 3 4 5 * 7 9 2 6 1 2 * 3 4 5 7 9 6 1 2 3 4 5 6 * 7 9 1 1 * 2 3 4 5 6 7 9
Сортировка вставкой очень похожа на сортировка выбора. Как и при сортировке по выбору, после того, как k проходит через массив, первые k элементов находятся в отсортированном порядке. Однако фундаментальное различие между этими двумя алгоритмами состоит в том, что сортировка вставкой сканирует назад от текущего ключа, а сортировка выбором сканирует вперед. Это приводит к тому, что сортировка выбора делает первые k элементов k наименьшими элементами несортированного ввода, тогда как при сортировке вставкой они просто являются первыми k элементами ввода.
Основное преимущество сортировки вставкой перед сортировкой выбора состоит в том, что сортировка выбора всегда должна сканировать все оставшиеся элементы, чтобы найти абсолютный наименьший элемент в несортированной части списка, в то время как сортировка вставкой требует только одного сравнения, когда ( k + 1) -й элемент больше k-го элемента; когда это часто бывает так (например, если входной массив уже отсортирован или частично отсортирован), сортировка вставкой явно более эффективна по сравнению с сортировкой по выбору. В среднем (при условии, что ранг (k + 1) -го элемента является случайным), сортировка вставкой потребует сравнения и сдвига половины предыдущих k элементов, что означает, что сортировка вставкой будет выполнять примерно вдвое меньше сравнений, чем сортировка выбора на в среднем.
В худшем случае для сортировки вставкой (когда входной массив отсортирован в обратном порядке) сортировка вставкой выполняет столько же сравнений, что и сортировка по выбору. Однако недостатком сортировки вставкой по сравнению с сортировкой по выбору является то, что она требует большего количества операций записи из-за того, что на каждой итерации вставка (k + 1) -го элемента в отсортированную часть массива требует замены множества элементов, чтобы сдвинуть все следующих элементов, в то время как для каждой итерации сортировки выбора требуется только один обмен. В общем, сортировка вставкой будет записывать в массив O (n) раз, тогда как сортировка по выбору будет записывать только O (n) раз. По этой причине сортировка по выбору может быть предпочтительнее в случаях, когда запись в память значительно дороже чтения, например, с EEPROM или флэш-памятью.
, в то время как некоторые разделяют и властвуют. алгоритмы, такие как quicksort и mergesort, превосходят сортировку вставкой для больших массивов, нерекурсивные алгоритмы сортировки, такие как сортировка вставкой или сортировка выбора, обычно быстрее для очень маленьких массивов (точные размер зависит от среды и реализации, но обычно составляет от 7 до 50 элементов). Следовательно, полезной оптимизацией при реализации этих алгоритмов является гибридный подход с использованием более простого алгоритма, когда массив был разделен до небольшого размера.
D. Л. Шелл внес существенные улучшения в алгоритм; измененная версия называется Shell sort. Алгоритм сортировки сравнивает элементы, разделенные расстоянием, которое уменьшается с каждым проходом. Shell sort значительно улучшил время выполнения на практике, с двумя простыми вариантами, требующими времени выполнения O (n) и O (n).
Если стоимость сравнений превышает стоимость свопов, как в случае с Например, со строковыми ключами, хранящимися по ссылке или при взаимодействии с человеком (например, при выборе одной из пары, отображаемой рядом), то использование сортировки двоичной вставкой может дать лучшую производительность. Сортировка двоичной вставкой использует двоичный поиск для определения правильного места для вставки новых элементов и, следовательно, выполняет сравнения ⌈log 2 n⌉ в худшем случае, который равен O (n log n). Алгоритм в целом по-прежнему имеет время работы O (n) в среднем из-за серии замен, необходимых для каждой вставки.
Количество перестановок можно уменьшить, вычислив положение нескольких элементов перед их перемещением. Например, если целевая позиция двух элементов вычисляется до того, как они будут перемещены в правильную позицию, количество перестановок может быть уменьшено примерно на 25% для случайных данных. В крайнем случае этот вариант работает аналогично сортировке слиянием.
Вариант с именем двоичная сортировка слияния использует сортировку двоичной вставкой для сортировки групп из 32 элементов, за которой следует окончательная сортировка с использованием сортировка слияния. Он сочетает в себе скорость сортировки вставкой для небольших наборов данных со скоростью сортировки слиянием для больших наборов данных.
Чтобы избежать необходимости выполнять серию перестановок для каждой вставки, входные данные могут быть сохранены в связанный список, который позволяет вставлять элементы в список или из него в постоянное время, когда известна позиция в списке. Однако поиск в связанном списке требует последовательного перехода по ссылкам в нужную позицию: связанный список не имеет произвольного доступа, поэтому он не может использовать более быстрый метод, такой как двоичный поиск. Следовательно, время выполнения, необходимое для поиска, равно O (n), а время сортировки - O (n). Если используется более сложная структура данных (например, куча или двоичное дерево ), время, необходимое для поиска и вставки, может быть значительно сокращено; в этом суть сортировки кучей и сортировки двоичного дерева.
В 2006 году Бендер, Мартин Фарач-Колтон и Мостейро опубликовали новый вариант сортировки вставкой под названием сортировка библиотеки или сортировка вставкой с пробелами, которая оставляет небольшое количество неиспользуемых пробелов (т. е. «пробелов») по всему массиву. Преимущество в том, что при вставке нужно только сдвигать элементы, пока не будет достигнут разрыв. Авторы показывают, что этот алгоритм сортировки выполняется с высокой вероятностью за время O (n log n).
Если используется список пропусков, время вставки сокращается до O (log n), и свопы не нужны, потому что список пропуска реализован в структуре связанного списка. Конечное время выполнения вставки будет O (n log n).
Сортировка вставкой списка - это вариант сортировки вставкой. Это уменьшает количество перемещений.
Если элементы хранятся в связанном списке, то список может быть отсортирован с дополнительным пространством O (1). Алгоритм начинается с изначально пустого (и, следовательно, тривиально отсортированного) списка. Элементы ввода удаляются из списка по одному, а затем вставляются в нужное место в отсортированном списке. Когда список ввода пуст, отсортированный список имеет желаемый результат.
struct LIST * SortList1 (struct LIST * pList) {// ноль или один элемент в списке if (pList == NULL || pList->pNext == NULL) return pList; // head - это первый элемент результирующего отсортированного списка struct LIST * head = NULL; в то время как (pList! = NULL) {struct LIST * current = pList; pList = pList->pNext; if (head == NULL || current->iValue < head->iValue) {// вставляем в начало отсортированного списка // или как первый элемент в пустой отсортированный список current->pNext = head; голова = текущая; } else {// вставляем текущий элемент в нужную позицию в непустом отсортированном списке struct LIST * p = head; while (p! = NULL) {if (p->pNext == NULL || // последний элемент отсортированного списка current->iValue < p->pNext->iValue) // середина списка {// вставить в середина отсортированного списка или как последний элемент current->pNext = p->pNext; p->pNext = текущий; перемена; // готово} p = p->pNext; }}} вернуть голову; }Приведенный ниже алгоритм использует конечный указатель для вставки в отсортированный список. Более простой рекурсивный метод перестраивает список каждый раз (а не сращивает) и может использовать пространство стека O (n).
struct LIST {struct 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; } return pSorted; } | The Wikibook Algorithm В реализации есть страница по теме: Сортировка вставкой |
 | На Викискладе есть медиафайлы, связанные с Сортировкой вставкой. |
.
