Сортировка вставками

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Пример сортировки вставками

Сортировка вставками — примитивный алгоритм сортировки с высокой вычислительной сложностью: O(n²).

Плюсы:

  • эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
  • эффективен на наборах данных, которые уже частично отсортированы;
  • это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
  • может сортировать список по мере его получения;
  • использует O(1) временной памяти, включая стек.
  • может работать значительно быстрее за счёт бинарного поиска

Минусы:

Описание[править | править вики-текст]

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

Анализ алгоритма[править | править вики-текст]

Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время выполняется сортировка. Также на время выполнения влияет исходная упорядоченность массива. Так, лучшим случаем является отсортированный массив, а худшим — массив, отсортированный в порядке, обратном нужному. Временная сложность алгоритма при худшем варианте входных данных — O(n²). Однако, данный алгоритм можно ускорить при помощи использования бинарного поиска для нахождения места текущему элементу в отсортированной части. Проблема с долгим сдвигом массива вправо решается при помощи смены указателей.

Псевдокод[1][править | править вики-текст]

Вход: массив A, состоящий из элементов A[0], A[1], A[2], ..., A[n]

for i = 1, 2, 3, ..., n:  
    curr := A[i]
    prevKey := i - 1
    while prevKey >= 0 and A[prevKey] > curr:
        A[prevKey+1] := A[prevKey]
        A[prevKey] := curr
        prevKey := prevKey-1

Примеры реализации[править | править вики-текст]

Java[править | править вики-текст]

 public static void insertionSort(int[] arr) {
     for(int i = 1; i < arr.length; i++){
         int currElem = arr[i];
         int prevKey = i - 1;
         while(prevKey >= 0 && arr[prevKey] > currElem){
             arr[prevKey+1] = arr[prevKey];
             arr[prevKey] = currElem;
             prevKey--; 
 
         }  
     }
 }

C++[править | править вики-текст]

template<class T> void InsertionSort(T *A, int N)
{
    if (N < 2) return;
 
    for (int i = 1; i < N; i++)
        for (int j = i; j && A[j] < A[j-1]; j--)
            std::swap(A[j], A[j-1]);
}

Примечания[править | править вики-текст]

  1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 2.1. Сортировка вставкой // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 57-64. — ISBN 5-8459-0857-4

См. также[править | править вики-текст]

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