• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Сортування злиттям.

Сортування злиттям використовується в тих випадках, коли треба відсортувати послідовний файл, що не поміщається цілком в основній пам'яті. Розглянемо саме поняття злиття. Нехай існують два відсортованих в порядку зростання масивів Р та Q. Крім того є порожній масив R, який треба заповнити значеннями масивів Р та Q в порядку зростання. Для злиття виконуються наступні дії: порівнюють р[1] та q[l], менше значення записується в г[1]. Нехай це будер p[1]. Тодір p[2] порівнюється з q[l], і менше з них заноситься в г[2]. Далі процес повторюється до кінця одного з масивів. В кінці роботи "хвіст" того масиву, що залишився, переписується в масив г.

Для сортування злиттям масиву а[1], а[2], ..., а[n] створюється парний масив b[l], b[2], .... b[n]. На першому кроку виконується злиття елементів а[1] та а[n] з розміщенням результатів у b[l], b[2], злиття елементів а[2], а[n-1] з розміщенням результатів в b[3], b[4],..., злиття елементів а[n/2], а[n/2+1] з розміщенням результату в b[n-l], b[n]. На другому кроку виконується злиття пар b[l], b[2] та b[n-l], b[n] з розміщенням результату в а[1], а[2], а[3], а[4], і т.п.

Таблиця 4.2. Приклад сортування злиттям.

Робоча функція методу злиття оцінюється як O(n*1nn). Але об'єм пам'яті при цьому дорівнює 2 *n.

Приклад програми методу злиттям.

#include <iostream.h>

#include <conio.h>

void sort (int x[20], int y[20], int z[40], int rl, int r2)

{

int i=j=k=0, min;

if(rl>r2)

min=r2

else min=rl;

for (; i<min|| j<min; ++k)

{

if x[i]>y[j]

{z[k]=y[j];++j;}

else if (x[i]<y[j])

{z[k]=xfij; ++k}

else {z[k]=x[i]; ++k;

z[k]=y[j]; ++k}

}

For (i=0; i<k; ++i)

cout <<z[i] <<end1;

}

void main()

{

int a[20], b[20], c[40], i, razml, razm2;

clrscr();

cout <<введіть розмір масиву а" << end1;

сіn >>razm1;

cout <<"введіть масив а";

for (i=0; i<rozml; ++i)

{ сіn >>а[і];

cout << end1;

}

соut<<"введіть розмір масиву b" << end1;

сіn >> razm2;

cout << "введіть масив b";

for (i=0; i<rozm2; ++i)

{cin >>b[i];

cout << end1;

} sort (a,b,c,razml, razm2);

getch()

}

Пірамідальне сортування.

Назвемо пірамідою послідовність елементів h₁, h₂,..., h_n, таку, що

h_i< h_2i

h_i < h_2i+1

для будь-якого і.

рис.4.3. Розташування елементів масиву в "піраміді".

Для того, щоб добавити новий елемент в дерево, треба:

1. новий елемент X розташовуємо в вершину дерева;

2. порівнюємо елементи справа та зліва: вибираємо найменший;

3. якщо цей елемент менше X - змінюємо їх місцями та переходимо до кроку 2. Інакше кінець процедури.

Розглянемо приклад виконання сортування методом піраміди. Нехай дано масив h₁ h₂,..., h_a Елементи h_т/2+1... h_n вже утворюють нижній ряд піраміди, тому що не існує індексів і, j : j=2*i (або j=2*i+l). Тут впорядковувати непотрібно. На кожному кроку добавляється новий елемент зліва та просіюється на місце.

Фаза перша: побудова піраміди.

Для масиву А=( 45, 13, 24, 31, 11, 28, 49, 40, 19, 27 ) дерево має вид

Фаза друга: сортування масиву.

Дерево, що представляє масив, називається сортуючим, якщо виконується умова

h_i< h_2i

h_i < h_2i+1

Якщо для деякого і ця умова не виконується, будемо говорити, що має місце "сімейний" конфлікт у трикутнику і.

Як на першому, так і на другому етапах елементарна дія алгоритму полягає в вирішенні сімейного конфлікту: якщо найбільший із синів більше, ніж батько, то переставляється і цей син. В результаті перестановки може виникнути новий конфлікт у тому трикутнику, куди переставлений батько. У такий спосіб можна говорити про конфлікт роду у піддереві з коренем у вершиш і. Конфлікт роду вирішується послідовним вирішенням сімейних кофліктів проходом по дереву вниз. Конфлікт роду вирішено, якщо прохід закінчився, або ж в результаті перестановки не виник новий сімейний конфлікт.

Робоча функція алгоритму O(n*log₂n/2).

Приклад програми методу піраміди:

var a: array[1..10] of real;

k,n,l: integer,

procedure conswap(i,j:integer);

var b:real;

begin

if a[i]<a[j] then begin

b:=a[i]; a[i]:=a[j]; a[i]:=b;

end

end;

procedure confiict(i,k: integer);

var j: integer;

begin

j:=2*i;

if j=k then conswap(i, j)

else if j<k then begin

if a[j+l]>a[j] thenj=j+l;

conswap(i,j);

conflict(j,k);

end

end;

procedure sorttree(i: integer);

begin if i<=n div 2 then begin

sorttree(2*i); sorttree(2*i+l); conflict(i,n);

end

end;

begin

writeln ('vv n');

readln(n);

writeln('vv mas a');

for l:=l to n do

read(a[l]);

sorttree(l);

for k:= n downto 2 do begin

conswap(k,l); conflict(l,k-l);

end;

for 1:=1 to n do

write(a[l]:4:0);

end.

Читайте також:

1. Багатофазне сортування
2. Багатофазне сортування
3. Контроль-сортування (дефектація).
4. Медичне сортування та медична евакуація при НС
5. МЕДИЧНЕ СОРТУВАННЯ.
6. Порозрядне сортування для списків.
7. Сортування
8. Сортування - це процес, який дозволяє впорядкувати множину подібних даних у порядку зростання або убування.
9. Сортування вибором
10. Сортування вибором
11. Сортування вибором.
12. Сортування включеннями

Переглядів: 2802