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

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;

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

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

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

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 – число операций обмена

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