Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



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

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

 

крок масив
а -6 -9 -15 А.
b -15 -9
а -6 -15 -9
b -6   -15 -9
а -15 -9 -6

Робоча функція методу злиття оцінюється як 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()

}

 

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

Назвемо пірамідою послідовність елементів h1, h2,..., hn, таку, що

hi< h2i

hi < h2i+1

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

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

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

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

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

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

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

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

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

 

 


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

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

hi< h2i

hi < h2i+1

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

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

Робоча функція алгоритму O(n*log2n/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. Сортування включеннями




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

<== попередня сторінка | наступна сторінка ==>
Метод Шелла. | Порозрядне сортування для списків.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.012 сек.