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

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

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

Сортування злиттям використовується в тих випадках, коли треба відсортувати послідовний файл, що не поміщається цілком в основній пам'яті. Розглянемо саме поняття злиття. Нехай існують два відсортованих в порядку зростання масивів Р та 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. Сортування включеннями

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