Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методи сортування та черги
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра СКС
Інформація про роботу
Рік:
2012
Тип роботи:
Курсова робота
Предмет:
Програмування частина 4 Технологія системного програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет «Львівська політехніка»
Інститут дистанційного навчання
Кафедра СКС
КУРСОВА РОБОТА
з дисципліни «Програмування»
на тему Методи сортування та черги»
Варіант № 10
Завдання на курсову роботу:
Задача на використання черги: масив з 10 елементів використовується для реалізації черги. На вході задана послідовність невід’ємних цілих чисел. Якщо число n більше нуля, то воно додається в чергу; якщо n=0, то перший елемент черги вилучається. Написати програму, яка читає послідовність, працює з чергою як з циклічною структурою і друкує повідомлення про помилку при кожному відшуку аварійної ситуації (маються на увазі ситуації коли або черга [тобто масив з 10 елементів] буде повністю заповнений і вставка елементу в чергу неможлива, або черга пуста [тобто не містить жодного елемента] і вилучення з такої черги неможливе. Наглядно відобразити на екрані всі зміни, що відбуваються в черзі.
Задача на сортування: на вході задано масив з N елементів. Використовуючи метод пірамідального сортування, відсортувати заданий масив і вивести його на екран.
ЗМІСТ
ВСТУП……………………………………………………………………….
4
1.
ТЕОРЕТИЧНА ЧАСТИНА ДО ЗАДАЧ…………………………….
6
1.1
Задача на дослідження внутрішнього представлення числових, логічних, рядкових даних та масивів і множин……………………….
6
1.1.1 Цілочисельний тип………………………………………………..
6
1.1.2 Дійсний тип………………………………………………………..
7
1.1.3. Рядкові типи………………………………………………………
9
1.1.4. Логічний тип………………………………………………………
10
1.1.5 Тип масив…………………………………………………………..
10
1.1.6 Тип множина……………………………………………………….
11
1.2
Задача на використання черги………………………………………….
12
1.3
Задача на сортування (Пірамідальне сортування)…………………….
14
2.
ОПИС АЛГОРИТМУ ЗАДАЧІ……………………………………….
16
3.
ЗАДАЧА НА СОРТУВАННЯ…………………………………………
19
4.
РЕЗУЛЬТАТИ ТЕСТУВАННЯ………………………………………
23
4.1
Результат дослідження внутрішнього представлення числових, логічних, рядкових даних та масивів і множин……………………….
23
4.2
Результати тестування програми на використання черги…………….
26
ВИСНОВКИ…………………………………………………………………
28
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ……………………………..
29
ВСТУП
Програма написана на будь-якій мові програмування, являється описаною послідовністю дій (операцій), котрі необхідно виконати з деякою сукупністю даних.
Будова конкретної обчислювальної машини і особливості трансляторів визначають внутрішнє представлення даних - їх розміщення в пам’яті обчислювальної машини.
Зрозуміло, що кожен рівень представлення даних важливий. Наприклад, обрана математична модель може не в цілому або не точно відображати властивості реальних об’єктів і існуючі між ними зв’язки. В свою чергу, синтаксис окремої алгоритмічної мови може значно обмежувати можливості опису логічної структури даних, або ж робить ці описи складними і громіздкими. Неможливим або неефективним виконання синтаксично (і самантично) правильної програми можуть зробити характеристики комп’ютера (малий об’єм пам’яті, низька швидкодія). Тому структури даних та їх внутрішнє представлення, а також зв’язки між ними є одним з важливих питань в програмуванні.
Найпростішими об’єктами, що представлені в більшості математичних моделей є числа, рядки символів, логічні значення. Цим об’єктам відповідає наявність в алгоритмічних мовах стандартних типів (цілих, дійсних, символьних, логічних) і простих змінних, котрі приймають значення вказаних типів.
Для побудови алгоритмів надзвичайно важливі способи організації дій - допустимі структури, а також способи організації інформації - структури даних (масиви, записи, множини, черги, стеки, списки, таблиці).
З іншого боку відомо, що обчислювальні машини використовують дані, внутрішнє представлення котрих відображається у двійкових числах (розрядах). Для людини таке представлення незручне через велику кількість цифр в числі, але воно є найкращим для електронних схем , оскільки два значення (0 і 1 ) можна надійно кодувати наявністю чи відсутністю електричного струму, заряду або магнітного поля. Таким чином всі дані в ЕОМ (числа, множини, послідовності) представляються у вигляді великої сукупності розрядів.
Для прикладу, потрібно відобразити положення об’єкта в просторі. На першому кроці береться пара дійсних чисел (декартові або полярні координати). На другому кроці вони представляються як числа з плаваючою комою: кожному дійсному числу x ставиться у відповідність пара цілих чисел, означаючих мантису f і порядок e (x=f ( 2e). На третьому кроці, коли враховується, що дані повинні бути розміщені в пам’яті ЕОМ, ми отримуємо двійкове позиційне представлення цілих чисел, і на останньому кроці двійкові числа можуть бути представлені напрямом магнітного поля в магнітному запам’ятовуючому пристрої. Видно, що перший крок визначається самою поставленою задачею, а останній тісно пов’язаний з використовуваним обчислювальним пристроєм.
Звичайно, оперуючи великими кількостями інформації, бажано щоб вона була певним чином відсортована. Для цього використовують різноманітні методи впорядкування, тобто сортування інформації.
Існує і інша проблема при роботі з великими об’ємами інформації - як зберегти і так організувати дані, щоб забезпечити найшвидшу їх вибірку та обробку. Цю проблему вирішують програми пошуку, котрі забезпечують швидкий і якісний пошук необхідної інформації.
1. ТЕОРЕТИЧНА ЧАСТИНА ДО ЗАДАЧ
1.1. Задача на дослідження внутрішнього представлення числових, логічних, рядкових даних та масивів і множин
1.1.1 Цілочисельний тип
Turbo Pascal містить п”ять вбудованих цілочисельних типів:
- Shortint (коротке ціле),
- Integer (ціле),
- Longint (довге ціле),
- Byte (ціле довжиною в байт) ,
- Word (ціле слово).
Кожен тип означає певну підмножину цілих чисел, як показано в таблиці 1.
Таблиця 1: Вбудовані цілочисельні типи
Тип
Діапазон
Формат
Shortint
-128 .. 127
8 біт із знаком
Integer
-32768 .. 32767
16 біт із знаком
Longint
-2147483648 .. 2147483647
32 біти із знаком
Byte
0 .. 255
8 біт без знака
Word
0 .. 65535
16 біт без знака
Примітка 1: На нижче приведених рисунках msb означає найбільший значущий біт і lsb означає найменший. Крайні ліві елементи зберігаються на великих адресах. Наприклад, для значення типу Real, e зберігається в першому байті, f - в наступних п’яти байтах і s - в найбільшому значущому біті останнього байта, де е - порядок, f - мантиса, s - знак.
Тип Integer
2-х байтовий (16-и бітний) тип Integer ділиться на два поля:
1 15
s
f
msb isb
Типи ShortІnt і LongІnt у пам”яті представляються аналогічно до
типу Integer, відрізняючись лише величиною поля мантиси.
Тип Byte
1-но байтовий (8-ми бітний) тип Byte має одне поле:
0 8
f
Тип Word подібний до типу Byte, відрізняючись тим, що займає не один, а два байти.
1.1.2 Дійсний тип
До дійсного типу відноситься підмножина дійсних чисел, котрі можуть бути представлені в форматі з плаваючою комою з фіксованою кількістю цифр.
Існує п”ять видів дійсних типі: Real, Single, Double, Extended і Comp.
Вони зберігають двійкове представлення знака (+/(), експоненти і мантиси.
Представлення числа має вигляд:
+/( мантиса х 2**експонента
де мантиса має один біт зліва від точки двійкового числа
(тобто 0 <= мантиса < 2).
Дійсні типи відрізняються діапазоном і точністю зв”язаних з ними значень ( таблиця 2)
Таблиця 2 Дійсні типи даних
Тип
Діапазон
Точність
Розмір в байтах
Real
2.9x10**-39 .. 1.7x10**38
11-12
6
Single
1.5x10**-45 .. 3.4x10**38
7-8
4
Double
5.0x10**-324 .. 1.7x10**308
15-16
8
Extended
3.4x10**-4932 .. 1.1x10**4932
19-20
10
Comp
-2**63 + 1 .. 2**63 - 1
19-20
8
Примітка 2: Складний тип Comp містить тільки цілочисельні значення в діапазоні від -2**63 + 1 до 2**63 - 1, що приблизно дорівнює від -9.2x10**18 і до 9.2x10**18.
Тип Real.
6-ти байтовий (48-ми бітовий) тип Real ділиться на три поля:
1 39 8
s
f
e
msb lsb msb lsb
Тип Single
4-х байтовий (32-х бітний) тип Single ділиться на три поля:
1 8 23
s
e
f
msb lsb msb lsb
Тип Double.
8-ми байтовий (64-х бітний) тип Double ділиться на три поля:
1 11 52
s
e
f
msb lsb msb lsb
Тип Extended.
10-и байтовий (80-и бітний) тип Extended ділиться на три поля:
1 15 1 63
s
e
і
f
msb lsb msb lsb
Тип Comp.
8-и байтовий (64-х бітний) тип Comp ділиться на два поля:
1 63
s
d
msb lsb
Тип Pointer.
Тип Pointer зберігається як подвійне слово з частиною зміщення в молодшому слові і сегментною частиною в старшому слові. Значен-ня вказівника nil зберігається як 0 в обох словах.
1.1.3. Рядкові типи
Значенням рядкового типу є послідовність символів з динамічним атрибутом довжини (в залежності від дійсної кількості символів при виконанні програми) і константним атрибутом разміру в діапазоні від 1 до 255.
Поточне значення атрибуту довжини можна отримати з допомогою стандартної функції Length.
d
s1
s2
s3
...
sn
де - d - довжина рядка;
si - ASCI-код символів, що входять у рядок
Відношення між будь-якими двома рядковими значеннями встановлюється відповідно до відношення порядку між значеннями символів у відповідних позиціях. В двох рядках різної довжини кожен символ довшого рядка без відповідного символа в коротшому рядку набуває значення "більше"; наприклад, 'xs' більше, ніж 'x'. Пусті рядки можуть дорівнювати тільки іншим пустим рядкам і вони являються рядками з найменшим значенням.
1.1.4. Логічний тип
Значення логічного типу позначаються вбудованими ідентифіка-торами констант False і True. Оскільки логічний тип є перерахову-вальним, між ними встановлено наступні співвідношення:
- False < True
- Ord(False) = 0
- Ord(True) = 1
- Succ(False) = True
- Pred(True) = False
1.1.5 Тип масив
Масив зберігається як неперервна послідовність змінних того типу, з яких оголошено масив. Компонента з найменшим індексом зберігається по найменшій адресі пам’яті. Багатомірний масив зберігається так, що більш правий індекс збільшується першим.
В типах індексу, по одному для кожної величини масиву, вказується кількість елементів. Допустимими типами індексу є всі порядкові типи, за винятком Longint і піддіапазонів Longint. Масив може бути проіндексований по кожній величині всіма значеннями відповідного типу індексу; кількість елементів тому дорівнює кількості значень в кожному типі індексу. Кількість величин - необмежена.
Приклад типу масив:
array [1..100] of Real
Якщо тип компоненти в типі масив також является масивом, то результат можна розглядати як масив масивів або як один багатомірний масив. Наприклад,
array [Boolean] of array [1..10] of array [Size] of Real
інтерпретується компілятором так само, як
array [Boolean, 1..10, Size] of Real.
Крім того, можна виразити
packed array [1..10] of packed array [1..8] of Boolean
як packed array [1..10,1..8] of Boolean
Для доступу до елементів масиву необхідно вказати ідентифікатор масиву з одним чи кількома індексами в дужках.
Тип масив, що має вигляд
packed array [M..N] of Char,
де M менше, ніж N, називаєтся упакованим рядковим типом (слово packed можна пропустити, оскільки воно не вказує на дію в Turbo Pascal). Упакований рядковий тип має де-які властивості, не характерні для інших типів масивів.
1.1.6 Тип множина
Множина (set) - це бітовий масив, де кожен біт показує є даний елемент в множині чи ні. Максимальна кількість елементів в множині - 256, тому множина ніколи не займає більше 32 байт. Кількість байт, що займає множина вираховується як:
ByteSize = (Max div 8) - (Min div 8) + 1
де Min и Max - нижня і верхня межі базового типу даноі множини. Елемент Е займає байт з номером:
ByteNumber = ( E div 8) - (Min div 8)
і позиція біта всередині байта:
BitNumber = E mod 8
де Е представляє порядкове значення елемента.
Базовий тип не повинен мати більше ніж 256 можливих значень і порядкові значення верхньої і нижньої межі базового типу не повинні перевищувати діапазону від 0 до 255. Тому базовий тип множина не може бути Shortint, Integer, LongInt, Word.
Будь-який тип множина може приймати значення [], що називається пустою множиною.
1.2 Задача на використання черги
Черги - це одна з простих і одночасно досить типова структур даних.
Проблема черги виникає при наявності деякого механізму обслуговування, котрий може виконувати замовлення послідовно, одне за одним. Якщо при поступленні нового замовлення обслуговуючий пристрій вільний, він може без затримки приступити до його виконання. Але коли він вже виконує раніше отриману задачу, то нова задача повинна поступити в кінець черги. Кожен раз, коли обслуговуючий пристрій закінчив виконання поточної задачі, він приступає до виконання задачі з початку черги, причиму ця задача виключається з черги, а першою в черзі стає наступна за нею задача. Якщо задачі поступають нерегулярно, то їх черга може збільшуватись чи зменшуватись, або залишатись пустою коли всі наявні задачі виконані, а нові ще не поступили.
Над структурою черги можуть виконуватись операції двох видів:
- вилучення першого елементу черги;
- занесення елементу в кінець черги.
Коли черга порожня, то вказівники на її початок і кінець співпадають (рисунок 1).
( Початок
( Кінець
Рисунок 1.
У випадку коли, наприклад, до виконання поступили задачі А,В,С, вони встановлюються в чергу і вказівник кінця черги відповідно зміщується (рисунок 2).
( Початок
А
В
С
( Кінець
Рисунок 2.
Коли задача А виконана , вона вилучається з черги, а вказівник початку черги зміщується вказуючи на наступний елемент черги ( це один з варіантів, можна, наприклад, зсувати всі наступні елементи на одну позицію вперед) (рисунок 3).
( Початок
В
С
( Кінець
Рисунок 3.
Якщо в цей час поступає на виконання задача D, вона поміщається в кінець черги і відповідно вказівник кінця черги переміщується, вказуючи на неї (рисунок 4)
( Початок
В
С
D
( Кінець
Рисунок 4.
Оскільки в реальних умовах розмір черги обмежений, найчастіше на практиці використовується кільцевий спосіб реалізації черги (рисунок 5), тобто з’єднуються початок і кінець черги, залишаючи вказівники її початку і кінця. Це дає змогу використовувати звільнені місця в черзі, тобто економити пам’ять.
Кінець
D
C
B
A
Початок
Рисунок 5.
Звичайно в такому виконанні існує проблема переповнення черги, тобто ситуація коли всі місця в черзі заповнені. Такі ситуації потрібно передбачати програмними засобами. В різних мовах програмування існує можливість використовувати як динамічні так і статичні дані для програмної реалізації черг.
1.3 Задача на сортування (Пірамідальне сортування)
Саме слово “сортування” (sorting) визначається як “розподіл, відбір по сортах, поділ на категорії”. В програмуванні цьому слову надають більш вузького змісту, позначаючи ним сортування деяких елементів в зростаючому чи спадаючому порядку, хоч цей процес вірніше було б назвати впорядкуванням.
Методи сортування часто відображають оригінальний підхід до прблем програмування в цілому і є хорошою ілюстрацією ідей аналізу алгоритмів.
Нехай потрібно впорядкувати N елементів (записів)
R1 , R2 , R3 , ... , RN
Сукупність таких записів називають файлом. Кожен запис Rі має ключ КІ , який і керує процесом сортування. Задача сортування знайти таку перестановку записів р(1), р(2), .. , р(N), після якої ключі розташувалися б у неспадному (незростаючому) порядку:
Кр(1) ( Кр(2) ( ... ( Кр(N)
(Кр(1) ( Кр(2) ( ... ( Кр(N))
Звичайно сортування поділяють на два класи:
- внутрішнє (коли всі записи зберігаються в швидкій оперативній пам’яті);
- зовнішнє (коли всі записи там не поміщаються).
При внутрішньому сортуванні є більш гнучкі умови для побудови структур даних і доступу до них, зовнішнє ж показує, як бути в умовах дуже обмеже-ного доступу.
При оцінці методів сортування існує декілька взаємопов’язаних і часто конфліктуючих аспектів. Ось найважливіші з них:
- час, затрачений на розробку програми;
- час виконання сортування;
- обсяг пам’яті, потрібний для роботи програми.
Щодо часу виконання сортування, то він в основному залежить від початкової послідовності даних. А змінюється він для різних методів від N logN до N2 (де N - кількість елементів).
Існує декілька основних груп методів сортування:
- сортування вставками (прості вставки, бінарні вставки, метод Шелла, вставки в список);
- обмінне сортування (метод бульбашки, паралельне сортування Бетчера, “швидке сортування”, обмінне порозрядне сортування);
- сортування за допомогою вибору (простий вибір, вибір з дерева, пірамідальне сортування);
- сортування злиттям;
- сортування підрахунком;
- інші спеціальні методи сортування.
Всі ці методи відрізняються швидкістю сортування, використанням пам”яті для його реалізації та іншими критеріями, що дає змогу використовувати різні методи сортування для кожного конкретного випадку.
2. ОПИС АЛГОРИТМУ ЗАДАЧІ
2.1. Щоб відобразити внутрішнє представлення даних в програмі вико-ристовується вбудована директива Turbo Pascal absolute яка дає доступ до кожного окремого байта числа того типу, який ми досліджуємо.
По суті директива absolute накладає адресу числа на адресу (наприклад в нашому випадку) масиву.
Bit : array [ 1..N] of byte absolute Chyslo;
Такий запис означає, що масив елементів Bit та змінна Chyslo розміщені
в пам”яті за однією і тією ж адресою.
Для кожного типу N буде залежати від довжини змінної цього типу (в байтах).
Програма подає результати в шіснадцятковій формі.
Для видачі результату в шіснадцятковій формі використовується масив Hex описаний як константа:
Hex: array [0..15] of char = ‘ 0123456789ABCDEF ‘
Це дає можливість використовуючи стандартну процедуру виводу write виводити результат
write (Hex [Bit[i] div 16], Hex [Bit[i] mod 16]);
В даній задачі представлення кожного окремого типу оформлене в виг-ляді процедур: TypeInteger, TypeRеal, TypeString, TypeBoolean, TypeSet, TypeArray. У свою чергу процедури вміщені в модуль utypepas.tpu.
Основна програма забезпечує інформацію, тобто створює меню для задачі, і відповідно до вибраного типу використовує потрібну процедуру з модуля utypepas.tpu.
Таким чином, вибравши тип Integer або Rеal, використовуються процедури TypeInteger або TypeRеal котрі запрошують ввести число відповідного типу (цілого або дійсного) і побайтово виводять результат (тобто масив Bit, накладений на введене число).
Процедура TypeString використовується для виведення внутрішнього представлення рядкового типу String. Ввівши рядок символів отримуємо результат в шістнадцятковій формі, тобто вивід масиву Bit , який накладений на рядок. Це дає змогувивести кожен байт рядка і побачити як цей рядокрозміщений в пам”яті компютера.
Процедура TypeBoolean накладає на змінну типу Boolean масив з одного байта. Результат складається з двох частин:
- вивід змінної при значенні false;
- вивід змінної при значенні true.
Процедура TypeArray використовується для виведення представлення масивів. В ній описано масив з пяти елементів типу char (cимвольного), на який накладено масив Bit типу byte задопомогою директиви absolut. В результаті отримуємо побайтовий вивід кожного елемента масиву Masiv (типу char) в шістнадцятковій формі.
На відміну від попередніх процедур, які дають вивід результатів в шістнадцятковій формі, процедура TypeSet виводить внутрішне пред-ставлення в двійковій формі для кращого відображення структури множин. Адже, щоб побачити як саме розміщуються елементи в множині, потрібен доступ до кожного окремого біта множини.
2.2. Ця задача вимагає наглядно відобразити, що собою являє така структура даних як черга, та відобразити дії та зміни, які можуть відбуватися в черзі. Ввід даних для програми відбувається в текстовому режимі.
Для реалізації черги в пам”яті комп”ютера використовуються такі процедури та функції:
procedure QueneInit - встановлює початкові параметри черги (вказівники на початок і кінець, переповнення);
procedure InsertInQuene - ставить елемент в чергу. Перевіряє умову переповнення черги, причому працює з чергою, як з циклічною структурою;
function RemoveFromQuene - вилучає елумент з черги;
function QueneIsEmpty - перевіряє чи не є черга порожньою при спробі вилучити з неї елемент.
В програмі широко використовується графічні можливості Turbo Pascal 7.0.
Процедура InitWindow - ініціалізує графіку, розбиваючи екран на декілька умовних вікон:
- [Enter line] - використовується для зображення відповідного вхідного рядка елементи якого використовуються в якості елементів черги;
- [Quene] - це вікно використовується власне для представлення самої черги на екрані та відображення змін, які у ній відбуваються;
- [Result line] - використовується для виводу інформації про дії, які в даний момент відбуваються у черзі (тобто, коли черга порожня, коли повна, про внесення та вилучення інформації, про закінчення програми).
Всі вікна відображені за допомогою графічних процедур Bar i Line.
Для кращого відображення всіх змін у черзі використовується процедура InitBegEnd, яка за допомогою процедур роботи з відеопам”яттю (GetMem, GetImage, PutImage) забезпечує переміщення вказівників Beg (початок) і End (кінець) на відповідні місця в черзі.
( Beg
8
9
10
( End
Отже програма зчитує вхідний рядок, виводить його у вікні Enter line і починає опрацьовувати елементи рядка. Якщо елемент не дорівнює нулю він встановлюється в чергу, при цьому вказівник зміщується на кінець черги (End) і в вікні для рерультатів Result line видається повідомлення про вставку елемента в чергу (Ok! Insert in quene.) При цьому перевіряється булівська змінна QueneIsFul, яка є індикатором переповнення черги. Вставка у чергу відбувається лише за умови що QueneIsFul = false інакше програма видає звуковий сигнал і повідомлення про переповнення черги (Sorry! Quene is full).
Якщо елемент вхідного рядка дорівнює нулю, то перший елемент черги (тобто елемент відмічений вказівником початку черги) вилучається, а вказівник на початок черги зміщується наїї наступну комірку. Вилучення з черги відбувається за умови, що булівська функція QueneIsEmpty = false (тобто черга не є порожньою) інакше програма видає звуковий сигнал - повідомлення про те, що в черзі немає елементів(Sorry! Quene is empty!). Функція QueneIsEmpty набирає значення true якщо співпадають вказівники початку і кінця черги та змінна QueneIsFull = false.
3. Задача на сортування
Пірамідальне сортування відноситься до внутрішнього сортуван-ня вибором.
Назвемо файл ключів К1, К2, ... , КN “пірамідою”, якщо
K[J/2] ( KJ, при 1 ( [J/2] ( J ( N (1)
В цьому випадку К1 ( К2 , К1 ( К3, К2 ( К4 і т.д., з чого випливає, що найбільший ключ виявляється на вершині піраміди
К1 = max(К1, К2, ... , КN)
Ефективний підхід до задачі побудови піраміди запропонував Р.І.Флойд
Нехай нам вдалось розмістити файл таким чином, що
K[J/2] ( KJ, при l ( [J/2] ( J ( N (2)
де l - деяке число ( 1. У початковому файлі ця умова виконується “автоматично” для l=N/2. Отже можна зменшувати l на одиницю поки не буде досягнута умова (1).
Таким чином алгоритм пірамідального сортування буде виглядати так:
крок 1: [Початкові установки]
l:=(N/2)+1; r:=N;
крок 2: [Зменшити l або r]
Якщо l > 1 , то l:=l-1;
R:=R[l];
K:=K[l]
(Якщо l > 1, то це означає, що вхідний файл перетворюється в “піраміду”; якщо l=1 то значить ключі К1, К2, ... , КN вже утворюють “піраміду”)
Інакше R:=R[r]
K:=K[r]
R[r]:=R[1]
r:=r-1
якщо виявилось, що r=1, то R[1]:=R завершити роботу.
крок 3: [Приготуватьсь до “просіювання”]
J:=1
(до цього моменту K[J/2] ( K[J] при l < [J/2] < J ( r, а записи R[k] займають свої кінцеві значення {r < k ( N}).
крок 4: [Просунутись вниз]
i:=J; J:=2*i
якщо J<r, то перейти до кроку 8
якщо J=r, то перейти до кроку 6
якщо J>r, то перейти до кроку 5
крок 5: [Знайти “більшого” сина]
якщо K[J] < K[J+1], то J:=J+1;
крок 6: [Більше К?]
якщо K ( K[J], то перейти до кроку 8
крок 7: [Підняти вверх]
якщоR[i]:=R[J], то перейти до кроку 4
крок 8: [Занести R]
R[i]:=R (На цьому алгоритм “просіювання” закінчується).
Перейти до кроку 2.
Цей алгоритм можна представити схематично, як вказано на нижчеприведеному рисунку 7.
В програмі алгоритм просіювання здійснюється процедурою SiftElem, а власне пірамідальне сортування процедурою HeapSort.
Аналізуючи метод пірамідального сортування, можна зробити вис-новок, що він досить ефективний, особливи при великих значеннях N.
Алгоритму необхідно N/2 кроків, котрі просіюють елементи через log(N/2), log(N/2-1), .. , log(N-1) позицій (береться ціла частина логарифму при основі 2). Отже, в найгіршому випадку, метод пірамідального сортування потребує N logN кроків, що є однією з найвигідніших властивостей цього методу.
Експериментально перевірено, що загальний час роботи такого алгоритму, в середньому, дорівнює 16*N*log2 N + 0,2*N одиниць.
Рисунок 7 Схема алгоритму пірамідального сортування.
Примітка: Кроки 3,4,5,6,7,8 називають алгоритмом просіювання.
4. Результати тестування
4.1. Результат дослідження внутрішнього представлення числових, логічних, рядкових даних та масивів і множин
4.1.1 Цілочисельний тип.
Наприклад, візьмемо для дослідження в першому випадку додатнє число 1980. Переведемо його в шістнадцяткову форму (програма видає результат в шістнадцятковій формі)
1980 16
1968 123 16
12 112 7
11
Отже 198010=07BC16
Очікуваний результат : 07ВС
Отриманий результат : 07BC
У другому випадку візьмемо від”ємне число -1980. Представимо це число без знака у двійковій формі:
07BC16=00000111101111002
Щоб перевести двійкове число у від”ємне інвертуємо його і до молодшого розряду додаємо 1
+1111100001000011
1
1111100001000100
( ( ( (
F 8 4 4 Отже -1980 10=F84416
Очікуваний результат : F844
Отриманий результат : F844
4.1.2 Дійсний тип.
Також візьмемо відємне і додатнє числа . Наприклад
- додатнє число 2.08
Переводимо його у двійкове
х0.08 х0.28 х0.48 х0.68 х0.88 х0.08
16 16 16 16 16 16 (((
1.28 4.48 7.68 10.88 14.08 1.28
Подальше множення приводить до циклічного повторення чисел 147АЕ,
тому
2.08 = 02.147АЕ147АЕ...= 0010.00010100011110101110...
Нормуємо число , виконуємо зсув вліво на один розряд,щоб отримати лише одну одиниць перед комою.
Визначаємо порядок. Оскільки ми зсунули число на 1 розряд отже порядок буде:
(129+1)10 = 13010 = 8216 =100000102
Число додатнє отже першу 1 замінюємо на 0
100001010001111010111000010100011110101110...
При обмеженні розрядною сіткою округлюємо число при потребі . В результаті отримуємо
0000
0101
0001
1110
1011
1000
0101
0001
1110
1100
1000
0010
6 байт
5 байт
4 байт
3 байт
2 байт
1 байт
(порядок)
( (
( (
( (
( (
( (
( (
0 5 1 Е В 8 5 1 Е С 8 2
Очікуваний результат : 051ЕВ851ЕС82
Отриманий результат : 051ЕВ851ЕС82
-від”ємне число -2.08 :
Для від”ємного числа порядок не змінюється, першу 1 не замінюємо на 0, а залишаємо:
1000
0101
0001
1110
1011
1000
0101
0001
1110
1100
1000
0010
6 байт
5 байт
4 байт
3 байт
2 байт
1 байт
(порядок)
( (
( (
( (
( (
( (
( (
8 5 1 Е В 8 5 1 Е С 8 2
Очікуваний результат : 851ЕВ851ЕС82
Отриманий результат : 851ЕВ851ЕС82
4.1.3 Рядковий тип
Рядки представляються як масив з n+1 елемента, де n - кількість символів в рядку. В першому елементі масиву зберігається довжина b
інших ASCII-коди символів.Нехай ми ввели рядок:”ЗЛМ”.Його довжина 3(03).ASCII-коди символів
‘З‘ - 13510 - 8716
‘Л‘ - 13910 - 8В16
‘М‘ - 14010 -
20.11.2013 19:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора