Сортировка массивов

End.

Begin

Begin

Var

Type

End.

Begin

Var

End.

Begin

Begin

Var

Type

Var

Type

Var

Type

Многомерные массивы

End.

Begin

Var

Type

Const

n=4;

vector=array[1..n] of real;

u, v:vector;

s, d:real; {S – скалярное произведение, d - длина}

i:integer;

s:=0; d:=0;

for i:=1 to n do begin

read(u[i],v[i]);

S:=S + u[i]*v[i];

d:=d + v[i]*v[i];

end;

d:=sqrt(d);

writeln(S, ‘ ‘,d);

ЛЕКЦИЯ №11

Схема описания многомерного массива

array [<тип индекса>] of array [тип индекса] of < тип элемента >

Тип элемента может быть любым кроме файлового.

Примеры описания двумерных массивов:

stroka = array [1..5] of integer;

matrix = array [1..3] of stroka;

a:matrix;

matrix = array [1..5] of array [1..3] of integer;

a:matrix;

matrix = array [1..3,1..5] of integer;

Доступ к элементам массива:

a[1][1]:= 1;

a[1,1]:= 1;

Многомерный массив:

var x: array [1..3, 5..10, 2..4] of real

x[1,5,2]:=1;

Элементы матрицы хранятся по строками

a11..a15	a21..a25	a31..a35
1-я строка	2-я строка	3-я строка

Такой способ даёт возможность индексировать целые строки.

Примеры программ:

1. Перестановка столбцов матрицы

program ColChange;

const n=3;

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

i, j, col1, col2: integer;

temp: real;

{ввод матрицы}

writeln(‘ Введите номера столбцов для перестановки ’);

readln(col1, col2);

for i:= 1 to n do

temp:= a[i,col1];

a[i,col1]:= a[i,col2];

a[i,col2]:= temp;

end;

{вывод матрицы}

2. Удаление строки матрицы

program ColDelete;

const n = 3, m = 4;

a:array [1..n, 1..m] of real;

I, j,k, newn: integer;

{ вводматрицы }

readln(k); { строка которую надо удалить }

for i:= k to n -1 do

for j:=1 to m do a[i, j]:= a[i + 1, j];

newn:= n-1; { новое количество строк }

{ вывод матрицы до строки newn }

Так как объем памяти, выделяемый под массив остается неизменным, последняя строка дублируется.

3. Умножение матриц. (три вложенных цикла)

program MultMatrix;

const p=10 { максимальный размер обрабатываемых матриц }

matrix = array [1..p, 1..p] of real;

a, b, c: matrix;

i, j, k, n, m, l: integer;

{ вводматрицы }

For i:= 1 to n do

for j:= 1 to m do

c[i, j]:= 0;

for k:=1 to l do c[i, j]:= c[i, j] + a[i, k]*b[k, j];

… { вывод матрицы }

4. Ввод размеров и элементов матриц.

writeln(‘ Введите количество строк матрицы А, n <= ’, p);

readln(n);

writeln(‘ Введите количество строк < = ’, p);

readln(L);

writeln(‘ Введите ‘, n * L, ‘ элементов матрицы А ’);

for i:= 1 to n do

for j:= 1 to L do read(a[i,j]);

{ Аналогично для матрицы В, количество строк = L }

for i:= 1 to L do

for j:= 1 to n do read(b[i,j]);

Сортировка – процесс перегруппировки заданного множества объектов в соответствии с определенными критериями (например, по возрастанию).

Цель сортировки – облегчить поиск элементов в отсортированном массиве

Методы:

ü Внутренний (не предусматривает использования дополнительных массивов, хранится в ОП)

ü Внешний (применяется к большим массивам, расположенным на внешних носителях)

Элементарные методы сортировки

ü Сортировка вставкой

ü Сортировка выбором

ü Сортировка обменом (пузырьковая)

Усовершенствованные методы сортировки

ü Быстрая сортировка (метод Хоара)

ü Сортировка методом Шелла

ü С помощью дерева или пирамидальный

ü Методом слияния.

Требования к алгоритму сортировки

ü Устойчивость (относительное расположение элементов с равными значениями не меняется)

ü Экономное использование памяти

ü Эффективность (время работы)

Мерой эффективности языка являются:

· С – число операций сравнения

· M – число операций обмена

Хорошие алгоритмы сортировки требуют операций сравнения.

Дата добавления: 2014-01-07