Основная идея сортировки вставками состоит в том, что при добавлении нового элемента в уже отсортированный список его стоит сразу вставлять в нужное место вместо того, чтобы вставлять его в произвольное место, а затем заново сортировать весь список. Сортировка вставками считает первый элемент любого списка отсортированным списком длины 1. Двухэлементный отсортированный список создается добавлением второго элемента исходного списка в нужное место одноэлементного списка, содержащего первый элемент. Теперь можно вставить третий элемент исходного списка в отсортированный двухэлементный список. Этот процесс повторяется до тех пор, пока все элементы исходного списка не окажутся в расширяющейся отсортированной части списка.
Вот алгоритм, реализующий этот процесс:
InsertionSort(list,N)
list сортируемый список элементов
N число элементов в списке
for i=2 to N do
newElement=list[i]
location=i-l
while(location >= 1) and (list [location]>newElement) do
// сдвигаем все элементы, большие очередного
list [location+l]=list[location]
location=location-l
end while
list[location+1]=newElement
end for
Этот алгоритм заносит новое вставляемое значение в переменную newElement. Затем он освобождает место для этого нового элемента, подвигая (в цикле while) все большие элементы на одну позицию в массиве. Последняя итерация цикла переносит элемент с номером location+1 в позицию location+2. Это означает, что позиция location+1
освобождается для «нового» элемента.Добавлено (14.03.2008, 23:03)
---------------------------------------------
Анализ наихудшего случая
Если посмотреть на внутренний цикл while, то видно, что наибольшее количество операций выполняется в случае, если вновь добавляемый элемент меньше всех элементов, содержащихся в уже отсортированной части списка. В этой ситуации выполнение цикла завершается, когда значение переменной location становится равным 0. Поэтому наибольшее количество работы алгоритм произведет, когда всякий новый элемент добавляется в начало списка. Такое возможно только, если элементы исходного списка идут в убывающем порядке. Это один возможный наихудший случай, однако бывают и другие. Посмотрим, как происходит обработка такого списка. Первым вставляется второй элемент списка. Он сравнивается всего с одним элементом. Второй вставляемый элемент (третий по порядку) сравнивается с двумя предыдущими, а третий вставляемый элемент — с тремя предыдущими; вообще, i-ый вставляемый элемент сравнивается с i предыдущими, и этот процесс повторяется N — 1 раз. Таким образом, сложность сортировки вставками в наихудшем случае равна.
