Обработка упорядоченных массивов

Упорядоченные массивы чаще всего используются как хранилища некоторой информации. Наиболее часто встречающиеся задачи, связанные с обработкой таких массивов, следующие:

• Добавление элемента в массив, без нарушения порядка

• Объединение двух массивов в один с сохранением порядка

• Поиск позиции элемента в массиве

• Удаление элемента из массива

Ниже рассматриваются процедуры и функции, решающие эти задачи.

11. Вставка элемента в отсортированный массив

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

Если все элементы массива больше чем добавляемый элемент, то все элементы массива сдвинутся вправо, а новый будет поставлен на первое место.

Процедура вставки элемента в отсортированный массив приведена ниже.

// Процедура добавления в упорядоченный массив

// x – вставляемый элемент

// а – упорядоченный массив, count – число элементов в нем

procedure AddToSortArray (x: integer; var a: TArray100; var count: integer);

var i: integer;

begin

// В результате вставки число элементов в массиве увеличится на 1

count := count + 1;

i := count - 1; // номер анализируемого элемента

while (i >= 1) and (a[i] > x) do

begin

a[i + 1] := a[i]; // сдвигаем вправо

i := i - 1;

end;

a[i + 1] := x;

end;

12. Слияние двух отсортированных массивов в один

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

Процедура слияния массивов приведена ниже.

// Процедура слияния двух упорядоченных массивов

// а1, а2 – исходные упорядоченные массивы,

// count1 count2, – число элементов в этих массивах

// а3 – объединенный массив, count3 – число элементов в нем

procedure MergeSort Array (a1, a2 : TArray100; count1, count2: integer;

var a3: TArray100; var count3: integer);

var i, j, k: integer;

begin

// Число элементов в новом массиве равно сумме исходных

сount3 := count1 + count2;

k:=0; // Текущий индекс в первом массиве

i:=0; // Текущий индекс во втором массиве

j:=0; // Текущий индекс в третьем массиве

while (i <= count1) and (j <= count2) do

begin

if a1[i] < a2[j]

then begin // Добавляем элемент из первого массива

a3[k]:=a1[i];

i:=i+1;

end

else begin // Добавляем элемент из второго массива

a3[k]:=a2[j];

j:=j+1;

end;

k:=k+1;

end;

// Добавляем остаток первого массива, если есть

for i := i to count1 do

begin

a3[k]:=a1[i]; k:=k+1;

end;

// Добавляем остаток второго массива, если есть

for j := j to count 2 do

begin

a3[k] := a2[j]; k : k+1;

end;

end;