WikiDer > Вставка сортировки

Insertion sort
Вставка сортировки
Вставка sort.gif
Анимация вставки сортировки
Учебный классАлгоритм сортировки
Структура данныхМножество
Худший случай спектакльО (п2) сравнения и свопы
Лучший случай спектакльO (п) сравнения, O (1) свопы
Средний спектакльО (п2) сравнения и свопы
Худший случай космическая сложностьО (п) итого, O (1) вспомогательный

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

  • Простая реализация: Джон Бентли показывает трехстрочный C версия, и пятистрочная оптимизированный версия[1]
  • Эффективен для (довольно) небольших наборов данных, как и другие алгоритмы квадратичной сортировки
  • Более эффективен на практике, чем большинство других простых квадратичных (т. Е. О(п2)) такие алгоритмы, как сортировка выбора или же пузырьковая сортировка
  • Адаптивный, т.е. эффективен для наборов данных, которые уже существенно отсортированы: временная сложность является О(кн), когда каждый элемент на входе не больше, чем k места вдали от отсортированной позиции
  • Стабильный; т.е. не меняет относительный порядок элементов с одинаковыми ключами
  • На месте; т.е. требуется только постоянное количество O (1) дополнительного пространства памяти
  • В сети; т.е. может сортировать список по мере его получения

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

Алгоритм

Графический пример сортировки вставками. Частично отсортированный список (черный) изначально содержит только первый элемент в списке. На каждой итерации один элемент (красный) удаляется из входных данных «еще не проверено на порядок» и вставляется на месте в отсортированный список.

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

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

Результирующий массив после k итераций имеет свойство, при котором первая k + 1 записи отсортированы («+1», потому что первая запись пропущена). На каждой итерации первая оставшаяся запись ввода удаляется и вставляется в результат в правильной позиции, таким образом расширяя результат:

Массив до вставки x

становится

Массив после вставки x

с каждым элементом больше, чем Икс копируется вправо при сравнении с Икс.

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

  1. Предположим, существует функция с именем Вставлять предназначен для вставки значения в отсортированную последовательность в начале массива. Он работает, начиная с конца последовательности и сдвигая каждый элемент на одну позицию вправо, пока не будет найдено подходящее положение для нового элемента. Побочным эффектом функции является перезапись значения, сохраненного сразу после отсортированной последовательности в массиве.
  2. Чтобы выполнить сортировку вставкой, начните с самого левого элемента массива и вызовите Вставлять чтобы вставить каждый встреченный элемент в его правильную позицию. Упорядоченная последовательность, в которую вставлен элемент, сохраняется в начале массива в уже изученном наборе индексов. Каждая вставка перезаписывает одно значение: вставляемое значение.

Псевдокод полного алгоритма следует, где массивы с нуля:[1]

я ← 1пока i <длина (A) j ← i пока j> 0 и A [j-1]> A [j] замена A [j] и A [j-1] j ← j - 1 конец пока    я ← я + 1конец пока

Внешний цикл проходит по всем элементам, кроме первого, потому что одноэлементный префикс A [0: 1] сортируется тривиально, поэтому инвариантный что первый я записи отсортированы верно с самого начала. Внутренний цикл перемещает элемент A [i] в правильное место, чтобы после петли первый я + 1 элементы отсортированы. Обратите внимание, что и-оператор в тесте должен использовать оценка короткого замыкания, иначе тест может привести к ошибка границ массива, когда j = 0 и он пытается оценить A [j-1]> A [j] (т.е. доступ A [-1] не удается).

После расширения замена операция на месте как x ← A [j]; A [j] ← A [j-1]; A [j-1] ← x (куда Икс - временная переменная), можно создать немного более быструю версию, которая перемещает A [i] в свою позицию за один раз и выполняет только одно присваивание в теле внутреннего цикла:[1]

я ← 1пока i пока j> = 0 и A [j]> x A [j + 1] ← A [j] j ← j - 1 конец пока    A [j + 1] ← x[3]    я ← я + 1конец пока

Новый внутренний цикл смещает элементы вправо, чтобы освободить место для х = А [я].

Алгоритм также можно реализовать рекурсивно. Рекурсия просто заменяет внешний цикл, вызывая себя и сохраняя последовательно меньшие значения п в стеке, пока п равно 0, где функция затем возвращает резервную копию цепочки вызовов для выполнения кода после каждого рекурсивного вызова, начиная с п равно 1, с п увеличивается на 1, когда каждый экземпляр функции возвращается к предыдущему экземпляру. Первоначальный звонок будет insertSortR (A, длина (A) -1).

функция insertSortR (массив A, int n) если n> 0 insertSortR (A, n-1) x ← A [n] j ← n-1 пока j> = 0 и A [j]> x A [j + 1] ← A [j] j ← j-1 конец пока        A [j + 1] ← x конец, есликонечная функция

Это не делает код короче, а также не сокращает время выполнения, но увеличивает потребление дополнительной памяти от О (1) к НА) (на самом глубоком уровне рекурсии стек содержит N ссылки на А массив, каждый с сопутствующим значением переменной п из N до 1).

