7.8 Вектор Айлиффа

A=array[1..L,1..M,…,1..N]of T; - k-мерный массив.

Координата записи A[k,i,…,j] вычисляется по формуле, сод. к-1 умножение.

Трехмерный массив А[L,M,N]

Приведенный индекс для A[k,i,j] – ((N*M)*k+N*i+j)=((M*k+i)*N+j)

Вектор F: F_k=адрес(A[1,1,1])+sizeof(T)*(N*M)*k, k=0..L-1

Вектор Q: Q_i=sizeof(T)*N*i, i=0..M-1

Вектор R: R_j=sizeof(T)*j, j=0..N-1

адрес(A[k,i,j])=F(k)+Q(i)+R(j)

Как устроен массив.

m: array[ 1..n1]of T; ( элементы)

mm: array[ 1..n2,1..n1]of T; ( строки, элементы)

mmm:array[1..n3,1..n2,1..n1]of T; (слои, строки, элементы)

Приведенный индекс.

Элемент массива	Приведенный индекс (смещение)
m[i]	i-1
mm[j,i]	(j-1)*n2+i-1
mmm[k,j,i]	((k-1)*n3+j-1)*n2+i-1

Вектор Айлиффа

w:=sizeof(T); v:=sizeof(pointer); A1,A2,A3:pointer;

Адрес начала массива	Адрес элемента массива
A1:=@m;	A1+(i-1)*w
A1:=@A2; A2=(@mm[1],@mm[2],..,@mm[n2])	(A1+(j-1)*v)^+(i-1)*w
A1:=@A2; A2:=(@A21,@A22,..,@A2n3); A2k=(@mmm[k,1],@mmm[k,2],..,@mmm[k,n2])	((A1+(k-1)*v)^+(j-1)*v)^+(I-1)*w

Лекция 8

Хранение данных в оперативной памяти или на внешних устройствах.

В оперативной памяти данные хранятся в структурах.

На внешних устройствах данные хранятся в файлах.

Обработка данных в структурах - вставка, удаление, поиск.

Для линейных структур «массив», «таблица» (а иногда и «очередь») – сортировка.

Для нелинейных структур - обход.

Операцию сортировки иногда применяют к файлам.

8.1 Сортировка – перестановка элементов линейной структуры

Структура – массив, таблица (реализована с помощью массива или в динамической памяти).

Запись:

Mem=record key:integer; info:inf end;

Mass=array[0..L]of Mem;

Считаем далее, что

a:Mass; x:Mem;

Всего элементов массива – n штук.

Для определенности считаем, что элементы массива a должны быть упорядочены по возрастанию значения ключа. Для простоты изложения будем говорить, что a[i]>a[j], если a[i].key>a[j].key.

Метод сортировки устойчив, если он не меняет порядок элементов с одинаковыми ключами.

Сортировка «на том же месте» – без использования дополнительной памяти (Под дополнительной памятью понимают память, объем которой зависит от количества элементов структуры).

Эффективность сортировки определяется объемом дополнительной памяти, если сортировка не «на том же месте», и затратами времени.

Алгоритмы сортировки будем характеризовать двумя параметрами:

С - количество сравнений ключей, М - количество перестановок.

8.2 Алгоритмы сортировки Три класса алгоритмов сортировки (включением, выбором, обменом)

8.2.1 Сортировка простым включением.

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

Пусть первые k элементов массива a упорядочены.

Первый элемент «неупорядоченной части» a[k+1] включается в «упорядоченную часть» на свое место следующим образом:

Значение a[k+1] записывается в переменную x. Далее «сдвигаются» на одну позицию в направлении возрастания индекса все элементы, большие чем x, до первого элемента, меньшего x. На «освободившееся» место записывается значение, хранящееся в x.

Procedure sort01(var a:Mass; N:integer);

var i,j:integer; x:Mem;

begin

for i:=2 to N do

begin

x:=a[i];

a[0]:=x;{Барьер!}

j:=i-1;

