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

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

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

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

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

// 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;

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

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

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

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

// а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;

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

Для поиска позиции элемента в отсортированном массиве можно использовать метод дихотомии (деления области поиска пополам). В этом методе элемент, который находится в середине области поиска, сравнивается с образцом, который нужно найти. В результате такого сравнения можно определить найден ли отыскиваемый элемент, а если нет, то можно определить, в какой из половин области поиска может находиться искомый элемент, справа или слева. Таким образом, в результате одного сравнения область поиска сужается наполовину.

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

Функция, возвращающая номер позиции элемента в отсортированном массиве приведена ниже. Если элемент не найден, функция возвращает 0.

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

// x – элемент, позицию которого нужно найти

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

function FindPosInSortArray (x: integer; a: TArray100; count: integer): integer;

var pos, left, right: integer;

Begin

// left и right – левая и правая границы области поиска

left:= 1; right:= count;

while left <= right do

Begin

// Позиция в середине области поиска

pos:=(right + left) div 2;

if a[pos] = x then begin

{ элемент найден}

result:= pos;

exit;

end;

if x < a[pos]

then right:= pos – 1 { элемент находится слева}

else left:= pos + 1; { элемент находится справа}

end;

// Элемент не найден

result:= 0;

end;