Сортировка простыми вставками.

Этот метод - "дословная" реализации стратегии включения. Порядок алгоритма сортировки простыми вставками - O(N^2), если учитывать только операции сравнения. Но сортировка требует еще и в среднем N^2/4 перемещений, что де- лает ее в таком варианте значительно менее эффективной, чем сортировка выборкой.

Алгоритм сортировки простыми вставками иллюстрируется программным примером 3.11.

{===== Программный пример 3.11 =====} Procedure Sort(a : Seq; var b : Seq); Var i, j, k : integer; begin for i:=1 to N do begin { перебор входного массива } { поиск места для a[i] в выходном массиве } j:=1; while (j < i) and (b[j]

Эффективность алгоритма может быть несколько улучшена при применении не линейного, а дихотомического поиска. Однако, следует иметь в виду, что такое увеличение эффективности может быть достигнуто лишь на множествах значительного по количеству элементов объема. Т.к. алгоритм требует большого числа пересылок, при значительном объеме одной записи эффективность может определяться не количеством операций сравнения, а количеством пересылок.

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