Сортировка вставками
презентация к уроку по информатике и икт (10 класс)

Слайд 1

Сортировка вставкой на языке программирования Pascal

Слайд 2

Принцип метода Массив разделяется на 2 части: отсортированную и неотсортированную. Элементы из неотсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы в качестве отсортированной части массива принимают только один первый элемент, а в качестве неотсортированной части - все остальные элементы.

Слайд 3

Алгоритм состоит из n-1 прохода: взятие очередного i-го неотсортированного элемента и сохранение его в дополнительной переменной; поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов; сдвиг элементов массива с i-1 -го до j-1 -го вправо, чтобы освободить найденную позицию вставки; вставка взятого элемента в найденную j -ю позицию.

Слайд 4

Схема метода: 3 1 9 2 5 7 1 2 3 4 5 n=6 1 1. 1 3 9 2 5 7 1 2 3 4 5 n=6 9 2.

Слайд 5

Схема метода: 1 3 9 2 5 7 1 2 3 4 5 n=6 2 3. 1 2 3 9 5 7 1 2 3 4 5 n=6 5 4

Слайд 6

Схема метода: 1 2 3 5 9 7 1 2 3 4 5 n=6 2 5. 1 2 3 5 9 7 1 2 3 4 5 n=6 Результат:

Слайд 7

Программа: For i := 2 to n do begin b:=a[i]; взятие неотсортированного эл-та j:=1; while b>a[j] do j:=j+1; нашли позицию для вставки for k:= i-1 downto j do a[k+1]:=a[k]; осуществили сдвиг a[j]:=b; end;

Слайд 8

Пример:

Слайд 9

Источники: Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%81%D1%82%D0%B0%D0%B2%D0%BA%D0%B0%D0%BC%D0%B8 http://upload.wikimedia.org/wikipedia/commons/0/0f/Insertion-sort-example-300px.gif