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

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

Сортировка вставками — примитивный алгоритм сортировки с высокой вычислительной сложностью: 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];
            prevKey--; 
        }
        arr[prevKey+1] = currElem;
    }
}

Примечания[править | править исходный текст]

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

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]