Разработка подпрограммы sort

Спецификация

1. Назначение: сортировка части одномерного массива (от индекса first по индекс last), содержащего не более, чем 2n элементов

2. Имя: sort

3. Вид: процедура

4. Перечень параметров:

Таблица 19.6. Перечень параметров

Статус	Назначение	Имя	Тип	Вид
Вход/ выход	сортируемый массив	b	t1	параметр-переменная
Вход	Индекс начала диапазона сортировки	first	integer	параметр-значение
Вход	Индекс конца диапазона сортировки	last	integer	параметр-значение
Вход	Признак сортировка (истина – сортировка по возрастанию, ложь – по убыванию)	prs	boolean	параметр-значение

Примечание: тип t1 и поименованная константа n должны быть определены до текста подпрограммы

type t1=array[1..2*n] of integer;

5. Заголовок подпрограммы: procedure sort(var b:t1;first,last:integer;prs:boolean);

Метод решения

Используем метод сортировки выбором с перестановкой. В этом методе формируем все места с начального по предпоследнее. Для каждого формируемого места

" i:=first(1)last-1:

решаем две задачи:

1) выбор значения, которое должно располагаться на формируем месте i.

2) перестановку. На место экстремального значения заносим значение с формируемого места. На формируемое место записываем экстремальное значение

Задача 1 сводится к поиску экстремального значения и его местоположения, начиная с формируемого места i по последнее сортируемое место last. При сортировке по возрастанию ищется минимальное значение, по убыванию – максимальное. Метод решения этой задачи выглядит следующим образом:

1) переменной extr, в которой будет сформировано экстремальное значение присваивается первое значение, среди которых ищется экстремальное;

2) фиксируется местоположение экстремального значения в массиве. Для этого во вспомогательную переменную nm заносится индекс элемента, из которого взято значение (в данном случае nm:=i);

3) перебираются все остальные значения:

                                         " j:= i +1(1) last:

Для каждого j значения при сортировке по возрастанию (pr=истина), если очередное j значение меньше хранящегося в extr, а при сортировке по убыванию (pr=ложь) – больше, то

а) переменной extr присваиваем это очередное значение;

б) фиксируем местоположение текущего значения в массиве. Для этого во вспомогательную переменную nm заносится индекс j.

Задача 2 – это перестановка значений. Так как экстремальное значение существует в двух экземплярах (в переменной extr и в массиве на месте с индексом nm), то метод решения состоит из следующих действий:

1)    b[nm]:=b[i];

2)    b[i]:=extr.

Информационная модель

Таблица 19.7. Информационная модель

Назначение	Имя	Тип
Индекс формируемого места	i	integer
Индекс при поиске экстремального	j	integer
Экстремальное значение	extr
Местоположение экстремального значения	nm

Текст процедуры

procedure sort(var b:t1;first,last:integer;prs:boolean);

var i,j,nm:integer;

extr:integer;

begin

for i:=first to last-1

do begin

  extr:=b[i];

  nm:=i;

  for j:=i+1 to last

  do if prs and (b[j]<extr) or not prs and (b[j]>extr)

       then begin

                 extr:=b[j];

                 nm:=j

               end;

  b[nm]:=b[i];

  b[i]:=extr;

end

end;

Разработка подпрограммы sortpart

Спецификация

1. Назначение: сортировка определенной в задании части двумерного массива с использованием подпрограммы sort

2. Имя: sortpart

3. Вид: процедура

4. Перечень параметров:

Таблица 19.8. Перечень параметров

Статус	Назначение	Имя	Тип	Вид
Вход/ выход	сортируемый массив	a	t2n	параметр-переменная

Примечание: тип t2n и поименованная константа n должны быть определены до текста подпрограммы

type t2n=array[1..2*n,1..2*n] of integer;

5. Заголовок подпрограммы: procedure sortpart(var a:t2n);

Метод решения

Для каждой сортируемой строки двумерного массива (с первой по n-ую)

" i:=1 (1) n:

1) переписываем i-ую строку во вспомогательный одномерный массив b. Для этого перебираем все столбцы двумерного массива. Индекс при этом является одновременно индексом одномерного массива и индексом столбца двумерного;

2) обращаемся к процедуре sort сортировки части одномерного массива, задавая границы сортировки. Нижняя граница, исходя из постановки задачи, всегда n+1, а верхняя уменьшается с увеличением номера строки – 2n-i+1 (побочная диагональ);

3) переписываем отсортированный одномерный массив b в i-ую строку двумерного массива.

Информационная модель

Таблица 19.9. Информационная модель

Назначение	Имя	Тип
Номер (индекс) строки двумерного массива	i	integer
Номер столбца (индекс) двумерного массива и номер элемента (индекс) вспомогательного одномерного массива	j	integer
Вспомогательный одномерный массив	b	t1

Примечание: тип t1 определяется следующим образом

type t1=array[1..2*n] of integer;

:где  поименованная константа n должна быть определены до текста подпрограммы

Текст процедуры

procedure sortpart(var a:t2n);

type t1=array[1..2*n] of integer;

var b:t1;

i,j:integer;

begin

for i:=1 to n

do begin

  for j:=1 to 2*n

  do b[j]:=a[i,j];

  sort(b,n+1,2*n-i+1, true);

  for j:=1 to 2*n

  do a[i,j]:=b[j]

end

end;