i21прим/Docu.Пошаговая разработка/1. Вставки.odc

1. Пошаговая разработка: Сортировка вставками

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


Решение

Построение программы происходит в несколько шагов, каждому из которых посвящена отдельная часть документа:

ЧастьЏА  Постановка задачи. Проектирование интерфейса
ЧастьЏБ  Разработка тела процедуры. Сведение задачи к более простой подзадаче
ЧастьЏВ  Реализация процедуры Вставить
ЧастьЏГ  Демонстрация работы
ЧастьЏД  Замена рекурсии на цикл


Часть А. Постановка задачи. Проектирование интерфейсов

Поскольку о задаче сказано в самом общем виде, необходимо принять ряд решений проектного характера.

Во-первых, сделаем процедуру частью отдельного модуля, который назовем Вставки. Модуль сделаем частью подсистемы i21прим. 
Соответственно полное имя модуля будет i21примВставки. 
(Напомним, что в Компонентном Паскале большие и малые буквы различаются  причем те и другие можно использовать в идентификаторах.)
			Опроцедурахимодулях
			ОподсистемахБлэкбокса
			Обидентификаторах
			
Уже можно написать первый вариант модуля. Для этого откроем новый чистый документ (с клавиатуры Ctrl+N или через меню Файл --> Новый) и напечатаем там одну букву:

m

Зеленый цвет используется только в данном описании для пометки новых фрагментов программного текста. При выполнении описываемых действий не нужно раскрашивать в зеленый цвет свой документ.
		ОбиспользованиицветавпрограммахБлэкбокса

Напечатав букву m, сразу нажмем клавишу F5. Получится следующий текст:

MODULE ;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
END.

Слова вроде MODULE, состоящие только из больших букв, относятся к числу ключевых слов языка Компонентный Паскаль. Ключевые слова пишутся только большими буквами и их нельзя использовать в качестве идентификаторов. (Их полный список дан в Сообщении о языке.)

Вторая строка, начинающаяся после отступа словом IMPORT, содержит через запятую имена модулей, которые будут использоваться в программе. В зависимости от настроек вставляться могут разные списки модулей. Здесь показан некий часто встречающися вариант. Для двух из трех модулей введены сокращенные имена (Log вместо StdLog и In вместо i21sysIn); эти сокращенные имена должны использоваться всюду в тексте модуля. Log помогает печатать данные в рабочий журнал (см. об истории названия слова Log), а In  вводить данные. Math содержит простые математические функции (синусы, логарифмы и т.п.).
На самом деле наша текущая задача настолько простая, что ни один из этих модулей не понадобится, и эту строку можно было бы стереть, но мы не будем этого делать.

Курсор будет мигать в первой строке непосредственно перед точкой с запятой  в точности там, где нужно теперь напечатать имя модуля; так и поступим. 
Получится следующий текст:

MODULE  i21примВставки;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
END.

Теперь скопируем имя модуля в позицию перед точкой через пробелы от слова END.
Удобная последовательность действий такова: 
	дважды кликнем мышкой по только что напечатанному имени модуля, 
	нажмем Ctrl+C, 
	нажмем Ctrl+K (см. ниже об этой важной горячей клавише), 
	нажмём клавишу пробела (по клавише пробела удобнее всего "стучать" большим пальцем любой руки; полезно выработать у себя такую привычку), 
	нажмем Ctrl+V, 
	снова нажмем Ctrl+K. 

Получится текст:

MODULE i21примВставки;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
END i21примВставки.

Мы выделили имя модуля жирным шрифтом (двойной клик по имени, потом нажать Ctrl+B). Компилятор игнорирует жирный шрифт, курсив, цвета и т.п.  всё это можно использовать для облегчения визуальной ориентации в программном тексте.

То, что у нас получилось  уже полноценный модуль, который можно компилировать (хотя выполнять там пока нечего).

Нужно стремиться к тому, чтобы после каждого шага уточнения получался модуль, который компилируется без ошибок. 

Это позволяет задействовать возможности компилятора, чтобы обнаружить ошибки как можно раньше: 

Чем позже обнаруживается ошибка, 
тем труднее ее искать и исправлять.

Скомпилируем модуль (Ctrl+K; напомним, что здесь K  латинское, и что переключать клавиатуру с русской на латинскую для выполнения команд Ctrl не нужно).
			Окомпиляции

