Курсовая работа: Програма для сортування даних методом піраміди
Якщо ліве і праве піддерева T (2i) і T (2i+1) дерева T (i) є сортуючими, то для перебудови T (i) необхідно вирішити конфлікт роду в цьому дереві.
На II-ом етапі - етапі просівання - для k від n до 2 повторюються наступні дії:
1. Переставити A [1] і A [k] ;
2. Побудувати сортуюче дерево початкового відрізка масиву A [1. k-1], усунувши конфлікт роду в корені A [1]. Відзначимо, що 2-а дія вимагає введення в процедуру Conflict параметра k.
Нескладно підрахувати, що
С (n) = O (n log2 n), М (n) = O (n log2 n)
4. Алгоритм програми
Записи R1. Rn вміщені в масиві. Сортування здійснюється за таким спільним алгоритмом:
1. Встановити l= [N/2] +1, r=n
2. Якщо l>1, то зменшити його на 1, R=R1. (Якщо l=1, це означає,що процес сортування завершено). Інакше встановити R=Rr, Rr=R1, r=r-1. Якщо r=1, то встановити R1=R і завершити роботу.
3. Приготуватися до перестановок (j=l)
4. Встановити i=j та j=j*2. Якщо j<r, то перейти в п.5, якщо j=r, то перейти до п.6, інакше - до п.8.
5. Якщо Kj>Kj+1, то j=j+1
6. Якщо К>Кj, то перейти до п.8.
7. Ri=Rj, перейти до п.4.
8. Ri=R, повернутися до п.2.
5. Реалізація програми
Після запуску програма зчитує з вхідного файла байти для сортування. Після цього викликається процедура sort_start, яка запускає процес сортування. При сортуванні використовується рекурсивний алгоритм виклику функцій sorttree, conflict та conswap. При сортуванні інформація записується в потрібне місце масиву згідно описаного вище алгоритму.
Після закінчення сортування програма створює вихідний файл і записує в нього відсортований масив.
6. Системні вимоги
Операційна системаDOS
CPUINTEL 8086 або ст.
RAM640 K
VIDEOCGA або старший
7. Інструкція для користувача
Перед запуском програми треба відредагувати або створити файл piramid. dat. Він у кожному байті (до 255) може містити 1-байтні числа. Для редагування зручно, наприклад, користуватися редактором VC у HEX-режимі.
Після цього треба запустити файл piramid,com. Після її роботи, якщо не виникне помилок, з’явиться файл piramid. out, який буде містити ті ж байти, що і вхідний, але у відсортованому порядку.
Висновки
Отже, ми розглянули як працює алгоритм пірамідального сортування і спробували визначити його складність.
Застосування того чи іншого алгоритму сортування для вирішення конкретної задачі є досить складною проблемою, вирішення якої потребує не лише досконалого володіння саме цим алгоритмом, але й всебічного розглядання того чи іншого алгоритму, тобто визначення усіх його переваг і недоліків.
Звичайно, необхідність застосування саме швидких алгоритмів сортування очевидна. Адже прості алгоритми сортування не дають бажаної ефективності в роботі програми. Але завжди треба пам’ятати й про те, що кожний швидкий алгоритм сортування поряд із своїми перевагами може містити і деякі недоліки.
Розглядаючи такий швидкий алгоритм сортування, як пірамідальне сортування, можна зазначити, що цей алгоритм ефективний, адже він сортує “на місці", тобто він не потребує додаткових масивів. Крім того, цей алгоритм оптимальний: його складність співпадає з нижньою оцінкою задачі, тобто за критеріями C (n) та M (n) він має складність O (n log2 n), але містить складний елемент в умові. Тобто, в умові A [left] має бути строго менше ніж x, а A [right] - строго більше за x. Якщо ж замість “строго більше” та “строго менше" поставити знаки, що позначають “більше, або дорівнює” та “менше, або дорівнює", то індекси left і right пробіжать увесь масив і побіжать далі. Вийти з цієї ситуації можна було б шляхом ускладнення умов продовження перегляду, але це б погіршило ефективність програми.
Отже, головною задачею, яку має вирішити людина, яка повинна розв’язати задачу сортування - це визначення як позитивних, так і усіх негативних характеристик різних алгоритмів сортування, передбачення кінцевого результату. До того ж, треба враховувати головне - чи, можливо, цю задачу задовольнить один з класичних простих алгоритмів сортування.
Використана література
1. Львов М.С., Співаковський О.В. Основи алгоритмізації та програмування. - Херсон, 1997.