КрНУ

Інформаційний портал – Коледжу Кременчуцького національного університету імені Михайла Остроградського!

Сортировка массивов. Двухмерные массивы.

Основные разделы темы.
1. Сортировка массива.
2. Виды сортировок.
3. Поиск в массиве.
4. Линейная сортировка (Сортировка отбором)
5. Пузырьковый метод.
6. Действия с двумерными массивами.
7. Программа транспонирования матрицы
Сортировка и поиск являются важнейшими понятиями информатики. Сортировка
– это процесс упорядочения набора данных одного типа по увеличению или уменьшению значения какого-либо признака. С точки зрения программиста наибольший интерес
представляют: сортировка массива; сортировка строк; сортировка элементов файла. Именно эти сортировки используются при разработке компиляторов, интерпретаторов, баз данных, оформлении статистических данных, справочных материалов и большинства прикладных пакетов.
При сортировке элементы массива меняются местами таким образом, что их значения оказываются упорядоченными по увеличению или уменьшению. Если в массиве есть одинаковые элементы, то говорят о сортировке по уменьшению или по не росту. В большинстве случаев речь идет о сортировке одномерного массива.
Следует знать:
 сортировка массивов-одно из наиболее важных действий над массивами в системах сбора и поиска информации, поскольку в отсортированных массивах найти нужную информацию можно гораздо быстрее по сравнению с неотсортированными;
 существует множество различных алгоритмов сортировки, которые значительно отличаются друг от друга по скорости работы (Один из самых популярных методов
сортировки – ” пузырьковый “основан на том, что в процессе исполнения алгоритма более “легкие элементы массива постепенно”всплывают”. Особенностью данного метода является сравнение, а затем, если требуется, и перестановка соседних элементов);
 “быстрые” способы сортировки массивов могут дать колоссальный выигрыш
на больших массивах, содержащих тысячи элементов, однако для небольших
массивов можно использовать самые простые способы сортировки.
Обычная постановка задачи по сортировке массива выглядит следующим образом:
 программа должна вывести несортированный массив целых чисел на экран,
 выполнить его сортировку по не росту или не уменьшению,
 вывести отсортированный массив.