Сохраним модуль (Ctrl+S или Файл --> Сохранить) в папке i21прим\Mod\ с именем Простые (стандартный суффикс .odc система добавит автоматически). 

В дальнейшем мы не будем повторять, что полезно периодически сохранять файл (достаточно нажимать Ctrl+S).

Еще полезно сохранять промежуточные варианты программы с другими именами (например, добавляя последовательные номера в конце имени файла). Для этого имеется удобная команда меню Файлы --> Сохранить копию как ... (Files --> Save Copy As ...).

Теперь выберем имя для процедуры, которую требуется построить. 
Чтобы отразить смысл процедуры в ее имени, назовем ее, скажем, Сорт.

Создадим остов процедуры. Для этого:
 кликнем мышкой в пустом пространстве после точки с запятой в строчке IMPORT, курсор должен встать после точки с запятой; 
 нажмем клавишу ввода дважды  добавятся две новые строки, причем в начале каждой новой строки автоматически вставляется столько же символов табуляции, сколько их было в начале предыдущей (в нашем случае один; чтобы на них посмотреть, нажать Ctrl+H; нажать Ctrl+H еще раз, чтобы спрятать);  наберем латинскую букву p, после чего текст будет выглядеть след. образом, с курсором сразу после procedure:

MODULE  i21примВставки;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
	p
	
END  i21примВставки.

Нажатие клавиши-помощницы F5 превратит этот текст в следующий:

MODULE  i21примВставки;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
	PROCEDURE  ();
		VAR  
	BEGIN
		
	END;

END  i21примВставки.

При этом курсор будет стоять точно там, где требуется напечатать имя процедуры. Сделаем это, обращая внимание на большие и маленькие буквы:

MODULE  i21примВставки;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
	PROCEDURE Сорт ();
		VAR  
	BEGIN
		
	END;
	
END  i21примВставки.

Сразу скомпилируем модуль (Ctrl+K). Компилятор поставит после END в конце процедуры черный квадратик, что говорит об ошибке в этой точке программы. 
В левой части статусной полоски внизу окна Блэкбокса появится сообщение "ожидается идентификатор" (identifier expected). 
Действительно, по правилам Компонентного Паскаля имя процедуры должно быть повторено после соответствующего END (это изменение по сравнению со старым Паскалем упрощает разработку сложных программ со многими END и многими процедурами).

Скопируем имя процедуры в позицию непосредственно перед символом ";" в конце процедуры так же, как в случае с модулем (двойной клик по имени, копируем в буфер обмена посредством Ctrl+C, компилируем посредством Ctrl+K, бьем большим пальцем по клавише пробела, вставляем имя посредством Ctrl+V). 
Получим следующий модуль, который должен компилироваться без ошибок:

MODULE  i21примВставки;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
	PROCEDURE Сорт ();
		VAR  
	BEGIN
		
	END Сорт;
	
END  i21примВставки.

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

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

Здесь следует понять следующее:
(1) разрешается ли нашей процедуре менять содержимое исходного массива;
(2) следует ли возвращать отсортированный результат в новом массиве.

Поскольку всё это в условии задачи не оговорено, а алгоритм сортировки вставками может быть выполнен непосредственно в исходном массиве, то примем простейший вариант: определим у процедуры один параметр, являющийся массивом с исходными данными, и в том же самом массиве вернем результат. 
Это значит, что массив должен передаваться "по ссылке", причем из трех возможных в этом случае атрибутов (IN, OUT, VAR) следует выбрать VAR (в случае IN запрещено менять элементы массива, а атрибут OUT можно применять, только если процедура не использует старых значений элементов массива, а просто заполняет его новыми).

Далее, каков тип элементов массива? Ведь в Компонентном Паскале есть 4 целых типа (INTEGER, SHORTINT, LONGINT, BYTE). Поскольку в условии задачи ничего на этот счет на сказано, выберем наиболее универсальный и простой в работе тип INTEGER (что соответствует 4 байтам или 32 битам или диапазону от примерно плюс два миллиарда до примерно минус два миллиарда).

Наконец, размер массива в условии задачи также не указан. Но процедуры вроде сортировки имеют универсальный характер, и применимы к массивам любого размера. Поэтому оставим наш единственный массив-параметр открытым, т.е. не будем указывать в описании его размер. Длину такого массива в процедуре всегда можно получить, обратившись к предопределенной процедуре-функции LEN, указав массив в качесте ее аргумента.

