i21прим/Docu.Пошаговая разработка/2. Пузырек.odc

2. Пошаговая разработка: Пузырьковая сортировка

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

Решение

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


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

Эта часть выполняется так же, как и в первомпримере. Единственное отличие  файлу дадим другое имя  Пузырек, так что имя модуля будет i21примПузырек. Заготовка модуля и процедуры будет иметь след. вид (мы здесь не показываем строчку IMPORT  она здесь не нужна):

MODULE  i21примПузырек;
	
	PROCEDURE Сорт* ( VAR a: ARRAY OF INTEGER );
		VAR  
	BEGIN
		
	END Сорт;
	
END  i21примПузырек.


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

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

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

Представим себе массив a:

		a[0]  a[1] ... a[len-1]

где len  число элементов массива. Его всегда можно узнать с помощью стандартной функции LEN: len := LEN(a).

На первом шаге максимальное значение "всплывает" в позицию len-1. 
На следующем шаге максимальное значение из оставшихся "всплывает" в позицию len-2. Кто такие "оставшиеся"? Это элементы a[0]a[1]..a[len-2].
На следующем шаге максимальное значение из оставшихся "всплывает" в позицию len-3. Кто такие "оставшиеся"? Это элементы a[0]a[1]..a[len-3].
И так далее.
Видим, что получается цикл, на каждом шаге которого делается по существу одно и то же: максимальное значение из некоторого сегмента a[0]..a[j] перемещается в крайнюю правую позицию сегмента  т.е. в позицию j. Вот это число j и возьмем в качестве управляющей переменной цикла.
Первый шаг соответствует j = len-1. На каждом очередном шаге j уменьшается на единицу. Другими словами, получается следующий цикл:

		FOR  j := LEN(a) - 1  TO  ?  BY  -1  DO
			(* переместить макс. значение из сегмента a[0] .. a[j] на место a[j] *)
		END;

Каким должно быть последнее значение? Рассмотрим крайнее значение: j=0. Но тогда сегмент состоит из единственного элемента, и он сам и есть максимальный, и притом стоит на своем месте  в позиции a[j]. Так что шаг j=0 не нужен. Следующим кандидатом будет j=1. В этом случае речь идет о сегменте a[0]a[1], и шаг цикла имеет смысл. 
Итак, вместо знака вопроса в цикле нужно поставить единицу.
Модуль приобретает следующий вид:

MODULE  i21примПузырек;
	
	PROCEDURE Сорт* ( VAR a: ARRAY OF INTEGER );
		VAR  j: INTEGER;
	BEGIN
		FOR  j := LEN(a) - 1  TO  1  BY  -1  DO
			(* переместить макс. значение из сегмента a[0] .. a[j] на место a[j] *)
		END;
	END Сорт;
	
END  i21примПузырек.

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

MODULE  i21примПузырек;
	
	PROCEDURE МаксВправо ( VAR a: ARRAY OF INTEGER; i: INTEGER );
		VAR  
	BEGIN
		
	END МаксВправо;
	
	PROCEDURE Сорт* ( VAR a: ARRAY OF INTEGER );
		VAR  j: INTEGER;
	BEGIN
		FOR  j := LEN(a) - 1  TO  1  BY  -1  DO
			МаксВправо( a, j )
		END;
	END Сорт;
	
END  i21примПузырек.

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

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


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

Итак, сосредоточимся на процедуре МаксВправо. Нам нужно переставить самый большой из элементов a[0] .. a[i] в самую правую позицию.

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

	PROCEDURE МаксВправо ( VAR a: INTEGER; i: INTEGER );
		VAR  j: INTEGER;
	BEGIN
		FOR  j := 0  TO  i - 1  DO
			(* сортировать пару a[j], a[j+1] *)
		END;
	END МаксВправо;
	
Нетрудно понять, что после проверки пары a[j], a[j+1] в позиции a[j+1] окажется самое большое значение из всех a[0], a[1], ... a[j+1]. А когда дойдем до j = i-1, то самое большое значение окажется в позиции a[i], что и требуется. Таким образом, задача полностью свелась к заданию шага цикла.

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

		FOR  j := 0  TO  i - 1  DO
			СортироватьПару( a[j], a[j+1] )
		END;

Понятно, что у новой процедуры должно быть два параметра. Как их надо описать?
Во-первых, тип обоих параметров должен совпадать с типом элементов массива a  INTEGER  чтобы можно было подставить на их места a[j] и a[j+1].
Во-вторых, по смыслу процедуры, значения элементов массива, которые передаются ей в качестве параметров, могут меняться в результате ее работы. Поэтому оба параметра нужно передать "по ссылке", т.е. снабдить атрибутом VAR.

Итак, модуль с новой процедурой может иметь такой вид:

MODULE  i21примПузырек;
	
	PROCEDURE СортироватьПару ( VAR лев, прав: INTEGER );
		VAR  
	BEGIN
		(* сортировать пару лев, прав *)
	END СортироватьПару;

	PROCEDURE МаксВправо ( VAR a: ARRAY OF INTEGER; i: INTEGER );
		VAR  j: INTEGER;
	BEGIN
		FOR  j := 0  TO  i - 1  DO
			СортироватьПару( a[j], a[j+1] )
		END;
	END МаксВправо;
	
	PROCEDURE Сорт* ( VAR a: ARRAY OF INTEGER );
		VAR  j: INTEGER;
	BEGIN
		FOR  j := LEN(a) - 1  TO  1  BY  -1  DO
			МаксВправо( a, j )
		END;
	END Сорт;
	
END  i21примПузырек.

Итак, процедура СортироватьПару должна, если нужно, переставлять значения параметров левый и правый так, чтобы после ее выполнения было выполнено условие лев <= прав. Очевидно, именно такое сравнение и должно быть выполнено в самом ее начале:
		
		IF  лев <= прав  THEN
			(* делать нечего *)
		ELSE
			(* обменять значения переменных лев и прав *)
		END;

Обмен значений реализуется обычным способом с помощью вспомогательной переменной того же типа, что и обмениваемые значения, т.е. INTEGER.

Окончательно получается следующий модуль:

MODULE  i21примПузырек;
	
	PROCEDURE СортироватьПару ( VAR лев, прав: INTEGER );
		VAR  t: INTEGER;
	BEGIN
		IF  лев <= прав  THEN
			(* делать нечего *)
		ELSE
			t := лев;  лев := прав;  прав := t
		END;
	END СортироватьПару;

	PROCEDURE МаксВправо ( VAR a: ARRAY OF INTEGER; i: INTEGER );
		VAR  j: INTEGER;
	BEGIN
		FOR  j := 0  TO  i - 1  DO
			СортироватьПару( a[j], a[j+1] )
		END;
	END МаксВправо;
	
	PROCEDURE Сорт* ( VAR a: ARRAY OF INTEGER );
		VAR  j: INTEGER;
	BEGIN
		FOR  j := LEN(a) - 1  TO  1  BY  -1  DO
			МаксВправо( a, j )
		END;
	END Сорт;
	
END  i21примПузырек.


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

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

Поскольку сигнатуры обеих процедур сортировки одинаковы, достаточно в этих проверочных модулях заменить имена импторируемых модулей с процедурами сортироваки  i21примВставки на i21примПузырек  и затем перекомпилировать. См. замечания в конце файлов после текстов проверочных модулей.

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