МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Сортування злиттям.Сортування злиттям використовується в тих випадках, коли треба відсортувати послідовний файл, що не поміщається цілком в основній пам'яті. Розглянемо саме поняття злиття. Нехай існують два відсортованих в порядку зростання масивів Р та 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() }
Пірамідальне сортування. Назвемо пірамідою послідовність елементів 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.
Читайте також:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|