Имя параметру-массиву дадим произвольно,  например, пусть это будет a (латинское). 
Внимание! Латинское a и русское а  для компилятора два разных символа, хотя на вид во многих шрифтах они не отличаются. 
Мы предпочли латинскую букву, чтобы не переключать клавиатуру ради одной буквы при наборе программного текста.

Опишем массив между скобками в заголовке процедуры:

MODULE  i21примВставки;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
	PROCEDURE Сорт ( VAR a: ARRAY OF INTEGER );
		VAR  
	BEGIN
		
	END Сорт;
	
END  i21примВставки.

Если не допущено опечаток, то модуль должен компилироваться без ошибок.

О пробелах вокруг списка параметров: такие пробелы заметно улучшают читабельность, а это важно: глаз должен по возможности без усилий "разбирать" структуру программы. Особенно это важно при небольшом размере шрифта  обычно хочется побольше видеть на экране. Насколько отсутствие таких пробелов затрудняет зрительное восприятие, легко почуствовать, читая тексты исходников Блэкбокса [например, дважды кликнуть по StdLog и нажать Ctrl+0, найти там длинные строки без единого пробела].

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

MODULE  i21примВставки;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
	PROCEDURE Сорт* ( VAR a: ARRAY OF INTEGER );
		VAR  
	BEGIN
		
	END Сорт;
	
END  i21примВставки.

Имя процедуры мы выделили жирным шрифтом (двойной клик, Ctrl+B), чтобы легче было ориентироваться в тексте модуля. Компилятор такие украшения текста игнорирует.

Первая успешная компиляция после проставления звездочки должна сопровождаться сообщением в рабочем журнале "Сорт is new in symbol file". 
Не вдаваясь в смысл сообщения, скажем лишь, что компилятор всегда пишет подобные сообщения в случае изменений интерфейса модуля (изменение имен и сигнатур экспортируемых объектов, их добавление и удаление, отмена экспорта и т.п.). Это очень важно в профессиональной работе, так как проектирование интерфейсов модулей  одна из ключевых задач в создании программного обеспечения.

На этом заканчивается перевод постановки задачи на язык программирования.

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


Часть Б. Разработка тела процедуры. Сведение задачи к более простой подзадаче

Алгоритм заключается в том, чтобы продвигаться по массиву (скажем, по возрастанию индекса элементов) и вставлять очередной элемент в предшествующий ему сегмент массива так, чтобы сегмент оставался упорядоченным.

Фраза "продвигаться по массиву" подразумевает, что у нас должен быть индекс, показывающий, в каком месте массива мы находимся в данный момент.
Назовем его j; т.к. это целое число, объявим его как INTEGER (напечатать i, потом нажать F5):

MODULE  i21примВставки;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
	PROCEDURE Сорт* ( VAR a: ARRAY OF INTEGER );
		VAR  j: INTEGER;
	BEGIN
		
	END Сорт;
	
END  i21примВставки.

Сразу скомпилируем модуль, чтобы убедиться, что не допущено опечаток.

Теперь алгоритм можно описать так: на очередном шаге мы берем элемент a[j] и, считая, что сегмент массива a[0] .. a[j-1] уже отсортирован, добиваемся того, чтобы стал отсортирован сегмент a[0] .. a[j]. 
Пока мы не обсуждаем, как именно мы добъемся, чтобы стал отсортирован сегмент a[0] .. a[j]  однако ясно, что эта задача проще, чем задача полной сортировки  ведь сегмент a[0] .. a[j-1] уже отсортирован.

В этом месте очень важно четко понять следующее: после того как мы разберемся с элементом a[j] и перейдем к обработке следующего элемента, увеличив j на единицу, ситуация будет выглядеть точно так же, как и перед обработкой предыдущего элемента: снова обрабатываться будет элемент a[j], а сегмент слева от него будет уже отсортирован и т.д.
Говоря профессиональным языком: утверждение, что сегмент a[0] .. a[j-1] отсортирован, является инвариантом цикла. Оно справедливо в начале каждого шага цикла. Именно это гарантирует в дальнейшем правильность цикла.

