Последовательная сортировка одномерных массивов

End.

Begin

Var

End.

Begin

Var

A: array [1..10] of real ;

chNO,chP,n,i:integer;

writeln('введите размер массива');

readln(n);

for i:=1 to n do

readln(A[i]);

chNO := 0;

chP := 0;

for i:=1 to n do

if A[i]>0 then

chP := chP + 1;

if A[i]<>0 then

chNO := chNO + 1;

end;

writeln('процент положительных значений -', chP/chNO*100);

Рассмотрим ещё один пример: необходимо найти все чётные элементы в массиве А и поместить их в массив В.

Алгоритм решения задачи представлен на рисунке 18.

В целом рассматриваемый алгоритм (рис. 18) схож с алгоритмом поиска определённых элементов. Разница состоит в том, что значения найденных элементов не накапливаются для последующей обработки, а перемещаются в новый массив.

Для индексов найденных элементов используется независимый счётчик j. В начале перебора ему присваивается значение 1 (блок 5). При нахождении в исходном массиве первого чётного элемента выполняется его запись в массив В под номером j (j = 1), и значение счётчика j увеличивается на единицу и становится равным 2 (блоки 7, 8). Соответственно, следующий найденный элемент будет помещён в массив В под номером 2.

Рисунок 18 – Блок-схема алгоритма поиска
чётных элементов

В таблице 9 приведена трассировка части алгоритма (рис. 18). Каждая строка трассировочной таблицы соответствует состоянию переменных после выполнения определённого алгоритмического блока. В колонках представлены значения определённых переменных, или выражений, необходимых для пояснения алгоритма. Для удобства восприятия жирным в таблице выделены значения, которые изменились во время выполнения соответствующего блока.

Таблица 9 – Трассировка алгоритма копирования чётных
элементов из массива А в массив В

№ блока

A[i]

...

Реализация алгоритма в программу выглядит следующим образом:

program A_Bmas;

B,A:array[1..100] of integer;

n,i,j:integer;

write('n>');

read(n);

for i:=1 to n do

write('A[',i,']→');

read(A[i]);

end;

j:=1;

for i:=1 to n do

if A[i] mod 2 = 0 then

B[j]:=A[i];

j:=j+1;

end;

for i:=1 to j-1 do

writeln(B[i]);

Поиск определённых элементов

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

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

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

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

Основная идея алгоритма заключается в последовательном парном сравнении всех элементов массива.

Алгоритм решения задачи представлен на рисунке 19.

Переменная max используется для хранения текущего максимального значения. Вначале в качестве текущего максимального значения принимается значение первого элемента массива (блок 5).

Затем организуется перебор элементов массива, начиная со второго (блок 6). В теле цикла текущий максимальный элемент сравнивается с очередным элементом массива, и большее из этих значений сохраняется в качестве нового текущего максимального в переменной max (блоки 7, 8). Таким образом, при первом проходе цикла выбирается максимальное значение из двух первых элементов. На втором проходе полученное значение сравнивается с третьим элементом, и т. д. После окончания цикла в переменной max будет находиться максимальное из всех значений элементов массива.

Рисунок 19 – Блок-схема алгоритма поиска
максимального элемента

В таблице 10 представлена трассировка основной части алгоритма, представленного на рисунке 19.

Таблица 10 – Трассировка алгоритма поиска максимального
элемента

№ блока	i	A[i]	max	A

...
	-	-











...

Реализация алгоритма в программу выглядит следующим образом:

program Max;

var

A:array[1..100] of real;

n,i:integer;

max:real;

begin

write('n>');

read(n);

for i:=1 to n do

begin

write('A[',i,']>');

readln(A[i]);

end;

max:=A[1];

for i:=2 to n do

begin

if max<A[i] then

max:=A[i];

end;

writeln('Max=',max:4:2);

end.

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

Сортировка представляет собой процесс упорядочения элементов в массиве в порядке возрастания или убывания их значений.

Основная идея последовательной сортировки заключается в следующем. Вначале выбирается минимальный элемент из всего массива, найденный элемент перемещается в начало массива (в позицию с индексом, равным 1). Затем снова проводится поиск минимального элемента, но поиск начинается с позиции с индексом 2, так что элемент с индексом 1 при поиске не учитывается. Таким образом, будет найден второй по величине элемент массива. Затем это элемент перемещается в позицию с индексом 2. Теперь необработанная часть массива, в которой будет произведён поиск минимального значения, начинается с элемента с индексом 3. Эта последовательность операций выполняется до тех пор, пока в необработанной части массива не останется один элемент.

Рассмотрим алгоритм, представленный на рисунке 20.

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

Тело основного цикла (блоки 5, 6, 7, 8) содержит алгоритм поиска минимального элемента. Его отличает от алгоритма, представленного на рисунке 19, следующее: осуществляется поиск не максимального, а минимального элемента (поскольку сортировка производится по возрастанию элементов), поиск осуществляется не по всему массиву, а только в его части (элементы с индексами от k+1 до n), помимо самого минимального значения выясняется и его положение в массиве (переменная Nmin). Далее в блоке 9 происходит перестановка элементов массива, так что найденный минимальный элемент оказывается на вершине необработанной части массива, под индексом k.

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

Так повторяется до тех пор, пока в необработанной части массива не остаётся один элемент.

Рисунок 20 – Блок-схема алгоритма
последовательной сортировки

Приведём трассировку части представленного алгоритма (таблица 11). Вложенный цикл (блоки 6, 7, 8) предназначен для нахождения минимального элемента массива, среди элементов с индексами от k+1 до n. Это алгоритм рассматривался ранее, поэтому в трассировке блоки 6, 7, 8 будут отображены одной строкой, элемент, находящийся на вершине необработанной части массива А, помечен серой заливкой ячейки.

Таблица 11 – Трассировка алгоритма последовательной сортировки
одномерного массива

№ блока	k	A[k]	Nmin	min	A[Nmin]	A

...
			-	-	-

6,7,8						22

			-	-	-

6,7,8							33

			-	-	-

6,7,8

			-	-	-

6,7,8								55



...

Реализация алгоритма в программу выглядит следующим образом:

program sort1;

const n=5;

var a:array [1..n] of real;

k,m,i,Nmin:integer;

t,min:real;