Задача сортування даних в програмуванні. Алгоритм сортування обміном за критерієм або вибором, деревом, пірамідальне, швидке, сортування Хоара та метод цифрового сортування. Системні вимоги та інструкція для користувача. Алгоритм та лістинг програми.
В наш час нові інформаційні технології посідають дуже важливе місце не лише в спеціалізованих, але й в повсякденних сферах життя. Компютери застосовуються в бізнесі, менеджменті, торгівлі, навчанні та багатьох інших сферах діяльності людини. Тому, кожна окрема галузь, яка використовує специфічні технічні засоби, потребує своїх власних програм, які забезпечують роботу компютерів. Під сортуванням звичайно розуміють перестановки елементів будь-якої послідовності у визначеному порядку. Взагалі, відомо, що в будь-якій сфері діяльності, що використовує компютер для запису, обробки та збереження інформації, усі дані зберігаються в базах даних, які також потребують сортування.Необхідно розробити програму, в якій реалізувати алгоритм сортування методом піраміди.Розглянемо спочатку метод представлення масиву у виді дерева: Нехай Зіставимо йому дерево, використовуючи наступні правила: 1. Вони ж задають спосіб руху по дереву від кореня до листків. Відповідне йому дерево має вид: Зверніть увагу на те, що всі рівні дерева, за винятком останнього, цілком заповнені, останній рівень заповнений ліворуч і індексація елементів масиву здійснюється вниз і праворуч. Дерево, що представляє масив, називається сортуючим, якщо виконуються умови (6).Сортування здійснюється за таким спільним алгоритмом: 1. Встановити l= [N/2] 1, r=n Інакше встановити R=Rr, Rr=R1, r=r-1. Якщо r=1, то встановити R1=R і завершити роботу.Після запуску програма зчитує з вхідного файла байти для сортування.CPUINTEL 8086 або ст.Перед запуском програми треба відредагувати або створити файл piramid. dat.Отже, ми розглянули як працює алгоритм пірамідального сортування і спробували визначити його складність. Застосування того чи іншого алгоритму сортування для вирішення конкретної задачі є досить складною проблемою, вирішення якої потребує не лише досконалого володіння саме цим алгоритмом, але й всебічного розглядання того чи іншого алгоритму, тобто визначення усіх його переваг і недоліків. Розглядаючи такий швидкий алгоритм сортування, як пірамідальне сортування, можна зазначити, що цей алгоритм ефективний, адже він сортує “на місці", тобто він не потребує додаткових масивів. Крім того, цей алгоритм оптимальний: його складність співпадає з нижньою оцінкою задачі, тобто за критеріями C (n) та M (n) він має складність O (n log2 n), але містить складний елемент в умові.; j<k conf_1: push ax mov si,dx mov ah,byte ptr a [si 1] mov al,byte ptr a [si] cmp ah,al jbe sk_2 inc dx sk_2: pop ax push bx push dx call conflict pop dx pop bx conf_stop: popa pop bp retn conflict endp sorttree proc near push bp mov bp,sp pusha mov ax, [bp 4] ; i mov bl,n xor bh,bh; n shr bx,1 cmp ax,bx; i<n jae sort_exit ; sorttree (2*i) mov bx,ax shl bx,1 push bx call sorttree pop bx ; conflict (i,n) mov bl,n xor bh,bh push bx push ax call conflict pop ax pop bx sort_exit: popa pop bp retn sorttree endp start_sort proc mov ax,1 push ax call sorttree pop ax mov cl,n mov ch,0 inc cx lo: ; conswap (k,1) mov si,cx mov di,1 call conswap ; conflict (1,k-1) mov bx,cx dec bx push bx push ax call conflict pop ax pop bx dec cx cmp cx,1 jne lo ret start_sort endp in_file db "piramid. dat",0 out_file db "piramid.
План
Зміст
1. Вступ
2. Постановка задачі
3. Обгрунтування вибору методів розвязку задачі
4. Алгоритм програми
5. Реалізація програми
6. Системні вимоги
7. Інструкція для користувача
Висновки
Використана література
Додаток
Вывод
Отже, ми розглянули як працює алгоритм пірамідального сортування і спробували визначити його складність.
Застосування того чи іншого алгоритму сортування для вирішення конкретної задачі є досить складною проблемою, вирішення якої потребує не лише досконалого володіння саме цим алгоритмом, але й всебічного розглядання того чи іншого алгоритму, тобто визначення усіх його переваг і недоліків.
Звичайно, необхідність застосування саме швидких алгоритмів сортування очевидна. Адже прості алгоритми сортування не дають бажаної ефективності в роботі програми. Але завжди треба памятати й про те, що кожний швидкий алгоритм сортування поряд із своїми перевагами може містити і деякі недоліки.
Розглядаючи такий швидкий алгоритм сортування, як пірамідальне сортування, можна зазначити, що цей алгоритм ефективний, адже він сортує “на місці", тобто він не потребує додаткових масивів. Крім того, цей алгоритм оптимальний: його складність співпадає з нижньою оцінкою задачі, тобто за критеріями C (n) та M (n) він має складність O (n log2 n), але містить складний елемент в умові. Тобто, в умові A [left] має бути строго менше ніж x, а A [right] - строго більше за x. Якщо ж замість “строго більше” та “строго менше" поставити знаки, що позначають “більше, або дорівнює” та “менше, або дорівнює", то індекси left і right пробіжать увесь масив і побіжать далі. Вийти з цієї ситуації можна було б шляхом ускладнення умов продовження перегляду, але це б погіршило ефективність програми.
Отже, головною задачею, яку має вирішити людина, яка повинна розвязати задачу сортування - це визначення як позитивних, так і усіх негативних характеристик різних алгоритмів сортування, передбачення кінцевого результату. До того ж, треба враховувати головне - чи, можливо, цю задачу задовольнить один з класичних простих алгоритмів сортування.
Список литературы
1. Львов М.С., Співаковський О.В. Основи алгоритмізації та програмування. - Херсон, 1997.
2. Д. Кнут. Искусство программирования ЭВМ: Т.3. Сортировка и поиск. М., МИР, 1978.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
