Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Сортування включенням
При сортуванні включенням до відсортованої множини R кожний раз приєднується один елемент, а саме: із невідсортованої вхідної множини М вибирається довільний елемент і розміщується у вихідну множину R.
Алгоритм V.
Нехай задано множину елементів М, | M|=n.
V1. k =1; повторювати кроки V2, V3, доки k<n.
V2. Вибір довільного елемента x вхідної множини М: x=M(k).
V3. Розміщення x у вихідній множині R так, щоб вона залишалась відсортованою.
V4. Кінець. Вихід.
Вихідну множину R при кожному включенні можна відсортовувати відомим методом сортування, наприклад, методом простої вибірки. Майже всі методи сортування включенням у найгіршому випадку вимагають порядку n2 порівнянь, тому їх застосування пов‘язане з деяким ризиком. Є багато варіантів цього методу сортування.
Розглянемо метод Шелла. Його суть полягає в тому, що на кожному кроці групуються та сортуються елементи, що стоять один від одного на певній відстані h. Потім ця відстань зменшується на крок рівний степені двійки. На останньому кроці іде звичайне одинарне сортування. Перша відстань вибирається відносно кількості елементів в масиві поділена на 2.
Приклад:
44 55 12 42 94 18 06 67 n=8, h=n/2=4
44 18 06 42 94 55 12 67 h=h/2=4/2=2
06 18 12 42 44 55 94 67 h=h/2=2/2=11
06 12 18 42 44 55 67 94 стоп.
Час роботи залежить від вибору значень h. Існує декілька підходів вибору цих значень:
· · При виборі,,, …, h m = 1 час роботи алгоритму, в найгіршому випадку, становить O (N 2).
· · Якщо h - впорядкований за спаданням набір чисел виду (3j – 1)/2, j Î N, h i < N, то час роботи є O (N 1.5).
· · Якщо h - впорядкований за спаданням набір чисел виду 2 i 3 j, i, j Î N,
h k < N, то час роботи є O (N ∙log2 N).
4.6. Сортування розподілом
Методи сортування розподілом являють собою природне узагальнення ручних методів сортування. Вони передбачають розбиття вхідної множини елементів М на р підмножини М1,..., Мр, для яких виконуються умови М1 < М2 <... < Мр
Алгоритм R має рекурсивну структуру (позначено квадратними дужками)
Нехай задано множину М елементів, що розбита на р підмножини Мі
R1. Якщо |M|=0 або |М|=1, кінець.
R2. Інакше [Розбиття М на М1... Мp так, щоб М1 < Мp ; i=1, виконувати доки і<p [Сортування розподілом підмножини Мі; i=i+1 ] ].
R3. Кінець. Вихід.
Одну з версій цього алгоритму називають цифровим або порозрядним сортуванням за аналогією з системою числення. На практиці механічне сортування починається з молодшого розряду і просувається в напрямку до старшого, при цьому відсортовані підмножини послідовно об’єднуються і перерозподіляються.
Приклад:
Дано сортування сортування сортування
«одиниць» «десятків» «сотень»
329 720 720 329
457 355 329 355
657 436 436 436
839 457 839 457
436 657 355 657
720 329 457 720
355 839 657 839
Цифрове сортування не використовує порівняння елементів, тому не можна оцінювати його в звичайних термінах. Якщо елементи містять m цифр, то потрібно виконати m проходів i, якщо на кожному проході розподіляється n елементів, то основні кроки виконуються m*n раз. Цифрове сортування зручно використовувати для рядків символів.
4.7. Сортування злиттям або об’єднанням
Методи цього класу працюють за таким принципом: невідсортовану вхідну множину довільно розбивають на підмножини М1,..., Мp. Потім ці підмножини сортують окремо одним з відомих методів сортування і об’єднують в одну відсортовану множину.
Продемонструємо цю схему на двох множинах, оскільки багаторазове злиття можна здійснювати багаторазовим виконанням попарного злиття.
Нехай маємо дві відсортовані множини X і У; потрібно об’єднати їх у множину Z, яка також повинна бути відсортованою. У ролі Z1 приймаємо min (x1, y1) якщо Z1 = x1є X, тоді Z2 = min(x2, y1) і т.д.
Для запису алгоритму використовуємо таке позначення: і - індекс для множини X, j - індекс для множини Y, k – індекс для множини Z, i=1..n; j=1..m; k=1..(n+m).
Для зручності розмістимо в кінці кожної множини фіктивні елементи: xn+1= max, ym+1 =max.
Алгоритм C
Дано X={ x1,…, xn }; Y={ y1,…, ym }.
C1. Ініціалізація індексів i=1, j=1, k=1;
C2. Виконувати C3, C4 доки k<n+m.
С3 [Якщо xi < yi то [ zk = xi; i=i+1 ] інакше [ zk=yi, j=j+1 ]
C4. k=k+1 ]
C5. Кінець. Вихід.
В квадратних дужках записані дії які повторюються. Кількість порівнянь, яку необхідно виконати в алгоритмі С для злиття двох множин, дорівнює |x|+|y|=n+m.
Вся процедура злиття разом вимагає не більше ніж n порівнянь для n елементів i потрібно буде виконати log2 n переходів із однієї множини у другу. Тобто алгоритм С вимагає п log2 n порівнянь.
Час роботи алгоритму злиття T (n) для n елементів задовольняє рекурентному співвідношенню: T (n) = 2∙ T (∙ n/2) + O (n), де T (∙ n/2) - час на впорядкування половини масиву, O (n) - час на злиття цих половинок. Враховуючи, що T (1) = O (1), розв’язком співвідношення є: T (n) = O (n ∙log(n)).
4.8. Сортування підрахунком
Сортування підрахунком (англійською «Counting Sort») — алгоритм впорядкування, що застосовується при малій кількості різних елементів (ключів) у масиві даних. Час його роботи лінійно залежить як від загальної кількості елементів у масиві, так і від кількості різних елементів.
Ідея алгоритму полягає в наступному: спочатку підрахувати скільки разів кожен елемент (ключ) зустрічається в вихідному масиві. Спираючись на ці дані можна одразу вирахувати на якому місці має стояти кожен елемент, а потім за один прохід поставити всі елементи на свої місця.
В алгоритмі присутні тільки прості цикли довжини N (довжина масиву), та один цикл довжини K (величина діапазону). Отже, обчислювальна складність роботи алгоритму становить O (N + K).
В алгоритмі використовується додатковий масив. Тому алгоритм потребує E (K) додаткової пам’яті.
В такій реалізації алгоритм є стабільним. Саме ця його властивість дозволяє використовувати його як частину інших алгоритмів сортування (наприклад, сортування за розрядами). Використання даного алгоритму є доцільним тільки у випадку малих K.
Дерева. Основні визначення та поняття. Бінарні дерева. Зображення в пам‘яті ЕОМ графоподібних структур. Алгоритми обходу дерев.Висхідні, нисхідні, змішані алгоритми обходу дерев.
ЛЕКЦІЯ 5
НЕЛІНІЙНІ СТРУКТУРИ ДАНИХ
Дерева
Деревоподібні і взагалі графові структури мають дуже широке застосування. Найчастіше деревоподібні структури використовуються у наступних випадках:
а) при трансляції арифметичних виразів;
б) при формуванні таблиць символів у трансляторах;
в) у задачах синтаксичного аналізу;
г) при трансляції таблиць розв‘язків.
При роботі з деревами дуже часто використовуються рекурсивні алгоритми, тобто алгоритми, які можуть викликати самі себе. При викликуалгоритму йому передається в якості параметра вказівник на вершину дерева, яка розглядається як корінь піддерева, що росте із цієї вершини. Якщо вершина термінальна, тобто в неї немає синів, то алгоритм просто застосовується до даної вершини. Якщо ж у вершини є сини, то він рекурсивно викликається для кожного із синів. Загальні графові структури застосовують при зображенні розріджених матриць, у машинній графіці, при пошуку інформації і в інших складних задачах. Прикладом графоподібної структури є ієрархічна циклічна структура, що має рівні, аналогічно дереву або орієнтованому графу, але елементи на всякому рівні можуть бути циклічно зв'язані, як, наприклад, у ієрархічних списках. У структурах даних найчастіше використовується табличний або матричний спосіб задання графа.
Кореневим деревом називають орієнтований граф, у якого:
1) є одна особлива вершина, в яку не заходить жодне ребро і яку називають коренем дерева;
2) у всі інші вершини заходить рівно одне ребро, а виходить скільки завгодно;
3) немає циклів.
Існує ще так зване рекурсивне визначення дерева, згідно з яким дерево трактується як скінченна множина вершин Т, кожна з яких (крім кореня) належить до однієї з підмножин Т1,..., Тm; m=>0, Тi ÇТj =0, і≠j. Підмножина Ті називається піддеревом даної вершини. Число піддерев даної вершини називають степеню цієї вершини. Вершину з нульовою степеню називають листком. Всі інші вершини називаються внутрішніми.
Рівнем або рангом вершини по відношенню до дерева називають довжину шляху від кореня до цієї вершини плюс одиниця.
Довжина шляху - це кількість дуг, які треба пройти від кореня для досягнення даної вершини.
Висота дерева дорівнює кількості рівнів у дереві.
Говорять, що кожний корінь є батьком коренів своїх піддерев. Останні є синами свого батька і братами між собою.
Дерево називають n -арним, якщо кожний його вузол має не більше n потомків. На рис.5.1 зображено 3-арне дерево.
Інший приклад деревоподібної структури дають алгебраїчні формули. На рис. 5.2 зображено дерево, що відповідає арифметичному виразу a-b(с/d +e/f). Зв‘язок між формулами і деревами дуже важливий для побудови трансляторів арифметичних виразів.
Рис. 5.1. Приклад зображення 3-арного дерева
Рис.5.2.Приклад зображення формули у вигляді дерева
5.1.1. Бінарні дерева
Всяке дерево може бути зведено до бінарного. Бінарним називають таке 2-арне дерево, в якого один потомок є лівим, а другий - правим. Вершина бінарного дерева може взагалі не мати потомків, або мати тільки ліве, або тільки праве піддерево, або обидва піддерева одночасно.
Бінарне дерево з m вершинами називають збалансованим, якщо різниця між рівнями будь-яких двох вершин не більша від одиниці.
Бінарні дерева бувають позиційними і впорядкованими. У впорядкованих деревах між множиною вершин і натуральним рядом чисел існує взаємно однозначна відповідність. Позиційні дерева відрізняються від впорядкованих тим, що в перших важлива позиція вершини, а в других - тільки номер (рис.5.3).
Рис.5.3. Різні позиційні, але однаково впорядковані бінарні дерева
У позиційному бінарному дереві кожна вершина може бути єдиним способом описана за допомогою рядка символів над алфавітом {0, 1}. Це дає значну зручність для зображення дерев в пам‘яті комп‘ютера. При цьому корінь дерева характеризується рядком "0". Всякий син вершини Z характеризується рядком, префікс (початкова частина) якого є рядком, що характеризує Z. Рядок, приписаний будь-якій висячій вершині Z, не є префіксом ні для яких рядків, що характеризують інші вершини дерева. Множина рядків, що відповідає висячим вершинам деякого дерева, утворює префіксний код цього дерева (рис.5.4). Довжина рядка, що відповідає вершині, дорівнює рівню цієї вершини.
Рис. 5.4. Символьний опис дерева
Багато алгоритмів формальних граматик і пошуку даних мають структуру бінарного дерева. Прикладом є алгоритми обробки префіксних формул у трансляторах арифметичних виразів.
Date: 2015-07-27; view: 875; Нарушение авторских прав; Помощь в написании работы --> СЮДА... |