while x.key<a[j].key do begin a[j+1]:=a[j]; j:=j-1; end;

a[j+1]:=x;

end;

end;

Свойства:

• Устойчивость;

• Естественное поведение (если массив упорядочен, то меньше перестановок)

С_мин=N-1; С_ср=N²/4; C_макс= N²/2; М_мин=2(N-1); М_ср=N²/4; М_макс= N²/2;

8.2.2 Сортировка бинарным включением

В отличие от сортировки простым включением, место размещения включаемой записи «вычисляется» с помощью бинарного поиска.

for i:=2 to N do

begin

x:=a[i]; l:=1; r:=i;

while l<r do

begin

m:=(l+r) div 2;

if x.key<a[m].key then r:=m else l:=m+1

end;

for j:=i-1 downto l do a[j+1]:=a[j];

a[l]:=x;

end;

Свойства: Неестественное поведение. С_ср=N log₂N; M_cp=N²

8.2.3 Сортировка простым выбором

Из неупорядоченной части выбирается самый «маленький» элемент и ставится в «конец» упорядоченной части.

for i:=1 to N-1 do

begin

k:=i;

x:=a[i];

for j:=i+1 to N do if a[j].key<x.key then begin k:=j; x:=a[j] end;

a[k]:=a[i];

a[i]:=x;

end;

Свойства: Число сравнений не зависит от начального порядка С=N²/2

М_мин=3(N-1); M_cp=N log₂N; M_макс=N²/4

8.2.4 Сортировка простым обменом (пузырек)

For i:=2 to N do

begin

for j:=N downto i do

if a[j-1].key>a[j].key then

begin

x:=a[j-1];

a[j-1]:=a[j];

a[j]:=x

end;

end;

Свойства: Сср= N²/2; Мср=0.75 N²

Улучшения: Запоминать, где был обмен

Шейкер-сортировка - чередование направлений второго цикла.

8.2.5 Сортировка Шелла

Понятие h - сортировки (сортируется последовательность элементов с шагом h, повторяется h раз со сдвигом)

Сортировка Шелла - применение h₁,h₂, h_k - сортировки, причем h_k=1

Рекомендуются последовательности: ...121, 40, 13, 4, 1 или ... 31, 15, 7, 3, 1

Найти закономерности в этих последовательностях.

Свойство: Доказано, что i-отсортированная последовательность остается i-отсортированной после к-сортировки.

М_ср=N^1.2

8.2.6 Быстрая сортировка Хоара

«Разделение» массива

i:=1;

j:=N;

Выбор медианы x

repeat

while a[i].key<x.key do i:=i+1;

while x.key<a[j].key do j:=j-1;

if i<=j then

begin

w:=a[i];

a[i]:=a[j];

a[j]:=w;

i:=i+1;

j:=j-1

end;

until i>j;

procedure sort(l,r:integer);

var i,j:integer; x,w:Mem;

begin

i:=l; j:=r; x:=a[(l+r) div 2];

«разделение»

if l<j then sort(l,j);

if i<r then sort(i,r);

end;

8.2.7 Алгоритм сортировка последовательных файлов слиянием.

М-серия – уже упорядоченная последовательность из М элементов

Слияние двух М-серий - дает 2М-серию.

Картинка!

Ссылка на стр.106 Вирта. Там таблица эффективностей алгоритмов сортировки.

Лекция 9

О дискретном представлении чисел в ЭВМ.

9.1 Приближенные числа

Числа, заданные с погрешностью (или с заданной точностью)

Пример:

Вычислить

Обозначим

Приближения:

1). - с точностью 0.02;

2) с точностью 0.003

7/5	64/15625=0.004196..	1/125=0.008000	1.000
17/12	15625/2985354=0.005238	1/216=0.0046296	-1/6=-0.1666...

Выводы:

1. Ошибки переносятся и могут быть усилены.

2. Тождественные математические соотношения могут дать различные результаты.

3. Нужно уметь выбирать «лучшую» формулу.