Сортування підрахунком

Сортування підрахунком (англійською «Counting Sort») — алгоритм впорядкування, що застосовується при малій кількості різних елементів (ключів) у масиві даних. Час його роботи лінійно залежить як від загальної кількості елементів у масиві, так і від кількості різних елементів.

Ідея алгоритму полягає в наступному: спочатку підрахувати скільки разів кожен елемент (ключ) зустрічається в вихідному масиві. Спираючись на ці дані можна одразу вирахувати на якому місці має стояти кожен елемент, а потім за один прохід поставити всі елементи на свої місця.

В алгоритмі присутні тільки прості цикли довжини N (довжина масиву), та один цикл довжини K (величина діапазону). Отже, обчислювальна складність роботиалгоритму становить O (N + K).

В алгоритмі використовується додатковий масив. Тому алгоритм потребує E (K) додаткової пам’яті.

В такій реалізації алгоритм є стабільним. Саме ця його властивість дозволяє використовувати його як частину інших алгоритмів сортування (наприклад, сортування за розрядами). Використання даного алгоритму є доцільним тільки у випадку малих K.

ЛЕКЦІЯ 5

НЕЛІНІЙНІ СТРУКТУРИ ДАНИХ

Дерева

Деревоподібні і взагалі графові структури мають дуже широке застосування. Найчастіше деревоподібні структури використовуються у наступних випадках:

а) при трансляції арифметичних виразів;

б) при формуванні таблиць символів у трансляторах;

в) у задачах синтаксичного аналізу;

г) при трансляції таблиць розв‘язків.

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

Кореневим деревом називають орієнтований граф, у якого:

1) є одна особлива вершина, в яку не заходить жодне ребро і яку називають коренем дерева;

2) у всі інші вершини заходить рівно одне ребро, а виходить скільки завгодно;

3) немає циклів.

Існує ще так зване рекурсивне визначення дерева, згідно з яким дерево трактується як скінченна множина вершин Т, кожна з яких (крім кореня) належить до однієї з підмножин Т₁,..., Т_m; m=>0, Т_i ÇТ_j =0, і≠j. Підмножина Т_і називається піддеревом даної вершини. Число піддерев даної вершини називають степеню цієї вершини. Вершину з нульовою степеню називають листком. Всі інші вершини називаються внутрішніми.

Рівнем або рангом вершини по відношенню до дерева називають довжину шляху від кореня до цієї вершини плюс одиниця.

Довжина шляху - це кількість дуг, які треба пройти від кореня для досягнення даної вершини.

Висота дерева дорівнює кількості рівнів у дереві.

Говорять, що кожний корінь є батьком коренів своїх піддерев. Останні є синами свого батька і братами між собою.

Дерево називають n -арним, якщо кожний його вузол має не більше n потомків. На рис.5.1 зображено 3-арне дерево.

Інший приклад деревоподібної структури дають алгебраїчні формули. На рис. 5.2 зображено дерево, що відповідає арифметичному виразу a-b(с/d +e/f). Зв‘язок між формулами і деревами дуже важливий для побудови трансляторів арифметичних виразів.

Рис. 5.1. Приклад зображення 3-арного дерева

Рис.5.2.Приклад зображення формули у вигляді дерева