Поскольку мы хотим пройтись по всему массиву элемент за элементом, то можно использовать цикл FOR с управляющей переменной j (кликнем в пустую строку примерно под VAR (курсор должен встать вровень с буквой V слова VAR), напечатаем for, нажмем F5, нажмем j):

MODULE  i21примВставки;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
	PROCEDURE Сорт* ( VAR a: ARRAY OF INTEGER );
		VAR  j: INTEGER;
	BEGIN
		FOR  j :=   TO    DO
			
		END;
	END Сорт;
	
END  i21примВставки.

Какими должны быть начальное и конечное значения для j?

Начальный элемент массива в Компонентном Паскале всегда имеет нулевой индекс.
Так как сегмент из единственного элемента всегда сам по себе отсортирован, то можно начинать сразу с j, равного 1. Действительно: сегмент слева от a[1] состоит из единственного элемента a[0] и поэтому автоматически отсортирован, так что первый шаг цикла будет начинаться корректно.

Последний элемент цикла в Компонентном Паскале всегда имеет индекс, равный LEN(a) - 1, где LEN  стандартная процедура-функция, её значение равно количеству элементов массива; т.к. нумерация начинается с нуля, то индекс последнего элемента на единицу меньше, чем значение LEN.
На последнем шаге цикла мы должны разобраться с последним элементом массива. В итоге получаем следующий цикл:

MODULE  i21примВставки;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
	PROCEDURE Сорт* ( VAR a: ARRAY OF INTEGER );
		VAR  j: INTEGER;
	BEGIN
		FOR  j := 1  TO  LEN(a) - 1  DO
			
		END;
	END Сорт;
	
END  i21примВставки.

Помним, что на каждом шаге цикла нужно вставить a[j] в правильное место упорядоченного сегмента a[0] .. a[j-1], т.е. так, чтобы сегмент a[0] .. a[j] стал упорядоченным. Это гарантирует, что на каждом шаге цикла будет воспроизводиться одна и та же ситуация (будет выполнен инвариант цикла), и по завершении цикла мы получим нужный результат.

Компилируем и исправляем опечатки. 

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

В пустой строке в теле цикла напечатаем вызов процедуры, оставив место для параметров:

MODULE  i21примВставки;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
	PROCEDURE Сорт* ( VAR a: ARRAY OF INTEGER );
		VAR  j: INTEGER;
	BEGIN
		FOR  j := 1  TO  LEN(a) - 1  DO
			Вставить(  )
		END;
	END Сорт;
	
END  i21примВставки.

Как и в старом Паскале, после вызова процедуры Вставить (после закрывающей скобки) точка с запятой отсутствует. Но в отличие от старого Паскаля, в Компонентном Паскале точку с запятой в этом месте разрешено ставить, если хочется. Подробнее об этом см. здесь. 

Сразу скомпилируем. Компилятор поставит черный квадратик после слова Вставить, в рабочем журнале появится сообщение "найдена одна ошибка", а слева внизу окна Блэкбокса появится сообщение "необъявленный идентификатор". В самом деле, процедуру Вставить мы еще не описали, и компилятор не знает, что это такое.

Определение новой процедуры проще всего поставить перед процедурой Сорт. 
			Опорядкеопределенияпроцедур

Поставим курсор непосредственно перед первой буквой слова PROCEDURE, нажмем ввод дважды, нажмем дважды стрелочку вверх, напечатаем латинскую p, нажмем F5, напечатаем имя процедуры Вставить, скопируем его в конец процедуры (не забыв про пробел после END). Получим:

MODULE  i21примВставки;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
	PROCEDURE Вставить (  );
		VAR  
	BEGIN
		
	END Вставить;
	
	PROCEDURE Сорт* ( VAR a: ARRAY OF INTEGER );
		VAR  j: INTEGER;
	BEGIN
		FOR  j := 1  TO  LEN(a) - 1  DO
			Вставить(  )
		END;
	END Сорт;
	
END  i21примВставки.

Эта версия модуля компилируется без ошибок.
Заметим, что новая процедура не экспортируется  в этом нет нужды, т.к. это чисто вспомогательная процедура (мы даже могли бы упрятать ее внутрь процедуры Сорт).

Теперь подумаем о параметрах новой процедуры. Объявления двух процедур полностью независимы (их тексты никак не пересекаются), поэтому ни одна из них не может знать, что происходит внутри другой. Поэтому, чтобы процедура Вставить могла что-то сделать с массивом a, его следует передать ей в качестве фактического параметра. Рассуждая как при разработке сигнатуры процедуры Сорт, приходим к выводу, что у процедуры Вставить должен быть такой же параметр для передачи массива, как и у процедуры Сорт. Достаточно просто скопировать объявление параметра из заголовка процедуры Сорт в заголовок процедуры Вставить:

MODULE  i21примВставки;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
	PROCEDURE Вставить ( VAR a: ARRAY OF INTEGER );
		VAR  
	BEGIN
		
	END Вставить;
	
	PROCEDURE Сорт* ( VAR a: ARRAY OF INTEGER );
		VAR  j: INTEGER;
	BEGIN
		FOR  j := 1  TO  LEN(a) - 1  DO
			Вставить(  )
		END;
	END Сорт;
	
END  i21примВставки.

Разумеется, имена параметров в двух процедурах совершенно независимы  мы могли бы дать параметру в процедуре Вставить другое имя, например, b.

Попробуем скомпилировать модуль  появится черный квадратик уже внутри скобок в теле цикла, а сообщение слева внизу экрана будет "фактических параметров меньше, чем формальных". В самом деле, раз параметр задан в описании процедуры Вставить, то при вызове на его место нужно что-то поставить. Ясно, что в нашем случае нужно поставить идентификатор массива a, поскольку именно с ним должна поработать процедура Вставить:

MODULE  i21примВставки;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
	PROCEDURE Вставить ( VAR a: ARRAY OF INTEGER );
		VAR  
	BEGIN
		
	END Вставить;
	
	PROCEDURE Сорт* ( VAR a: ARRAY OF INTEGER );
		VAR  j: INTEGER;
	BEGIN
		FOR  j := 1  TO  LEN(a) - 1  DO
			Вставить( a )
		END;
	END Сорт;
	
END  i21примВставки.

Теперь все компилируется без ошибок.
		
Но процедура Вставить должна не просто поработать с массивом a  она должна поработать с его j-м элементом. Передать ей эту информацию можно, поставив в качестве второго фактического параметра значение переменной j. 
Но тогда второй параметр должен быть правильно описан в заголовке процедуры Вставить. Этот параметр должен, во-первых, иметь тип INTEGER (т.к. именно этот тип имеет переменная j, значение которой мы хотим передавать). 
Во-вторых, переменная j, объявленная внутри Сорт, должна быть защищена в том смысле, что процедура Вставить не должна иметь возможности изменить ее. Поэтому параметр должен передаваться по значению, т.е. быть описан без атрибута VAR. Напечатаем все это, дав параметру другое имя во избежание путаницы:

MODULE  i21примВставки;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
	PROCEDURE Вставить ( VAR a: ARRAY OF INTEGER;  i: INTEGER );
		VAR  
	BEGIN
		
	END Вставить;
	
	PROCEDURE Сорт* ( VAR a: ARRAY OF INTEGER );
		VAR  j: INTEGER;
	BEGIN
		FOR  j := 1  TO  LEN(a) - 1  DO
			Вставить( a, j )
		END;
	END Сорт;
	
END  i21примВставки.

Компилируем модуль  ошибок быть не должно.

Подчеркнем, что процедура Сорт полностью закончена. Задача теперь свелась к написанию тела процедуры Вставить. 


Часть В. Реализация процедуры Вставить

Процедура Вставить предполагает, что уже отсортирован сегмент массива слева от a[j]  т.е. сегмент a[0] .. a[j-1]. Задача процедуры Вставить  вставить значение элемента a[j] в этот сегмент так, чтобы сегмент a[0] .. a[j] тоже оказался отсортирован.

Введем обозначения для значений массива на момент начала выполнения процедуры Вставить:
пусть a'[k]  значение, которое содержалось в k-м элементе массива;
а значение, которое содержалось в элементе a[j], пусть будет X.

Значения элементов сегмента a[0] .. a[j-1] расположены в порядке неубывания:

		a'[0] <= a'[1] <= ... <= a'[j-1]  ?  X
			0	1	...	j-1	j

В нижней строке показаны соответствующие значения индексов. В частности, значение X хранится в ячейке a[j]. Вопросительный знак показывает, что мы не знаем, в каком отношении находятся a'[j-1] и X.

