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