Вопрос 16. Многомерные массивы. Работа с многомерными массивами.

В Паскале можно определять массивы различной размерности. В зависимости от того, как трактовать реальный объект – матрицу, можно использовать различные формы описания двумерного массива.

1). Матрица рассматривается как двумерная таблица. Пусть tl –тип индекса

1, t2 – тип индекса 2, t3 – тип компонента.

Формат записи двумерного массива (матрицы).

1. type

<имя типа> = array [tl, t2] of t3;

var

<имя массива> : <имя типа>;

b) var

<имя массива> : array [tl, t2] of t3;

2). Матрица рассматривается как вектор, элементы которой –векторы. Для удобства введем обозначения: tl и t2 – имена типов. А – имя двумерного массива, В – имя одномерного массива.

Формат записи двумерного массива.

1) type

М = array [tl] of array [t2] of t3;

var

A:M;

или

2). Var

A : array [tl] of array [t2] of t3;

Последнее описание дает большое удобство в работе. Мы можем обрабатывать матрицу, вызывая ее строки.

Работа с диагональными элементами массива.

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

включая сами эти элементы.

Индексы элементов главной диагонали всегда совпадают друг с другом.

Чтобы обратиться к элементам главной диагонали, необходимо:

For i:=l to n do

Writeln a[i, i];

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

Взаимосвязь индексов элемента побочной диагонали, стоящего на пересечении i-й строки и j-ro столбца, выражается соотношением i+j = n+1. Чтобы обратиться к элементам побочной диагонали необходимо:

b:=n;

For i:=l to n do begin

Writeln a[i, b];

b:=b-l; end;

Вопрос 17. Сортировка элементов массива. Алгоритмы пузырьковой сортировки.

Сортировка информации - это одна из стандартных процедур, возни­кающих в процессе решения задач самого различного характера.

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

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

С отсортирован­ными данными работать легче, чем с произвольно расположенными. Когда эле­менты отсортированы, их проще найти (как в телефонном справочнике или в словаре), проще производить с ними различные операции. В отсортированных данных легче определить, имеются ли пропущенные элементы; найти общие элементы двух множеств, если оба они отсортированы.

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

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

• количество сравнений;

• количество присваиваний.

Все методы сортировки можно разделить на две большие группы:

• прямые методы сортировки

• улучшенные методы сортировки.

В настоящее время известно большое число методов сортировки. Назовем некоторые из них:

1) сортировка выбором;

2. сортировка обменом;

3. сортировка вставками.

Алгоритм сортировки обменами (алгоритм "пузырька").

Метод "пузырька" является, пожалуй, самым простым из всех известных методов внутренней сортировки. Суть этого алгоритма состоит в последователь­ном просмотре массива от начала к концу и сравнении каждой пары элементов между собой. При этом если взаиморасположение не соответствует условию упорядоченности, то это устраняется путем перестановки элементов (обмена значениями). После такого прохода на последней n - ой позиции массива будет стоять максимальный элемент («всплыл» первый пузырек). Поскольку макси­мальный элемент уже стоит на своей последней позиции, то второй проход об­менов выполняется до n-1 -го элемента. И так далее. Всего потребуется n-1 про­ход.

Рассмотрим этот процесс на примере. Пусть исходный массив М состоит из 5 элементов и имеет вид:

Процесс сортировки может быть представлен на схеме:

Во время первого прохода произойдут три перестановки: 9-3, 9-6 и 9-1. На втором проходе будут переставлены 5 и 3, а затем 6 и 1. Третий и четвертый проход даст только по одной перестановке соответственно — 5 и 1, 3 и 1. Одна из возможных версий программы, реализующей алгоритм "пузырька", представлена на языке программирования Паскаль в следующем ви­де:

Program SortJBull; {сортировка методом "пузырька"}

uses Crt;

const п=10; {длина массива}

type Mas = array[1..n] of real;

var

M : mas;

В :real ;

i,j : integer; {счетчики}

begin

ClrScr,

writeln('Введите элементы массива');

for i :=1 To n do

Read(M{ i j); Readln;

{начало сортировки}

for i:=n downto 2 do {всплывание очередного максимального элемента на i позицию } for j : =1 to i-1 do

if M[j] > M[j + l ] then {обмен содержимым ячеек}

begin В := M[j +1]; M[j+l]:=M[j]; M[j]:=B; end;

{печать отсортированного массива}

for i : = 1 to n do

Write (M[i]:8:2); Writeln End.

Приведенный пример программы иллюстрирует сортировку массива по возрастанию с использованием метода «пузырька».