Метод прямых вставок с барьером (ПрВстБар)

Алгоритм ПрВст

Сортировка простыми вставками

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

Оперирование несколькими полями

Доступ к полям

Обратиться к полю записи можно следующим способом: <имя_записи>.<имя_поля>. Например:

month:= my_birthday.month +1;

Если программе предстоит несколько раз подряд обращаться к полям одной и той же записи,

может оказаться неудобным записывать это обращение полностью:

my_birthday.day:= 17;

my_birthday.month:= 3;

my_birthday.year:= 2004;

Для сокращения таких участков служит оператор with, позволяющий обращаться к полям, не указывая каждый раз имя всей записи:

with <имя_записи> do

begin

<операторы>

{имена полей здесь используются как<имя_поля>,а не как <имя_записи>.<имя_поля>}

end;

Например:

with my_birthday do

begin day:= 17;

month:= 3;

year:= 2004;

end;

Замечание. Для того чтобы внутри оператора with можно было обратиться не к полю записи, а к глобальной переменной с таким же именем, перед этой переменной нужно указать (через точку) имя программы: <имя_программы>.<имя_переменной>.

К простым внутренним сортировкам относят методы, сложность которых пропорциональна квадрату размерности входных данных (при сортировке массива, состоящего из N компонент, такие алгоритмы будут выполнять С*N2 действий, где С - некоторая константа).

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

1. Первый элемент записать "не раздумывая".

2. Пока не закончится последовательность вводимых данных, для каждого нового ее элемента выполнять следующие действия:

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

- записать новый элемент на освободившееся место.

Реализация алгоритма ПрВст

for i:= 2 to N do

if a[i-1]>a[i] then {*}

begin x:= a[i];

j:= i-1;

while (j>0)and(a[j]>x) do {**}

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

j:= j-1; end;

a[j+1]:= x;

end;

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

for i:= 2 to N do

if a[i-1]>a[i] then

begin a[0]:= a[i]; {*}

j:= i-1;

while a[j]>a[0] do {**}

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

j:= j-1; end;

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

end;

Эффективность алгоритма ПрВстБар ~N2.