Теперь представим себе, что должно получиться после завершения процедуры  значение X должно найти свое правильное место среди упорядоченной цепочки a'[0] .. a'[j-1], т.е. должно получиться такое расположение значений:

		a'[0] <= .. <= a'[n] <= X <  ...				a'[j-1]
			0	n	n+1	j

Другими словами, все элементы, которые были <= X, останутся на своих местах,
а остальные (большие X) сдвинутся вправо на одну позицию. 
Мы, конечно, заранее не знаем, каково n.

Картинки такого рода, несмотря на всю их полезность, обладают одним большим недостатком: можно легко забыть об особых случаях, для изображения которых требуются отдельные картинки  даже если такие случаи охватываются чисто логическими рассуждениями. В данной ситуации это особые случаи n=j и n=-1 (все элементы слева от a[j] не больше, или наборот, все больше, чем X). О таких особых случаях всегда нужно помнить и проверять их отдельно  даже если чисто логически рассуждение построено так, что оно охватывает эти случаи.

Так и построим алгоритм. Начинаем в состоянии, когда значения расположены так, как уже было описано:

		a'[0] <= a'[1] <= ... <= a'[j-1]  ?  X
			0	1	...	j-1	j

Затем сравним значение X (а фактически значение из ячейки a[j]) c a[j-1]. 
Если окажется, что X меньше, то поменяем местами значения ячеек a[j-1] и a[j]. Получим следующее расположение значений:

		a'[0] <= a'[1] <= ... <= a'[j-2]  ?  X <= a'[j-1]
			0	1	...	j-2	j-1	j

и после этого получается точно такая же задача, как и та, с которой мы начали, но с j-1 вместо j.
В противном случае (т.е. если X оказалось не меньше, чем a[j-1]) имеем следующую ситуацию:

		a'[0] <= a'[1] <= ... <= a'[j-1] <= X
			0	1	...	j-1	j

так что ничего больше делать не надо, т.к. сегмент a[0] .. a[j] уже правильно отсортирован.

Эти рассуждения можно немедленно реализовать следующим образом (кликнуть в пустую строку между BEGIN и END в процедуре Вставить примерно под VAR, напечатать if, нажать F5, и т.д.):

MODULE  i21примВставки;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
	PROCEDURE Вставить ( VAR a: ARRAY OF INTEGER;  i: INTEGER );
		VAR  
	BEGIN
		IF  a[i] < a[i-1]  THEN
			(* переставить значения a[i] и a[i-1] *)
			Вставить( a, i-1 )
		ELSE
			(* делать нечего *)
		END;
	END Вставить;
	
	PROCEDURE Сорт* ( VAR a: ARRAY OF INTEGER );
		VAR  j: INTEGER;
	BEGIN
		FOR  j := 1  TO  LEN(a) - 1  DO
			Вставить( a, j )
		END;
	END Сорт;
	
END  i21примВставки.

Обдумаем то, что мы написали.

1) Заметим, что в процедуре Вставить за словом VAR никаких объявлений нет  но это разрешено, ведь модуль компилируется успешно. Можно было бы эту строку и стереть, но раздел объявлений нам еще понадобится  оставим его пока как есть.

2) Вместо комментария после THEN нужно будет написать соответствующие команды. Пока отложим это.

3) Мы написали вызов процедуры вставить внутри нее самой  другими словами, процедура Вставить получилась рекурсивной. В этом ничего страшного нет и в Компонентном Паскале все процедуры могут вызывать себя и друг друга. Но важно обеспечить, чтобы рекурсия не оказалась бесконечной. Заметим себе этот пункт  он здесь самый важный.

4) Пустую ветвь ELSE условного оператора можно удалить.

Сначала сделаем самое легкое  удалим пустую ветвь ELSE: отметим мышкой текст от начала ELSE до начала END и нажмем клавишу Delete. Должно получиться следующее:

MODULE  i21примВставки;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
	PROCEDURE Вставить ( VAR a: ARRAY OF INTEGER;  i: INTEGER );
		VAR  
	BEGIN
		IF  a[i] < a[i-1]  THEN
			(* переставить значения a[i] и a[i-1] *)
			Вставить( a, i-1 )
		END;
	END Вставить;
	
	PROCEDURE Сорт* ( VAR a: ARRAY OF INTEGER );
		VAR  j: INTEGER;
	BEGIN
		FOR  j := 1  TO  LEN(a) - 1  DO
			Вставить( a, j )
		END;
	END Сорт;
	