Лучшие, худшие и средние случаи

В лучшем случае входные данные - это уже отсортированный массив. В этом случае сортировка вставкой имеет линейное время выполнения (т. Е. O (п)). Во время каждой итерации первый оставшийся элемент ввода сравнивается только с крайним правым элементом отсортированной части массива.

Самый простой вход в худшем случае - это массив, отсортированный в обратном порядке. Набор всех входных данных наихудшего случая состоит из всех массивов, где каждый элемент является наименьшим или вторым наименьшим из элементов перед ним. В этих случаях каждая итерация внутреннего цикла будет сканировать и сдвигать всю отсортированную часть массива перед вставкой следующего элемента. Это дает сортировке вставки квадратичное время выполнения (то есть O (п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) -й элемент больше, чем k-й элемент; когда это часто бывает так (например, если входной массив уже отсортирован или частично отсортирован), сортировка вставкой явно более эффективна по сравнению с сортировкой по выбору. В среднем (исходя из ранга (k + 1) -й ранг элемента является случайным), сортировка вставкой потребует сравнения и сдвига половины предыдущего k элементов, что означает, что сортировка вставкой в ​​среднем будет выполнять примерно вдвое меньше сравнений, чем сортировка по выбору.

В худшем случае для сортировки вставкой (когда входной массив отсортирован в обратном порядке) сортировка вставкой выполняет столько же сравнений, что и сортировка выбора. Однако недостатком сортировки вставкой перед сортировкой выбора является то, что она требует большего количества записей из-за того, что на каждой итерации вставка (k + 1) -й элемент в отсортированной части массива требует замены множества элементов для сдвига всех следующих элементов, в то время как для каждой итерации сортировки выбора требуется только одна замена. В общем случае сортировка вставкой будет записывать в массив O (п2) раз, тогда как сортировка выбора будет писать только O (п) раз. По этой причине сортировка выбора может быть предпочтительнее в случаях, когда запись в память значительно дороже чтения, например, с EEPROM или же флэш-память.

Хотя некоторые алгоритмы разделяй и властвуй Такие как быстрая сортировка и Сортировка слиянием лучше сортировки вставкой для больших массивов, нерекурсивные алгоритмы сортировки, такие как сортировка вставкой или сортировка выбора, обычно быстрее для очень маленьких массивов (точный размер зависит от среды и реализации, но обычно составляет от 7 до 50 элементов). Следовательно, полезной оптимизацией при реализации этих алгоритмов является гибридный подход с использованием более простого алгоритма, когда массив был разделен на небольшой размер.[1]

Варианты

Д. Л. Шелл внесены существенные улучшения в алгоритм; модифицированная версия называется Сортировка оболочки. Алгоритм сортировки сравнивает элементы, разделенные расстоянием, которое уменьшается с каждым проходом. Сортировка Shell значительно улучшила время работы на практике, с двумя простыми вариантами, требующими O (п3/2) и O (п4/3) Продолжительность.[5][6]

Если стоимость сравнений превышает стоимость свопов, как, например, в случае строковых ключей, хранящихся по ссылке или при взаимодействии с человеком (например, при выборе одной из пары, отображаемой рядом), то использование сортировка двоичной вставкой[нужна цитата] может дать лучшую производительность. Сортировка двоичной вставкой использует бинарный поиск для определения правильного места для вставки новых элементов, поэтому выполняет ⌈log2 п⌉ сравнения в худшем случае, что составляет O (п бревноп). Алгоритм в целом по-прежнему имеет время работы O (п2) в среднем из-за серии свопов, необходимых для каждой вставки.

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

Вариант с именем двоичная сортировка слиянием использует сортировка двоичной вставкой для сортировки групп из 32 элементов, после чего следует окончательная сортировка с использованием Сортировка слиянием. Он сочетает в себе скорость сортировки вставкой для небольших наборов данных со скоростью сортировки слиянием для больших наборов данных.[7]

Чтобы избежать необходимости выполнять серию свопов для каждой вставки, ввод можно сохранить в связанный список, который позволяет вставлять элементы в список или из него в постоянное время, когда позиция в списке известна. Однако поиск в связанном списке требует последовательного перехода по ссылкам в желаемую позицию: связанный список не имеет произвольного доступа, поэтому он не может использовать более быстрый метод, такой как двоичный поиск. Следовательно, время, необходимое для поиска, равно O (п), а время сортировки - O (п2). Если более сложный структура данных (например., куча или же двоичное дерево) можно значительно сократить время, необходимое для поиска и вставки; это суть куча сортировки и двоичная сортировка дерева.

В 2006 году Бендер, Мартин Фарач-Колтон, а Мостейро опубликовал новый вариант сортировки вставками под названием сортировка библиотеки или же сортировка вставки с разрывом что оставляет небольшое количество неиспользуемых пробелов (т. е. "пробелов") по всему массиву. Преимущество в том, что при вставке нужно только сдвигать элементы, пока не будет достигнут разрыв. Авторы показывают, что этот алгоритм сортировки с большой вероятностью работает за O (п бревноп) время.[8]

Если пропустить список время вставки сокращается до O (logп), и свопы не нужны, потому что список пропуска реализован в структуре связанного списка. Окончательное время вставки будет O (п бревноп).

Сортировка вставкой списка это вариант сортировки вставками. Уменьшает количество движений.[нужна цитата]

Код сортировки вставки списка в C

Если элементы хранятся в связанном списке, то список можно отсортировать с O (1) дополнительным пространством. Алгоритм начинается с изначально пустого (и, следовательно, тривиально отсортированного) списка. Элементы ввода удаляются из списка по одному, а затем вставляются в нужное место в отсортированном списке. Когда список ввода пуст, отсортированный список имеет желаемый результат.

структура СПИСОК * SortList1(структура СПИСОК * pList) {    // ноль или один элемент в списке    если (pList == НОЛЬ || pList->pNext == НОЛЬ)        возвращаться pList;    // head - первый элемент итогового отсортированного списка    структура СПИСОК * голова = НОЛЬ;    пока (pList != НОЛЬ) {        структура СПИСОК * Текущий = pList;        pList = pList->pNext;        если (голова == НОЛЬ || Текущий->Я ценю < голова->Я ценю) {            // вставляем в начало отсортированного списка            // или как первый элемент в пустой отсортированный список            Текущий->pNext = голова;            голова = Текущий;        } еще {            // вставляем текущий элемент в нужную позицию в непустом отсортированном списке            структура СПИСОК * п = голова;            пока (п != НОЛЬ) {                если (п->pNext == НОЛЬ || // последний элемент отсортированного списка                    Текущий->Я ценю < п->pNext->Я ценю) // середина списка                {                    // вставить в середину отсортированного списка или как последний элемент                    Текущий->pNext = п->pNext;                    п->pNext = Текущий;                    перемена; // сделано                }                п = п->pNext;            }        }    }    возвращаться голова;}

В приведенном ниже алгоритме используется конечный указатель.[9] для вставки в отсортированный список. Более простой рекурсивный метод перестраивает список каждый раз (а не сращивает) и может использовать O (п) пространство стека.

структура СПИСОК{  структура СПИСОК * pNext;  int           Я ценю;};структура СПИСОК * SortList(структура СПИСОК * pList){  // ноль или один элемент в списке  если (!pList || !pList->pNext)      возвращаться pList;  / * строим отсортированный массив из пустого списка * /  структура СПИСОК * pСортировано = НОЛЬ;  / * берем элементы из входного списка один за другим, пока он не станет пустым * /  пока (pList != НОЛЬ) {      / * запоминаем голову * /      структура СПИСОК *   pHead  = pList;      / * конечный указатель для эффективного монтажа * /      структура СПИСОК ** ppTrail = &pСортировано;      / * выскакивать список * /      pList = pList->pNext;      / * вставляем голову в отсортированный список в нужном месте * /      пока (!(*ppTrail == НОЛЬ || pHead->Я ценю < (*ppTrail)->Я ценю)) { / * здесь голова? * /          / * нет - продолжить вниз по списку * /          ppTrail = &(*ppTrail)->pNext;      }      pHead->pNext = *ppTrail;      *ppTrail = pHead;  }  возвращаться pСортировано;}

Рекомендации

  1. ^ а б c d Бентли, Джон (2000), Жемчуг программирования, ACM Press / Addison – Wesley, стр.107-109
  2. ^ Седжвик, Роберт (1983), Алгоритмы, Эддисон-Уэсли, стр.95ff, ISBN 978-0-201-06672-2.
  3. ^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2009) [1990], «Раздел 2.1: Сортировка вставками», Введение в алгоритмы (3-е изд.), MIT Press и McGraw-Hill, стр. 16–18, ISBN 0-262-03384-4. См., В частности, стр. 18.
  4. ^ Шварц, Кейт. "Почему в среднем случае сортировка вставкой Θ (n ^ 2)? (Ответ" templatetypedef ")". Переполнение стека.
  5. ^ Франк, Р. М .; Лазарь, Р. Б. (1960). «Процедура высокоскоростной сортировки». Коммуникации ACM. 3 (1): 20–22. Дои:10.1145/366947.366957.
  6. ^ Седжвик, Роберт (1986). «Новая верхняя граница для Shellsort». Журнал алгоритмов. 7 (2): 159–173. Дои:10.1016/0196-6774(86)90001-5.
  7. ^ «Сортировка двоичным слиянием»
  8. ^ Бендер, Майкл А .; Фарах-Колтон, Мартин; Mosteiro, Miguel A. (2006), "Сортировка вставкой О(п бревноп)", Теория вычислительных систем, 39 (3): 391–397, arXiv:cs / 0407003, Дои:10.1007 / s00224-005-1237-z, МИСТЕР 2218409
  9. ^ Хилл, Курт (редактор), "Техника скользящего указателя", Эйлер, Государственный университет Вэлли-Сити, получено 22 сентября 2012.

дальнейшее чтение

внешняя ссылка