Сложность времени сортировки вставки

Sloznost Vremeni Sortirovki Vstavki

Рассмотрим следующие числа:

50 60 30 10 80 70 20 40



Если этот список отсортировать в порядке возрастания, это будет:



10 20 30 40 50 60 70 80



Если отсортировать по убыванию, то будет:

80 70 60 50 40 30 20 10

Сортировка вставками — это алгоритм сортировки, который используется для сортировки списка по возрастанию или по убыванию. В этой статье рассматривается только сортировка по возрастанию. Сортировка по убыванию следует той же логике, что и в этом документе. Цель этой статьи — объяснить сортировку вставками. Программирование выполняется в следующем примере на C. Сортировка вставками объясняется здесь с использованием одного массива.



Алгоритм сортировки вставками

Дан несортированный список. Цель состоит в том, чтобы отсортировать список в порядке возрастания, используя тот же список. Сортировка несортированного массива с использованием того же массива называется сортировкой на месте. Здесь используется нулевая индексация. Шаги следующие:

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

Иллюстрация сортировки вставками

При работе с временной сложностью обычно принимается во внимание наихудший случай. Худшее расположение для предыдущего списка:

80 70 60 50 40 30 20 10

Имеется восемь элементов с индексами от нуля до 7.

При нулевом индексе сканирование доходит до 80. Это одно движение. Одно это движение — операция. Всего пока одна операция (одно перемещение, без сравнения и без обмена). Результат:

| 80 70 60 50 40 30 20 10

По индексу один происходит движение к 70. 70 сравнивается с 80. 70 и 80 меняются местами. Одно движение - одна операция. Одно сравнение — это тоже одна операция. Один своп — это тоже одна операция. В этом разделе представлены три операции. Всего на данный момент выполнено четыре операции (1 + 3 = 4). Результат выглядит следующим образом:

70 | 80 60 50 40 30 20 10

По индексу два происходит движение к 60. 60 сравнивается с 80, затем 60 и 80 меняются местами. 60 сравнивается с 70, затем 60 и 70 меняются местами. Одно движение - одна операция. Два сравнения — это две операции. Два свопа — это две операции. В этом разделе представлены пять операций. Всего на данный момент выполнено девять операций (4 + 5 = 9). Результат выглядит следующим образом:

60 70 | 80 50 40 30 20 10

По индексу три происходит движение к 50. 50 сравнивается с 80, затем 50 и 80 меняются местами. 50 сравнивается с 70, затем 50 и 70 меняются местами. 50 сравнивается с 60, затем 50 и 60 меняются местами. Одно движение - одна операция. Три сравнения — это три операции. Три свопа — это три операции. В этом разделе представлены семь операций. Всего на данный момент выполнено шестнадцать операций (9 + 7 = 16). Результат выглядит следующим образом:

50 60 70 | 80 40 30 20 10

По индексу четыре происходит движение к 40. 40 сравнивается с 80, затем 40 и 80 меняются местами. 40 сравнивается с 70, затем 40 и 70 меняются местами. 40 сравнивается с 60, затем 40 и 60 меняются местами. 40 сравнивается с 50, затем 40 и 50 меняются местами. Одно движение - одна операция. Четыре сравнения — это четыре операции. Четыре свопа — это четыре операции. В этом разделе представлены девять операций. Всего на данный момент выполнено двадцать пять операций (16 + 9 = 25). Результат выглядит следующим образом:

40 50 60 70 80 | 30 20 10

По индексу пять происходит движение к 30. 30 сравнивается с 80, затем 30 и 80 меняются местами. 30 сравнивается с 70, затем 30 и 70 меняются местами. 30 сравнивается с 60, затем 30 и 60 меняются местами. 30 сравнивается с 50, затем 30 и 50 меняются местами. 30 сравнивается с 40, затем 30 и 40 меняются местами. Одно движение - одна операция. Пять сравнений — это пять операций. Пять свопов — это пять операций. В этом разделе представлены одиннадцать операций. Всего на данный момент выполнено тридцать шесть операций (25 + 11 = 36). Результат выглядит следующим образом:

30 40 50 60 70 80 | 20 10

По индексу шесть происходит движение к 20. 20 сравнивается с 80, затем 20 и 80 меняются местами. 20 сравнивается с 70, затем 20 и 70 меняются местами. 20 сравнивается с 60, затем 20 и 60 меняются местами. 20 сравнивается с 50, затем 20 и 50 меняются местами. 20 сравнивается с 40, затем 20 и 40 меняются местами. 20 сравнивается с 30, затем 20 и 30 меняются местами. Одно движение - одна операция. Шесть сравнений — это шесть операций. Шесть свопов — это шесть операций. В этом разделе представлены тринадцать операций. Всего пока выполнено сорок девять операций (36 + 13 = 49). Результат выглядит следующим образом:

20 30 40 50 60 70 80 | 10

По индексу семь происходит движение к 10. 10 сравнивается с 80, затем 10 и 80 меняются местами. 10 сравнивается с 70, затем 10 и 70 меняются местами. 10 сравнивается с 60, затем 10 и 60 меняются местами. 10 сравнивается с 50, затем 10 и 50 меняются местами. 10 сравнивается с 30, затем 10 и 40 меняются местами. 10 сравнивается с 30, затем 10 и 30 меняются местами. 10 сравнивается с 20, затем 10 и 20 меняются местами. Одно движение - одна операция. Семь сравнений — это семь операций. Семь свопов — это семь операций. В этом разделе представлены пятнадцать операций. Всего на данный момент выполнено шестьдесят четыре операции (49 + 15 = 64). Результат выглядит следующим образом:

10 20 30 40 50 60 70 80 10 |

Работа сделана! Было проведено 64 операции.

64 = 8 х 8 = 8 два

Временная сложность для сортировки вставками

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

На два )

Это использует нотацию Big-O. Обозначение Big-O начинается с O в верхнем регистре, за которым следуют круглые скобки. В скобках указано максимально возможное количество операций.

Кодирование на C

В самом начале сканирования первый элемент не может изменить свое положение. Программа по сути следующая:

#include

пустая вставкаСортировка ( инт А [ ] , целое N ) {
за ( инт я знак равно 0 ; я < Н; я++ ) {
интервал j = я;
пока ( А [ Дж ] < А [ j- 1 ] && j- 1 > знак равно 0 ) {
инт темп = А [ Дж ] ; А [ Дж ] = А [ j- 1 ] ; А [ j- 1 ] = температура; // менять
ж--;
}
}
}


В определении функции insertionSort() используется описанный алгоритм. Обратите внимание на условия цикла while. Подходящей основной функцией C для этой программы является:

внутренний основной ( целочисленный аргумент, символ ** argv )
{
инт п = 8 ;
инт А [ ] знак равно { 50 , 60 , 30 , 10 , 80 , 70 , 20 , 40 } ;

вставкаСортировка ( А, н ) ;

за ( инт я знак равно 0 ; я < н; я++ ) {
printf ( '%i' , А [ я ] ) ;
}
printf ( ' \n ' ) ;

возвращаться 0 ;
}

Вывод

Временная сложность сортировки вставками определяется как:

На два )

Читатель, возможно, слышал о временной сложности в худшем случае, временной сложности в среднем и временной сложности в лучшем случае. Эти варианты временной сложности сортировки вставками обсуждаются в следующей статье на нашем веб-сайте.