END  i21примВставки.

Разобраться с замечанием 2) тоже легко. Перестановка значений двух переменных реализуется обычным образом с помощью вспомогательной переменной. Выберем для нее имя  например, t  и объявим ее в (пока пустом) разделе объявлений процедуры Вставить. Тип t должен быть таким же, как и у переменных, значения которых мы переставляем, т.е. INTEGER. После этого команды, выполняющие перестановку, пишутся легко, и процедура Вставить получается такой:
		
	PROCEDURE Вставить ( VAR a: ARRAY OF INTEGER;  i: INTEGER );
		VAR  t: INTEGER;
	BEGIN
		IF  a[i] < a[i-1]  THEN
			t := a[i];  a[i] := a[i-1];  a[i-1] := t;
			Вставить( a, i-1 )
		END;
	END Вставить;

Теперь обратимся к самому важному замечанию 3): корректное окончание цепочки рекурсивных вызовов:

		Вставить( a, j ) --> Вставить( a, j-1 ) --> Вставить( a, j-2 ) --> ...
		--> Вставить( a, 1 ) --> Вставить( a, 0 ) --> Вставить( a, -1 ) --> ...

Процедура в том виде, как она написана, будет пытаться выполнить всю эту бесконечную цепочку. Но применение метода пристального разглядывания показывает, что уже при значении второго параметра, равном нулю (i = 0), в теле процедуры Вставить будет сделана попытка обратиться к элементу массива с индексом i - 1 = -1, а таких элементов не существует. Обдумаем эту ситуацию, для этого вспомним, что должна делать процедура Вставить.

Мы условились, что процедура Вставить должна оставлять после себя отсортированный сегмент, последним элементом которого является a[i]. Но при i=0 этот сегмент состоит из единственного элемента a[0], а такой сегмент автоматически отсортирован, так что процедура в этом случае просто ничего делать не должна. Чтобы обеспечить это, "охватим" все выполняемое тело процедуры Вставить условным оператором IF  i = 0  THEN ... и т.д.

Последовательность действий такова: 
	поставить курсор непосредственно перед IF; 
	нажать клавишу ввода; 
	стрелку вверх; 
	набрать if; 
	нажать F5; 
	набрать i > 0; 
	выделить целиком 4 строки второго оператора IF (например, поставить курсор в любое место строки IF  a[i] ..., нажать клавишу Home, с нажатой клавишей Shift четырежды нажать стрелку вниз и отпустить Shift); 
	нажать F12  все четыре строки должны сдвинуться на один отступ вправо (в начале строк автоматически вставляются символы табуляции; заметим, что клавиша F11 действует в противоположном направлении  но нажимать ее сейчас не надо);
	нажать Ctrl+X (вырезать 4 строки в буфер обмена); 
	нажать один раз стрелку вверх; 
	с нажатой клавишей Shift трижды нажать стрелку вверх и отпустить Shift; 
	нажать Ctrl+V. 
Результат должен быть таким:
	
	PROCEDURE Вставить ( VAR a: ARRAY OF INTEGER;  i: INTEGER );
		VAR  t: INTEGER;
	BEGIN
		IF  i > 0  THEN
			IF  a[i] < a[i-1]  THEN
				t := a[i];  a[i] := a[i-1];  a[i-1] := t;
				Вставить( a, i-1 )
			END;
		END;
	END Вставить;

Благодаря правилу сокращенного вычисления логических выражений, два таких вложенных оператора IF (оба без ELSE) можно преобразовать в один:

		IF  (i > 0) & (a[i] < a[i-1])  THEN
			t := a[i];  a[i] := a[i-1];  a[i-1] := t;
			Вставить( a, i-1 )
		END;

В самом деле, по правилу сокращенного вычисления, если результат вычисления i > 0 оказался FALSE, то результатом операции & (логическое И) будет FALSE независимо от значения второго операнда, и в таком случае этот второй операнд  выражение (a[i] < a[i-1])  не вычисляется.

Окончательный результат:

