Когда количество данных велико: все не помещаются в оперативной памяти, тогда используется «постраничная организация данных».
Содержит 2 списка: во-первых, упорядоченный по возрастанию список ключей и соответствующей ему список указателей.
Для терминальных элементов (лист) список указателей отсутствует.
Если ключ k то указатель k+1
Добавление ключа всегда в лист.
Алгоритм добавления
Ключи в узле добавляются упорядочено
 |
Расщепление страницы
| | |
При удаление нужно соблюдать след. Правила:
Если элемент в листе, то удаляем просто так. Если элемент не в листе, то он заменяется на лексико-графический элемент. (либо самый правый из левого поддерева, либо самый левый из правого поддерева)
Удаляем 45
|
Удаляем 30
|
|
Для n=1 В-деревья называются 2-3 деревья. В+ деревья-все реальные ключи хранятся только в листьях, а не в терминальных узлах.
Сортировки
Внутренние внешние(сортировки файлов)
6. Внутренние сортировки(алгоритмы и реализация почти для всех разновидностей)
a.понятие(назначение), классификация
внутренние:
1)не на том же месте
· Подсчетом
· Распределяющий подсчет
· Вставка в список
· Вставка в список с вычислением адреса
· Слияние(простое/естественное)
· Турнирная
· Двухпутевые вставки
2) на том же месте
Обмен:
Простые:
· пузырек
· Улучшенный пузырек
· Шейкерная
Улучшенные:
· Сортировка Бетчера
· Быстрая сортировка
· Обмен-поразрядная
Вставка:
Простые:
· Простые вставки
· Бинарные вставки
Улучшенные
· Шема
· Пирамидальная
Выбор:
Простые:
· Простой выбор
6.b Сортировка подсчетом
1)Сравнить попарно все элементы массива и посчитать больше скольких каждый
2)Расставить элементы по своим местам
A-исходный массив
31 10 6 5 8 16 24 10
Cnt 7 3 1 0 2 5 6 4
Сортировка устойчива, если 2 элемента с одинаковыми ключами, не меняются местами
Const N=10;
Type TElem=real;
Tmas=array[1..n] of TElem;
Procedure CuleSort(var A:TMas);
Vari,j:integer;
Cut:array[1..n] of integer;
B:array[1..n]of TElem;
Begin
For i:=1 to n do
Cut[i]:=1;
For i:=1to n-1 do
For j:=i+1 to n do
If a[i]>a[j] then inc(cut[i])
Else inc(cut[j]);
For i:=1 to n do
B[cut[i]]:=A[i];
For i:=1 to n do
A[i]:=B[i];
End;
6.c. Распределяющий подсчет.
Ключ-прост. порядк. тип данных. Известен диапазон ключей и он невелик.
Type
TKey=1..4;
TElem=record
Key:TKey;
Info:char;
End;
VarCntKey:array[TKey] of integer;
//сколько раз какой ключ встречался
B:TMas;
i,j:integer;
key:TKey;
begin
for k:=u to v do
CntKey[k]:=0;
For i:=1 to n do
Inc(cntkey[a[i].key]);
For k:=succ(u) to v do
Cntkey[k]:=CntKey[k]+Cntkey[predkey];
For i:= n downto 1 do begin
B[cntkey[a[i].key]]:=a[i];
Dec(CntKey[a[i].key]);
End;
For i:= 1 to n do
A[i]:=B[i];
end;
6.d.Сортировка метода пузырька, улучшенный «пузырек».
A: 3 17 5 18 6 10 9 12
1 проход: 3 5 17 6 10 9 12 18
2 проход: 3 5 6 10 9 12 17
(от 1 до N-2)
3 проход: 3 5 6 9 10 12
(от 1 до N-3)
N-1 проход
For i:=1 to n-1 do
For j:=1 to n-I do
If A[j]>A[j+1] then a[j]<->a[j+1]
Улучшенный пузырек
A: 7 12 3 5 16 18 19 20
1: 7 3 5 12 16 18 19 20
2: 3 5 7 12 16 18 19 20
3: больше перестановок нет
T:=N;
Repeat
K:=t-1;
T:=0;
For j:=1 to k do
If a[j]>a[j+1] then begin
A[j]<->A[j+1];
T:=j;
End;
Until t=0; {t<2}
6.e. Шейкерная сортировка.
Улучшенный пузырек в 2 стороны
Varj,k,L,R:TIndex;
X:TElem;
Begin
L:=2; R:=N;
K:=n;
Repeat
For j:=R downto L do
If a[j-1]>a[j] then begin
A[j]<->a[j-1]; k:=j;
End;
L:=k+1;
For j:=L to R do
If a[j-1]>a[j] then begin
A[j]<->a[j-1]; k:=j;
End;
R:=k-1;
Until L>R;
End;
6.f. простые вставки.
A: 3 1 2 7 15 3 4 18
1: 1->3
For i:=2 to n do begin
X:=a[i];
J:=i-1;
While (j>0) and (a[j]>=x) do begin
A[j+1]:=a[j]; dec(j);
End;
A[j+1]:=x;
End;
6.g. Бинарные вставки.
VarI,j,m,L,R:TIndex;
X:TElem;
Begin
For i:=2 to n do begin
X:=A[I];
L:=1;R:=I;
While L<R do begin
M:=(L+R)div2;
If a[m]<=x then L:=m+1
Else R:=m;
End;
For J:=1 to downto R+1 do a[j]:=a[j-1];
A[R]:=x;
End;
End;
6.h. Вставка в список.
Элементы добавляются в упорядоченный список, после обратно в массив.
6.i.Двухпутевые вставки(с помощью массива, с помощью списка)
· Берется 1й элемент и размещается в область вывода.
· Каждый последующий сравнивается с центральным и помещается налево или направо.
6.j. Вставка в список с вычислением адреса.
6.kПростой выбор.(прямой выбор)
1) выбирается элемент с наименьшим ключом.
2)он меняется местами с первым элементом а1
3)затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый большой элемент.
For i:=1 to n-1 do begin
imin:=i;
For j:= i+1 to n do
If a[j]<a[imin] then imin:j;
If i<>imin then a[i]<->a[imin]
End;
6.l. Быстрая сортировка (сортировка Хоара)(два метода)
1) i идет вправо и ищем a[i] такое, чтобы оно оказалось больше чем a[j]
A: 7 3 15 8 20 6 11 4
A: 4 3 15 8 20 6 11 7
2) jидет вправо и мы ищемa[j] такое, что a[j]<a[i]. Еслиi<j, тоa[i]<->a[j]
Procedure Sort(L,R:integer);
VarI,j:integer; x:TElem;
Begin
i:=L; j:=R;
while(i<j) do begin
while (i<j) and (a[i]<a[j]) do i:=i+1;
ifi<j then a[i]<->a[j];
while (i<j) and (a[i]<a[j]) do j:=j-1;
ifi<j then a[i]<->a[j];
end;
if L<i-1 then Sort(L,i-1);
if j+1<R then Sort(j+1,R);
End;
6.m. Обменная поразрядная сортировка.
A: 5 7 1 3 0 2 4
101 111 001 011 000 010 100
1бит 2 7 1 3 0 5 4
010 111 001 011 000 101 100
2 0 1 3 7 5 4
Слева ищем число, где 1й бит=1. Справа ищем 0. Сдвигаемся к центру.
Отдельно сортируем по 2 биту.
2бит: 1 0 2 3 7 5 4
001 000 010 011
3бита 0 1 2 3
000 001 010 011
Procedure Sort(var A:TMas);
Procedure S(Left,Right,bit:integer);
Varj,i: integer;
Begin
i:=Left; j:=Right;
repeat
while (i<=j) and (GetBit(a[i], bit)=0) do inc(i);
while (i<=j) and (GetBit(a[i], bit)=1) dodec(j);
ifi<j then begin
a[i]<->a[j];
inc(i); dec(j);
end;
until (j<i);
if (Left<j) and (bit<size) then//если в отрезке не 1 элемент и бит с количества возможных битов
S(left,j,bit+1);
If (i<right) and (bit<size) then S(i, right,bit+1);
End;
Begin
S(1,N,1);
End;
Function GetBit(el:TElem; bit:byte):byte;
Var i:integer; mask:TElem;
Begin
Mask:=1;
For i:=size-1 downto bit do mask:=mask*2;
If el and mask=0 then result:=0
Else result:=1;
End;//result:=ord(el and mask<>0)
Type TElem=byte;
ConstSize=Sizeof(TElem)*8//для получения количества битов
6.n.Сортировка с убывающим шагом(сортировка Шелла).
A: 5 8 3 1 19 54 7
h1>h2>h3…>ht=1
желательно брать шаги не кратные друг другу
варианты выбора шага:
h[k-1]=3h[k]+1
h[t]=1 t=[log3n]-1
h[k-1]=2h[k]+1
h[t]=1 t=[log2n]-1
procedure Shell(var A:TMas);
vari,j,step,p,l,T:integer; el:TElem;
begin
T:=trunk(ln(N)/ln2);
For j:=T downto 1 do begin
Step:=Power(2,j)-1;
For p:=1 to step do begin
i:=step+p;
while (i<=N) do begin
el:=a[i];
l:=i-step;
while(l>=1) and (el<a[l] do begin
a[l+step]:=a[l];
l:=l-step;
end;
a[l+step]:=Elem;
i:=i+step;
end;
End;
End;
end;
6.o. Пирамидальная сортировка
Пирамида- это бинарное дерево для каждого из узлов которого выполняется след. правило: родитель старше(больше) своих потомков при сортировке по возрастанию; и родитель младше(меньше) своих потомков при сортировке по убыванию.
A: 5 8 1 8 42 56 14 2
8 1
8 42 56 14
Procedure HeapSort;
VarL,R:index; x:item;
Procedure sift(L,R:index);
Vari,j:index; x:item;
Begin
i:=L; j:=2*L; x:=a[L];
if (j<R) and (a[j]<a[j+1]) then j:=j+1;
while (j<=R) and (x<a[j]) do begin
a[i]:=a[j]; i:=j; j:=2*j;
if (j<R) and (a[j]<a[j+1]) then j:=j+1;
end;
a[i]:=x;
End;{sift}
Begin
L:=(n div 2)+1; R:=n;
While L>1 do begin L:=L-1; sift(L,R); end;
While R>1 do begin
X:=a[1]; a[1]:=a[R];a[R]:=x; R:=R-1;sift(L,R);
End;
End;{HeapSort}
6.p. простое слияние, естественное слияние(только алгоритмы)
Простое: серия- упорядоченный отрезок, фиксированной длины. В простом слияние длины всех серий одинаковы. Если есть 2 серии, то их можно слить в одну более длинную упорядоченную серию.
A: 21 13 6 5 11 84 7 28
B: 21 28 6 4 11 5 13 7
A: 7 13 21 28 84 11 6 5
B: 5 6 7 11 13 21 28 84
A: 5 6 7 11 13 21 28 84
Естественное слияние: естественнаяупоряд-ость данных. У каждой серии своя длина. Информация о длинах сериях не сохраняется.
A: 2 7 13; 6 8 24 11 6 4 5 2 1
B: 1 2 2 5 7 13; 24 11 8 6 6 4
A: 1 2 2 4 5 6 6 7 8 11 13 24
6.q. Туринирная сортировка(алгоритм)
2
2 35
3 2 35
3 6 2 35
A:3 17 8 6 2 11 35
B:2 3 6
7. Внешние сортировки
7.a. Понятие (назначение), классификация, характеристики.
1) простые(слияние):
· Простое:
ü Без использования внутр. Сортировки
ü С использованием
· Естественное:
ü Несбалансированное
ü Сбалансированное
2) Улучшенные(естественное сбалансированное слияние):
· Многофазная
· Каскадная
Характеристики:
1) двухпутевое
многопутевое
2)двухфазные
однофазные
7.e. Каскадная сортировка. Каскадная сортировка строится на базе многофазной сортировки, т.е. при распределение серий по файлам нужно следить чтобы серии не сливались, используя n вспомогательных файлов.
N=6
M=190//количество серий
a01=1
a0i =0 ali=ali+1+al-1n-1
| Lavel | a1 | a2 | a3 | a4 | a5 | a6 | Сумма | ||