VI. Метод вставок

Отсортированный массив создаётся заново, сначала он пуст. На каждом шаге очередной элемент несортированного массива помещается на соответствующее место в сортированном массиве. Для этого отсортированный массив просматривается начиная с текущего элемента до первого, пока не найдётся место новому элементу и т.д., пока все отсортированные элементы с меньшими значениями не окажутся впереди его, а с большими значениями- после него.

Рис. 7

Вставка в другой массив

A= 4 5 1 2 3

i	к	A(j)	B(к)	B
				4 5 x x x
				4 5 5 x x
				4 4 5 x x
				1 4 5 x x

Рис. 8

Вставка в том же массиве

A= 4 5 1 2 3

i	s	k	A(k)	A
				4 5 1 2 3
				4 5 1 2 3 4 4 5 2 3 1 4 5 2 3
				1 4 5 5 3 1 4 4 5 3 1 2 4 5 3
				1 2 4 5 5 1 2 4 4 5 1 2 3 4 5

Рис. 9

Оценка метода вставок

»n²/4

Min - n

Max - n²/2

Плюсы:

· прост в реализации

· на наборах данных до десятков элементов может оказаться лучшим

· эффективен на наборах данных, которые уже частично отсортированы

· это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы)

· может сортировать список по мере его получения

· не требует временной памяти, даже под стек

Минусы:

· не эффективен на больших наборах данных

Дата добавления: 2015-11-30