MODULE  i21примВставки;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
	PROCEDURE Вставить ( VAR a: ARRAY OF INTEGER;  i: INTEGER );
		VAR  t: INTEGER;
	BEGIN
		IF  (i > 0) & (a[i] < a[i-1])  THEN
			t := a[i];  a[i] := a[i-1];  a[i-1] := t;
			Вставить( a, i-1 )
		END;
	END Вставить;

	PROCEDURE Сорт* ( VAR a: ARRAY OF INTEGER );
		VAR  j: INTEGER;
	BEGIN
		FOR  j := 1  TO  LEN(a) - 1  DO
			Вставить( a, j )
		END;
	END Сорт;
	
END  i21примВставки.

Разработка процедуры сортировки вставками закончена!


Часть Г. Демонстрация работы

Две программы, демонстрирующие работу построенного алгоритма сортировки, даны в отдельных модулях (открываются в режиме редактирования):
		Демо1    Демо2

Первоначальные варианты можно открыть здесь (в режиме просмотра):
		Демо1    Демо2


Часть Д. Замена рекурсии на цикл

Посмотрим внимательно на процедуру Вставить:

	PROCEDURE Вставить ( VAR a: ARRAY OF INTEGER;  i: INTEGER );
		VAR  t: INTEGER;
	BEGIN
		IF  (i > 0) & (a[i] < a[i-1])  THEN
			t := a[i];  a[i] := a[i-1];  a[i-1] := t;
			Вставить( a, i-1 )
		END;
	END Вставить;

Заметим, что рекурсивный вызов процедуры Вставить стоит в самом конце, после него нет никаких исполняемых операторов. При этом все "актуальные экземпляры" процедуры Вставить работают с одним и тем же массивом. Таким образом, можно было бы просто изменить значение i на i-1 и выполнить процедуру снова. Но это эквивалентно тому, что мы выполняем цикл WHILE:

	PROCEDURE Вставить ( VAR a: ARRAY OF INTEGER;  i: INTEGER );
		VAR  t: INTEGER;
	BEGIN
		WHILE  (i > 0) & (a[i] < a[i-1])  DO
			t := a[i];  a[i] := a[i-1];  a[i-1] := t;
			i := i-1
		END;
	END Вставить;

Нужно только обратить внимание на поведение параметра i. Так как он у нас объявлен как параметр, передаваемый "по значению", то это означает, что переменная i является фактически внутренней переменной процедуры Вставить  в общем такой же, как и переменная t. Но значение переменной t при входе в процедуру не определено (по правилам языка), а значение i при первом вызове из процедуры Сорт равно значению выражения, которое было подставлено на его место в момент вызова процедуры (это было значение переменной j).
Другими словами, поведение параметра можно условно описать так:

	PROCEDURE Вставить ( VAR a: ARRAY OF INTEGER; <значение j> );
		VAR  t: INTEGER;  i: INTEGER;
	BEGIN
		i := <значение j>;
		WHILE  (i > 0) & (a[i] < a[i-1])  DO
			t := a[i];  a[i] := a[i-1];  a[i-1] := t;
			i := i-1
		END;
	END Вставить;

Легко убедиться, что цикл работает и завершается правильно в вырожденных случаях, упомянутых ранее  когда все элементы слева от a[i] больше него, или, наоборот, меньше или равны.

В итоге модуль получается таким:

MODULE  i21примВставки;
	IMPORT  Log := StdLog,  In := i21sysIn,  Math;
	
	PROCEDURE Вставить ( VAR a: ARRAY OF INTEGER;  i: INTEGER );
		VAR  t: INTEGER;
	BEGIN
		WHILE  (i > 0) & (a[i] < a[i-1])  DO
			t := a[i];  a[i] := a[i-1];  a[i-1] := t;
			i := i-1
		END;
	END Вставить;

	PROCEDURE Сорт* ( VAR a: ARRAY OF INTEGER );
		VAR  j: INTEGER;
	BEGIN
		FOR  j := 1  TO  LEN(a) - 1  DO
			Вставить( a, j )
		END;
	END Сорт;
	
END  i21примВставки.

Модуль компилируется без ошибок.

Чтобы продемонстрировать и проверить его работу, можно воспользоваться теми же процедурами, что были уже написаны (см. выше разделГ). 

Внимание! Так как процедура сортировки и проверяющие программы реализованы в разных модулях, могут возникнуть проблемы (вызывается старая версия сортировки, когда уже написана и успешно скомпилирована новая). О том, что делать в таких случаях, см. здесь.