Сортировка вставки - Insertion sort

Вставка сортировки
Вставка sort.gif
Анимация вставки сортировки
Класс Алгоритм сортировки
Структура данных Множество
Наихудшая производительность сравнения и свопы
Лучшая производительность сравнения, свопы
Средняя производительность сравнения и свопы
Сложность пространства в наихудшем случае общая, вспомогательная

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

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

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

Алгоритм

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

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

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

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

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

становится

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

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

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

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

Далее следует псевдокод полного алгоритма, где массивы отсчитываются от нуля : 

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

Внешний цикл проходит по всем элементам, кроме первого, потому что одноэлементный префикс 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]в свою позицию за один раз и выполняет только одно присваивание в теле внутреннего цикла: 

i ← 1
while i < length(A)
    x ← A[i]
    j ← i - 1
    while j >= 0 and A[j] > x
        A[j+1] ← A[j]
        j ← j - 1
    end while
    A[j+1] ← x
    i ← i + 1
end while

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

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

function insertionSortR(array A, int n)
    if n > 0
        insertionSortR(A, n-1)
        x ← A[n]
        j ← n-1
        while j >= 0 and 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 2 )).

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

Пример: В следующей таблице показаны шаги для сортировки последовательности {3, 7, 4, 9, 5, 2, 6, 1}. На каждом этапе рассматриваемый ключ подчеркивается. Ключ, который был перемещен (или оставлен на месте, потому что он был самым большим из всех, что рассматривался) на предыдущем шаге, отмечен звездочкой. 

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

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

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

Варианты

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

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

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

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

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

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

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

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

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

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

struct LIST * SortList1(struct LIST * pList) 
{
    // zero or one element in list
    if (pList == NULL || pList->pNext == NULL)
        return pList;
    // head is the first element of resulting sorted list
    struct LIST * head = NULL;
    while (pList != NULL) {
        struct LIST * current = pList;
        pList = pList->pNext;
        if (head == NULL || current->iValue < head->iValue) {
            // insert into the head of the sorted list
            // or as the first element into an empty sorted list
            current->pNext = head;
            head = current;
        } else {
            // insert current element into proper position in non-empty sorted list
            struct LIST * p = head;
            while (p != NULL) {
                if (p->pNext == NULL || // last element of the sorted list
                    current->iValue < p->pNext->iValue) // middle of the list
                {
                    // insert into middle of the sorted list or as the last element
                    current->pNext = p->pNext;
                    p->pNext = current;
                    break; // done
                }
                p = p->pNext;
            }
        }
    }
    return head;
}

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

struct LIST
{
  struct LIST * pNext;
  int           iValue;
};

struct LIST * SortList(struct LIST * pList)
{
  // zero or one element in list
  if (!pList || !pList->pNext)
      return pList;

  /* build up the sorted array from the empty list */
  struct LIST * pSorted = NULL;

  /* take items off the input list one by one until empty */
  while (pList != NULL) {
      /* remember the head */
      struct LIST *   pHead  = pList;
      /* trailing pointer for efficient splice */
      struct LIST ** ppTrail = &pSorted;

      /* pop head off list */
      pList = pList->pNext;

      /* splice head into sorted list at proper place */
      while (!(*ppTrail == NULL || pHead->iValue < (*ppTrail)->iValue)) { /* does head belong here? */
          /* no - continue down the list */
          ppTrail = &(*ppTrail)->pNext;
      }

      pHead->pNext = *ppTrail;
      *ppTrail = pHead;
  }

  return pSorted;
}

использованная литература

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

внешние ссылки