Линейная сортировка (Сортировка отбором)
Идея линейной сортировки по не росту состоит в том, чтобы, последовательно
просматривая весь массив, отыскать наибольшее число и поменять его местами с
первым элементом. Затем просматриваются элементы массива, начиная со второго,
снова находится наибольший, который меняется местами со вторым и т. д.
Задание 20:
Программа линейной сортировки по убыванию
const count=20;
m: array [1.. count] byte =(9,11,12,3,19,1,5,17,10,18,3,19,17,9,12,20,20,19,2,5);
var i, j, buf, l: byte; a: integer;
begin
writeln (‘ исходный массив:’ ) ;
for i:=1 to count do write (‘ ‘, m[i]);
writeln;
а:=0; { обнуляем счетчик итераций }
{ изменение размера не отсортированной части массива }
for i:=1 to count-1 do
{сравниваем поочередно i-й элемент не отсортированной части массива со всеми от
i + 1-го до конца }
for j:=i+1 to count do
begin
а:=A+1;
if m[i]<m[j] then { если в не отсортированной части массива нашли элемент}
{больше, чем i-й, то меняем их местами }
begin
buf: = m[i]; { buf-буфер обмена }
m[i]:=m[j];
m[j] := buf;
end;
for l:=1 to count do write(‘ ‘, m[l]);
writeln ( ‘ ; итерация# ‘, a);
end;
end.
По последнему значению а определяем, что для данного массива линейная сортировка
по не росту выполняется за 190 итераций.
Задание 21:
Пузырьковый метод.
Массив просматривают слева направо. Каждый предыдущий элемент сравнивается с
дальнейший. Если предыдущий элемент больше следующего, ТО предыдущий и
следующий элементы меняются местами.
Program sort1;
const n=10;
label metka;
var a: array [1..n] of integer;
i, c, k : integer;
begin
for i:=1 to n do readln(a[i]);
metka: k=0; {счетчик перестановок}
for i:=1 to n-1 do
if a[i]>a[i+1] then begin c:=a[i];
a[i]:=a[i+1];
a[i+1]:=c;
k:=1;
end;
if k=1 then goto metka
else writeln (‘упорядоченный ‘);
for i:=1 to n do writeln(a[i]);
эnd.
Тоже самое, но с использованием вложенных циклов: Program sort2;
const n=10;
var a: array [1..n] of integer;
i, k, c : integer;
begin
for i:=1 to n do readln(a[i]);
for i:=1 to n-1 do
for k:=1 to n-i do
if a[k]>a[k+1] then begin c:=a[k];
a[k]:=a[k+1];
a[k+1]:=c;
end;
for i:=1 to n do writeln(a[i]);
эnd.
Задание 22:
Данная программа замены отрицательных элементов массива на их модули:
program mass;
const n=30;
type mas=array[1..n] of integer;
var a : mas;
i : integer;
begin
for i:=1 to n do {ввод массива}
begin write (‘введите ‘, i, ‘ – ый элемент массива); readln(a[i]);
end;
for i:=1 to n do writeln(‘a [‘, i,’]=’, a[i]); {вывод массива}
for i:=1 to n do
if a[i]<0 then a[i]:=abs(a[i]);
for i:=1 to n do writeln(‘a [‘, i,’]=’, a[i]); { вывод нового массива}
end.
Задание 11:
Измените программу так, чтобы она выполняла:
1. добавить к каждому элементу массива число 25;
2. если элемент четный, то прибавить к нему первый, Если нечетный – последний элемент массива. Первый и последний элементы не менять.
3. найти значение максимального по модулю элемента массива;
4. найти среднее арифметическое значение парных элементов.
Действия с двумерными массивами.
1. Суммирование элементов каждой строки.
Договоримся, что массив а состоит из п строк и M столбцов. Результатом является массив с именем d, состоящий из п Сумм элементов строк:
for i:=1 to n do
begin
s:=0;
for j:=1 to m do s:=s+a[i,j];
d[i]:=s;
end;
Аналогично исчисляется сумма в столбцах, для этого внешний цикл необходимо сделать по переменной j (номер столбца), а внутренний-по i (номер в строке)
2. Поиск минимального элемента всей матрицы и умножения матрицы на вектор будут рассмотрены в лабораторной работе.
3. Перестановки элементов в массиве
В случае перестановки строк матрицы необходимо переставить местами все элементы двух строк.
При перестановке двух строк, скажем, первого и второго, не обязательно использовать в качестве буфера обмена целый массив. Одной переменной вполне достаточно, поскольку перестановки всех элементов строк выполняются по очереди.
for j:=1 to m do
begin
buf:= а[1, j]; а[1, j]:=a[2, j]; а[2, j]:=buf;
end;
Хорошим примером перестановки элементов двумерного массива является транспонирование матрицы. При транспонировании элементы матрицы переставляются таким образом, что строки начальной матрицы становятся столбцами транспонированной матрицы. Транспонирование сводится к обмену элементов матрицы, расположенных симметрично относительно главной диагонали.
Главная диагональ-элементы a11, a22, a33, a44 (индексы элементов, расположенных на главной диагонали (i=j)
Побочная диагональ-элементы a41, a32, a23, a14 (сумма индексов элементов на 1
больше размерности строки (или столбца) т. е. i+j=4+1 или i+j=n+1.
Для индексов элементов, расположенных над главной диагональю выполняется
отношение i<J.
Для индексов элементов, расположенных под главной диагональю выполняется
отношение i > J.
Пример:
1) Найти сумму элементов главной диагонали :
S:=0;
for i:=1 to n do
S:=S+a[i,i];
2) Найти минимальный элемент боковой диагонали :
min:=a[1,n];
for i:=1 to n do
if a[i,n+1-i]<min then min:=a[i,n+1-i];
Задание 23:
Программа транспонирования матрицы.
program Transpon;
const а: array[1..4,1..4] integer= ( (2,5,7,3) (1,7,4,9) (3,6,8,4) (5,8,2,4) );
var i,j,t:integer;
begin
for i:=1 to 4 do
for j:=1 to 4 do
if I < j then begin { все элементы выше диагонали меняем}
t:=a [i, j]; { местами с соответствующими }
а[i,j]:=a [j,i]; { ниже по диагонали}
а [j, i]:=t;
end;
63
for i:=1 to 4 do begin { вывод транспонированной матрицы}
for j:=1 to 4 do write(а[I,j]:4);
writeln;
end;
end.
Задание 12:
1. Матрицу размером 4 4 заполнить случайными числами и упорядочить строки
по росту.
2. Матрицу размером 4 4 заполнить случайными числами и упорядочить столбцы
по убыванию.
3. Дан двумерный массив A[N, M] сформировать массив B [N, M], где
B[I, J] =SQR (A[I, J]), если I – нечетное