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

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

Основная идея сортировки вставками состоит в том, что при добавлении нового элемента в уже отсортированный список его стоит сразу вставлять в нужное место, а затем заново сортировать весь список. Сортировка вставками считает первый элемент любого списка отсортированным списком длины 1. Двухэлементный отсортированный список создается добавлением второго элемента исходного списка в нужное место одноэлементного списка, содержащего первый элемент. Теперь можно вставить третий элемент исходного списка в отсортированный двухэлементный список. Этот процесс повторяется до тех пор, пока все элементы исходного списка не окажутся в расширяющейся отсортированной части списка.
Вот алгоритм, реализующий этот процесс:

InsertionSort(list, N)
list		сортирующий список элементов
N			число элементов в списке
for i = 2 to N do
	newElement = list[i]
	location = i - 1
	while (location >= 1) and (list[location] > newElement) do
		//сдвигаем все элементы, большие очередного
		list[location + 1] = list[location]
		location = location - 1
	end while
	list[location + 1] = newElement
end for

Этот алгоритм заносит новое вставляемое значение в переменную newElement. Затем он освобождает место для этого нового элемента, подвигая (в цикле while) все большие элементы на одну позицию в массиве. Последняя итерация цикла переносит элемент с номером location + 1 в позицию location + 2. Это означает, что позиция location + 1 освобождается для "нового" элемента.

Сайт управляется системой uCoz