КрНУ

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

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

Основные разделы темы.
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 – НЕЧЕТНОЕ, и B[I,J] = SQRТ(A[I, J]), если I – ЧЕТНОЕ;