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

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

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

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

Алгоритм [ править ]

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

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

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

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

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

становится

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

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

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

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

Далее следует псевдокод полного алгоритма, где массивы отсчитываются от нуля : [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операции на месте как x ← A[j]; A[j] ← A[j-1]; A[j-1] ← x(где x- временная переменная) может быть создана немного более быстрая версия, которая перемещается A[i]в свою позицию за один раз и выполняет только одно присваивание в теле внутреннего цикла: [1]

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

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

Алгоритм также может быть реализован рекурсивно. Рекурсия просто заменяет внешний цикл, вызывая себя и сохраняя последовательно меньшие значения n в стеке до тех пор, пока n не станет равным 0, где функция затем возвращает цепочку вызовов для выполнения кода после каждого рекурсивного вызова, начиная с n, равного 1, с n увеличивается на 1, когда каждый экземпляр функции возвращается к предыдущему экземпляру. Первым вызовом будет insertSortR (A, length (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 конец, если конечная функция

Это не делает код короче, это также не сокращает время выполнения, но увеличивает потребление дополнительной памяти с 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]

Варианты [ править ]

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

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

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

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

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

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

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

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

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

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

struct  LIST  *  SortList1 ( struct  LIST  *  pList )  {  // ноль или один элемент в списке  if  ( pList  ==  NULL  ||  pList -> pNext  ==  NULL )  return  pList ;  // head - это первый элемент результирующего отсортированного списка  struct  LIST  *  head  =  NULL ;  while  ( pList  ! =  NULL )  {  struct  LIST  *  current  =  pList;  pList  =  pList -> pNext ;  if  ( head  ==  NULL  ||  current -> iValue  <  head -> iValue )  {  // вставить в начало отсортированного списка  // или как первый элемент в пустой отсортированный список  current -> pNext  =  head ;  голова  =  текущий ;  }  else  {  // вставляем текущий элемент в нужную позицию в непустой  структуре  отсортированного списка LIST  *  p  =  head;  while  ( p  ! =  NULL )  {  if  ( p -> pNext  ==  NULL  ||  // последний элемент  текущего отсортированного списка -> iValue  <  p -> pNext -> iValue )  // середина списка  {  // вставка в середину отсортированного списка или как последний элемент  current -> pNext  =  p -> pNext ;  p -> pNext  =  текущий ;  перерыв ;  // сделано }  p  =  p -> pNext ;  }  }  }  вернуть  голову ; }

В приведенном ниже алгоритме для вставки в отсортированный список используется конечный указатель [9] . Более простой рекурсивный метод перестраивает список каждый раз (а не сращивание) и может использовать пространство стека 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 ; }

Ссылки [ править ]

  1. ^ Б с д Бентли, Джон (2000), Программирование Pearls , ACM Пресс / Addison-Wesley, стр.  107 -109
  2. ^ Седжвик Роберт (1983), алгоритмы , Addison-Wesley, стр.  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. ^ Франк, RM; Лазарь, РБ (1960). «Процедура высокоскоростной сортировки». Коммуникации ACM . 3 (1): 20–22. DOI : 10.1145 / 366947.366957 .
  6. ^ Седжвик, Роберт (1986). «Новая верхняя граница для Shellsort». Журнал алгоритмов . 7 (2): 159–173. DOI : 10.1016 / 0196-6774 (86) 90001-5 .
  7. ^ "Сортировка двоичным слиянием"
  8. ^ Бендер, Майкл А .; Фарач-Колтон, Мартин ; Мостейро, Мигель А. (2006), «Сортировка вставкой - O ( n  log  n )», Теория вычислительных систем , 39 (3): 391–397, arXiv : cs / 0407003 , doi : 10.1007 / s00224-005-1237 -z , Руководство по ремонту 2218409 
  9. ↑ Hill, Curt (ed.), "Trailing Pointer Technique", Euler , Valley City State University , получено 22 сентября 2012 г..

Дальнейшее чтение [ править ]

  • Кнут, Дональд (1998), «5.2.1: Сортировка вставкой», Искусство компьютерного программирования , 3. Сортировка и поиск (второе издание), Addison-Wesley, стр. 80–105, ISBN 0-201-89685-0.

Внешние ссылки [ править ]

  • Анимированные алгоритмы сортировки: сортировка вставкой на Wayback Machine (архивировано 8 марта 2015 г.) - графическая демонстрация
  • Адамовский, Джон Пол, Сортировка двоичной вставкой - Табло - Полное исследование и реализация C , Pathcom.
  • Сортировка вставкой - сравнение с другими алгоритмами сортировки O (n 2 ) , UK : Core war.
  • Категория: Сортировка вставкой (вики), LiteratePrograms - реализации сортировки вставками на различных языках программирования