Использовать в след.ситуациях




Когда количество данных велико: все не помещаются в оперативной памяти, тогда используется «постраничная организация данных».

Содержит 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 Сумма
   
     
       
         
           
 
   
     
       
         
           
 
   
     
       
         
           
 
                   

 

...





Читайте также:
Тест мотивационная готовность к школьному обучению Л.А. Венгера: Выявление уровня сформированности внутренней...
Своеобразие родной литературы: Толстой Л.Н. «Два товарища». Приёмы создания характеров и ситуаций...
Основные научные достижения Средневековья: Ситуация в средневековой науке стала меняться к лучшему с...
Историческое сочинение по периоду истории с 1019-1054 г.: Все эти процессы связаны с деятельностью таких личностей, как...

Поиск по сайту

©2015-2022 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-12-12 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту:


Мы поможем в написании ваших работ!
Обратная связь
0.057 с.