17.Сортировка массивов. Метод обменов.

Под сортировкой понимают перестановку эл-тов массива в заданном порядке. Отсортировать числовую таблицу по возрастанию это значит переставить эл-ты так, чтобы они шли в порядке возрастания значений, при возрастании номеров эл-тов. Отсортировать символьную таблицу – это значит расположить эл-ты этой таблицы в алфавитном порядке. Любой метод сортировки оценивается по двум показателям:

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

2. число сравнений.

Сортировка обменам.

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

Procedure Obmen(n:integer; var a:mas1);

Var I,j,vsp:integer;

Begin

For i:=0 to n-2 do

For j:=0 to n-i-2 do

If a[j]>a[j+1] then begin

Vsp:=a[j];

A[j]:=a[j+1];

A[j+1]:=vsp;end;

End;

18.Сортировка массивов. Метод вставок.

Под сорт-ой понимают перестановку эл-тов массива в заданном порядке. Отсортировать числовую таблицу по возрастанию это значит переставить эл-ты так, чтобы они шли в порядке возрастания значений, при возрастании номеров эл-тов. Отсортировать символьную таблицу – это значит расположить эл-ты этой таблицы в алфавитном порядке. Любой метод сортировки оценивается по двум показателям:

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

2. число сравнений

Сортировка вставками.

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

(Например: -3 0 -8 77 13

-8 -3 0 77 13

-8 -3 0 77 13

-8 -3 0 13 77)

Procedure Vstavka(n:integer; var a:mas1);

Var I,j,vsp:integer;

Begin

For i:=1 to n-1 do begin

Vsp:=a[i];

J:=i-1;

While (j>=0) and (a[j]>vsp) do begin

A[i+1]:=a[i];

J:=j-1;

End;

A[i+1]:=vsp;end;end;

19.Подпрограммы в Паскале. Основные способы передачи параметров в подпрограмму, их сравнение.

Подпрограммы помогают реализовать принцип структурного прог-ия связанный с нисходящим проектированием программы. При обращении к подпрограмме вместо формальных параметров указываются фактические параметры. Список формальных параметров отражает исходные данные и результаты подпрограммы. При обращении к подпрограмме на месте формальных параметров задаются фактические, т.е. это вполне определённые значения величин подлежащих обработки. М/у формальными и фактическими параметрами должны выполнятся следующие соответствия:

1. по количеству;

2. по типу: на соответствующих местах должны стоять величины одного и того же типа;

3. по смыслу: на соответственных местах должны стоять параметры, в которые вкладывается один и тот же смысл.

1)Параметры-значения: В заголовке подпро-мы параметр-значения описываются без каких-то предшествующих служебных слов. Механизм взаимодействия: при вызове подпро-мы для парам.-значения в стеке выделяется соот-ый объём памяти, куда копируется соот-ый фактический параметр. В дальнейшем все действия выполняются над этой копией, не затрагивая при этом фактического параметра. После завершения работы подпро-мы память в стеке освобождается от копии формального параметра. Значение фактического параметра можно изменять, после завершения программы посмотреть чему равен параметр-значения нельзя. Преимущества и недостатки:«+»изменения формального параметра не влечёт за собой изменения параметра-значения;«-»копирования фактического параметра занимает дополнительный объём памяти, совпадающий с объёмом фактического параметра. 2)Параметры-переменные: описываются в заголовке подпро-мы после служебного слово VAR. Обычно параметр-переменной используется для результата. Если в заголовке встречается несколько параметров-переменных имеющие разные типы, то для каждого из них задаётся своё VAR. При использовании параметров-переменных копии фактического параметра не создаётся, т.к. передаётся адрес фактического параметра. И т.о. формальный и фактически параметр имеют на всём протяжении подпро-мы один и тот же адрес. При изменении одного из параметров происходит изменение и другого. Именно за счет этого и происходит передача результата работы подпро-мы в основную программу. Достоинства и недостатки: «+»Экономия памяти;«-» возможные неконтролируемые изменения фактического параметра.

3)Параметры-константы: описываются после служебного слова const. Перед параметром каждого типа нужно поставить своё const. Передача фактического параметра осуществляется по адресу. Отличие от параметров-переменых заключается в том, во-первых, их запрещается менять внутри подпро-мы; во-вторых, они не м/б использованы в качестве фактических параметорв других подпрограмм.