Сортування підрахунком (англійською «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.Приклад зображення формули у вигляді дерева