МІНІСТЕРСТВО освіти та науки України
Кіровоградський державний технічний університет
Кафедра програмного забезпечення
курсового проекту
з дісціпліні
"Програмування на мові ASM-86"
на тему:
"Програма для сортування даніх методом Піраміди"
Зміст
1. Вступ
2. Постановка Задачі
3. Обгрунтування Вибори методів розв'язку Задачі
4. Алгоритм Програми
5. Реалізація Програми
6. Сістемні вимоги
7. Інструкція для користувача
Висновки
Використана література
Додаток
1. Вступ
У наш годину Нові Інформаційні технології посідають Дуже Важливе Місце НЕ Ліше в спеціалізованіх, альо ї в повсякдення сферах життя. Комп'ютери застосовують у бізнесі, менеджменті, торгівлі, навчанні та багатьох інших сферах діяльності людини.
Комп'ютерні технології Дуже зручні для виконан різноманітніх операцій, альо в різніх сферах застосування ці Операції Різні. Того, шкірних окрема Галузо, Яки вікорістовує спеціфічні технічні засоби, потребує своїх Власний програм, які забезпечуються роботу комп'ютерів.
Розробка програмного забезпечення займається така Галузь науки, Як програмування. Вона набуває все більшого й більшого Значення останнім годиною, Аджея з шкірних днем ​​комп'ютер стає все більш необхіднім, все більш повсякдення явищем нашого життя. Аджея обчислювальних техніка минулих РОКІВ Вже Майже повністю вічерпала собі І не задовольняє тім потребам, Що постають перед людством.
Таким чином, Нові Інформаційні технології Дуже Актуальні в наш час и потребують Багато УВАГА для подальшої Розробка та вдосконалення. Поряд з ЦІМ, велике значення має кож и програмування, його призначення та є одним Із фундаментальних розділів інформатики и тому не Може залішатісь осторонь.
Програмування містіть цілу низький Важливим внутрішніх завдань. Однією з найбільш Важливим таких завдань для програмування є задача сортування. Під сортуванням звичайна розуміють перестановки елементів будь-якої послідовності у визначеному порядку. Ця задача є однією з найважлівішіх того, Що її метою є полегшення подальшої ОБРОБКИ Певної даніх І, насамперед, Задачі Поиск. Так, одним з ефективних алгорітмів Поиск є бінарній поиск. ВІН працює швідше Ніж, Наприклад, лінійній поиск, альо Його можливости застосовуваті Ліше за умов, Що послідовність Вже упорядкована, тобто відсортована.
Взагалі, відомо, Що в будь-якій сфері діяльності, Що вікорістовує комп'ютер для запису, ОБРОБКИ та Збереження інформації, Усі дані зберігаються в базах даніх, які кож потребують сортування. Певна впорядкованість для них Дуже Важливе, Аджея корістувачеві набагато легшим працюваті з данімі, Що мают Певний порядок. Так, можна розташуваті ВСІ товари по назві або Відомості про співробітніків чі студентів за прізвіщем або фатумом народження, тощо.
Задача сортування в програмуванні НЕ вірішена повністю. Аджея, хоча й існує велика кількість алгорітмів сортування, все ж таки метою програмування є не Ліше розробка алгорітмів сортування елементів, альо ї розробка самє ефективних алгорітмів сортування. Мі знаємо, Що одну й ту саму задачу можна вірішіті за допомог різніх алгорітмів и Коженов раз Зміна алгоритмом приводити до нових, більш або Менш ефективних розв'язків Задачі. Основними Вимоги до ефектівності алгорітмів сортування є дерло за все Ефективність за годиною та Економні Використання пам'яті. Згідно ціх Вимоги, Прості Алгоритми сортування (Такі, Як сортування Вибори и сортування включенням) не є Дуже Ефективна.
Алгоритм сортування обмінамі, хоча и завершує свою роботу (оскількі ВІН вікорістовує Ліше циклі з параметром и в тілі ціклів Параметри примусового НЕ змінюються) І не вікорістовує допоміжної пам'яті, альо займає Багато годині. Навіть, ЯКЩО внутрішній цикл не містіть жодної перестановки, то дії Будуть повторюватісь до тихий пір, Поки не завершитися Зовнішній цикл.
Алгоритм сортування Вибори ефектівніше сортування обмінамі за крітерієм М (n), тобто за кількістю пересілань, альо кож є не Дуже ефективна. З ціх причин Було розроблено деякі Нові Алгоритми сортування, Що ОТРИМАНО Назв швидких алгорітмів сортування. Це Такі алгоритми, Як сортування деревом, пірамідальне сортування, Швидко сортування Хоара та метод цифрового сортування.
2. Постановка Задачі
Необхідно Розробити програму, в якій реалізуваті алгоритм сортування методом Піраміди. Ця програма буде застосовуватісь для сортування числових даніх у файлі.
3. Обгрунтування Вибори методів розв'язку Задачі
Алгоритм пірамідального сортування HeapSort вікорістовує представлені масивов у віді дерева. Цей алгоритм не вімагає допоміжніх масівів, сортуючі "на місці". Розглянемо Спочатку метод представлення масивов у віді дерева:
Нехай A [1. n] - Деяк масив. Зіставімо йому дерево, вікорістовуючі наступні правила:
1. A [1] - корінь дерева;
2. ЯКЩО A [i] - вузол дерева и 2i ВЈ n,
то A [2 * i] - вузол - "Лівий сін" вузла A [I]
3. ЯКЩО A [i] - вузол дерева и 2i + 1 ВЈ n,
то A [2 * i +1] - вузол - "правий син" вузла A [i]
Правила 1-3 визначаються у масіві структуру дерева, причому Глибина дерева не перевершує [log 2 n] + 1. Смороду ж задають спосіб руху по дереву від кореня до листків. Рух вгору задається правилом 4:
4. ЯКЩО A [i] - вузол дерева и i> 1, то A [i mod 2] - вузол - "батько" вузла A [i];
Приклад: Нехай
A = [45 13 24 31 11 28 49 40 19 27]
- масив. Відповідне йому дерево має вид:
Зверніть Увага на ті, Що ВСІ рівні дерева, за вінятком последнего, ЦІЛКОМ заповнені, Останній Рівень заповненості ліворуч и індексація елементів масиву здійснюється вниз и праворуч. Тому дерево упорядкованого масиву відповідає Наступний властівостям:
A [i] (A [2 * i], A [i] (A [2 * i +1], A [2 * i] (A [2 * i +1].
Як це не дивно, алгоритм HeapSort Спочатку будує дерево, Що відповідає прямо протилежних співвідношенням:
A [i] Ві A [2 * i], A [i] Ві A [2 * i +1]
а потім змінює місцямі A [1] (найбільшій елемент) i A [n].
Як и TreeSort, алгоритм HeapSort працює в два етапи:
I. Побудова сортуючого дерева;
II. Просівання елементів по сортуючому дереву.
Дерево, Що представляє масив, назівається сортуючім, ЯКЩО виконують Умови (6). Якщо для Деяк i ця розумів не віконується, будемо Говорити, Що має Місце (сімейний) Конфлікт у трикутнику i.
Як на I-ом, так и на II-ому етапах елементарних дія алгоритму полягає в вірішенні сімейного конфлікту: Якщо найбільшій Із Синів Більше, Ніж батьку, то переставляються батько и цею сін (процедура ConSwap).
У результаті перестановки Може вінікнуті новий Конфлікт у тому трикутнику, Куди переставлених батьку. У такий спосіб можна Говорити про Конфлікт (роду) у піддереві з коренем у вершіні i. Конфлікт роду вірішується послідовнім вірішенням сімейних конфліктів проходом по дереву вниз. (На малий шлях Вирішення конфлікту роду у вершіні 2 відзначеній). Конфлікт роду вірішено, ЯКЩО прохід закінчівся (i> n div 2), або ж в результаті перестановки не виник новий сімейний Конфлікт.
I етап - побудова сортуючого дерева - оформімо у віді рекурсівної процедури, вікорістовуючі визначення:
ЯКЩО ліве и право піддерева T (2i) i T (2i +1) дерева T (i) є сортуючімі, то для перебудови T (i) необхідно вірішіті Конфлікт роду в цьому дереві.
На II-ом ​​етапі - етапі просівання - для k від n д...
