Реалізація на асемблері алгоритму сортування Шелла

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ

Київський національний університет технологій та дизайну

Кафедра інформаційних  та комп’ютерних технологій

КУРСОВА РОБОТА

з дисципліни

”Системне програмування”

на  тему

«Реалізація на асемблері алгоритму сортування Шелла»

 

 

 

 

Допущена до захисту      Виконав:

“____” ___________ 2011 р.     студент  3-го курсу

Захищена з оцінкою      гр. БЧСП-1-09

____________________      Гончар Є.Ю.

“____” ___________ 2011 р.        

^{(підпис)}

 

Керівник роботи            ст. викл. Півень О.Б.

__________________           ^{(підпис)}.

 

 

 

 

 

 

 

Черкаси 2012 

Форма № У-9.01
Киівський національний університет технології та дизайну
(назва вищого навчального закладу)
Кафедра _____________________________________________________________
Дисципліна __________________________________________________________
Спеціальність ________________________________________________________
Курс ____________        Група ____________         Семестр ____________________
ЗАВДАННЯ на курсовий проект (роботу)  студента
(прізвище, ім’я, побатькові)
1.Тема проекту (роботи)
2.Строк здачі студентом закінченого проекту  (роботи)
3.Вихідні дані до проекту (роботи)
4.Зміст розрахунково-пояснювальної записки (перелік питань, які підлягають розробці)
5.Перелік графічного матеріалу (з точним зазначенням обов’язкових креслень)
6.Дата видачі завдання ________________________________________________
Календарний план
№ п/п	Назва етапів курсового проекту  (роботи)						Строк виконання етапів проекту (роботи)		Примітка
Студент дипломник
		(підпис)
Керівник
		(підпис)                                    (Прізвище, ім’я, по батькові

«_____»____________  _____ р.

 

ЗМІСТ

 

 

ВСТУП

Програмування на мові асемблера вважається складною задачею, причини цього  такі:

Мова асемблера будь-якого процесора суттєво складніша будь-якої мови високого рівня. Щоб скористатись всіма можливостями мови асемблера, треба по крайній мірі знати команди мікропроцесора, а їх число з усіма можливими варіантами переважає 100, їх кількість значно перевищує кількість операторів і ключових слів інших мов високого рівня. Проблема ускладнюється ще тим, що зміни в асемблері виникають набагато швидше ніж в мовах високого рівня, це зв’язано з появою нових мікропроцесорів і відповідно нових команд.

Програміст, який використовує мови асемблера повинен сам слідкувати за розподілом пам’яті та вмістом регістрів, щоб коректно розподіляти і оперувати пам’яттю, в мовах високого рівня це робиться автоматично при допомозі компілятора, але ця обставина має перевагу: можна оптимально розташувати дані в пам’яті, забезпечити максимальну швидкість виконання та мінімальну довжину програми.

Програми на мові асемблера важче  проектувати та підлагоджувати, треба  весь час пам’ятати, що конкретно  знаходиться в кожному регістрів  в даній комірці пам’яті. Прийнято вважати, що розробка програми тільки на мові асемблера, деякого процесора, навіть якщо він поширений не рекомендується. Зрозуміло, що будь-яку програму можна написати тільки з допомогою асемблера, але для цього треба використати набагато більшу кількість команд і час який піде на її виконання і відладку буде набагато більший ніж для мови високого рівня. Набагато вигідніше писати програми на мові високого рівня, а найбільш критичні частини на швидкодії писати на мові асемблера. Наприклад на асемблері можна скласти процедури для реалізації вводу-виводу низького рівня, процедури обробки переривань та деякі інші.

 

Розділ 1 Теоретична частина

1. Алгоритм сортування

Алгоритм сортування - це алгоритм для впорядкування  елементів у списку. У випадку, коли елемент списку має кілька полів, поле, що служить критерієм порядку, називається ключем сортування. На практиці в якості ключа часто виступає число, а в інших полях зберігаються будь-які

дані, котрі  ніяк не впливають на роботу алгоритму.

Алгоритми сортування оцінюються за швидкістю виконання та ефективності використання пам'яті:

Час - основний параметр, що характеризує швидкодію  алгоритму. Називається також обчислювальною складністю. Для впорядкування важливі  найгірша, середня і краща поведінка  алгоритму в термінах потужності вхідного безлічі A. Якщо на вхід алгоритму подається безліч A, то позначимо n = | A |. Для типового алгоритму хорошу поведінку - це O (n log n) і погану поведінку - це O (n2). Ідеальна поведінка для впорядкування - O (n). Алгоритми сортування, що використовують тільки абстрактну операцію порівняння ключів завжди потребують щонайменше в Ω (n log n) порівняннях. Тим не менш, існує алгоритм сортування Хана з обчислювальною складністю O (n log log n log log log n), що використовує той факт, що простір ключів обмежено (він надзвичайно складний, а за О-позначенням ховається досить великий коефіцієнт, що робить неможливим його застосування в повсякденній практиці). Також існує поняття сортуючих мереж. Припускаючи, що можна одночасно (наприклад, при паралельному обчисленні) проводити кілька порівнянь, можна відсортувати n чисел за O (log2 n) операцій. При цьому число n має бути заздалегідь відомо;

Пам'ять - ряд  алгоритмів вимагає виділення додаткової пам'яті під тимчасове зберігання даних. Як правило, ці алгоритми вимагають O (log n) пам'яті. При оцінці не враховується місце, яке займає вихідний масив і незалежні від вхідної послідовності витрати, наприклад, на зберігання коду програми (так як все це споживає O (1)). Алгоритми сортування, що не споживають додаткової пам'яті, відносять до сортування на місці.

Однією з  важливих властивостей алгоритму є  його сфера застосування. Тут основних типів упорядкування два:

1. Внутрішня  сортування оперує з масивами, цілком поміщається в оперативній  пам'яті з довільним доступом до будь-якого осередку. Дані зазвичай упорядковуються на тому ж місці, без додаткових витрат.

В сучасних архітектурах персональних комп'ютерів широко застосовується підкачка і кешування пам'яті. Алгоритм сортування повинен добре поєднуватися з вживаними алгоритмами кешування і підкачки.

2. Зовнішня  сортування оперує з запам'ятовуючими  пристроями великого об'єму, але  з доступом не довільним, а  послідовним (упорядкування файлів). Це накладає деякі додаткові  обмеження на алгоритм і призводить до спеціальних методів упорядкування, які зазвичай використовують додатковий дисковий простір. Крім того, доступ до даних на носії виробляється набагато повільніше, ніж операції з оперативною пам'яттю.

Доступ до носія здійснюється послідовним  чином: у кожен момент часу можна вважати або записати тільки елемент, наступний за поточним. Обсяг даних не дозволяє їм розміститися в ОЗУ.

Також алгоритми  класифікуються за:

- потребами  у додатковій пам'яті або її  відсутності;

- потребами  в знаннях про структуру даних, що виходять за рамки операції порівняння, або відсутності такої.

 

1.2 Відомі алгоритми  сортування

Серед відомих  алгоритмів сортування розрізняють:

  1. За час  O (n2):

     - сортування вибором;

     - сортування вставкою;

     - сортування обміном;

2. За час O (n log n):

     - пірамідальне сортування;

     - швидке сортування;

     - сортування злиттям;

3. За час  O (n)  з використанням додаткової  інформації про елементи:      

     - сортування за розрядами;

     - сортування комірками;

     - сортування підрахунком;

4. За час  O (n log2 n):

     - сортування злиттям модифіковане;

     - сортування Шелла;

5. За час  O(nn!):

     - сортування перестановкою.

 

Сортування  вибором — простий алгоритм сортування лінійного масиву, на основі вставок. Має ефективність n2, що робить його неефективним при сортування великих масивів, і в цілому, менш ефективним за подібний алгоритм сортування включенням. Сортування вибором вирізняється більшою простотою, ніж сортування включенням, і в

деяких випадках, вищою продуктивністю.

Сортування  вибором не є складним в аналізі  та порівнянні його з іншими алгоритмами, оскільки жоден з циклів не залежить від даних у списку. Знаходження  найменшого елементу вимагає перегляду  усіх n елементів (у даному випадку n − 1 порівняння), і після цього, перестановки його до першої позиції. Знаходження наступного найменшого елементу вимагає перегляду n − 1 елементів, і так далі, для (n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n2) порівнянь. Кожне сканування вимагає однієї перестановки для n − 1 елементів (останній елемент знаходитиметься на своєму місці).

Сортування  включенням — простий алгоритм сортування на основі порівнянь. На великих масивах  є значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має цілу низку переваг:

- простота у реалізації;

- ефективний (за звичай) на маленьких массивах;

- ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна O(n + d), де d — кількість інверсій;

- на практиці  ефективніший за більшість інших  квадратичних алгоритмів (O(n2)), як  то сортування вибором та сортування  бульбашкою: його швидкодія рівна n2/4, і в найкращому випадку є лінійною;

- є стабільним алгоритмом.

Сортування  обміном або Сортування бульбашкою є простим алгоритмом сортування. Алгоритм працює таким чином —  у поданому наборі даних (списку чи масиві) порівнюються два сусідні елементи. Якщо один з елементів, не відповідає критерію сортування (є більшим, або ж, навпаки, меншим за свого сусіда), то ці два елементи міняються місцями. Прохід по списку продовжується до тих пір, доки дані не будуть відсортованими. Алгоритм отримав свою назву від того, що процес сортування за ним нагадує поведінку бульбашок повітря у резервуарі з водою. Оскільки для роботи з елементами масиву він використовує лише порівняння, це сортування на основі порівнянь.

Складність  алгоритму у найгіршому у середньостатистичному випадку рівна О(n²), де n — кількість елементів для сортування. Існує чимало значно ефективніших алгоритмів, наприклад, з найгіршою ефективністю рівною O(n log n). Тому даний алгоритм має низьку ефективність у випадках, коли N є досить великим, за винятком рідких конкретних випадків, коли заздалегідь відомо, що масив з самого початку буде добре відсортований.

Швидке сортування (англ. Quick Sort) — алгоритм сортування, добре відомий, як алгоритм розроблений  Чарльзом Хоаром, який не потребує додаткової пам'яті і виконує у середньому  операцій. Однак, у найгіршому випадку робить O(n2) порівнянь. Оскільки алгоритм використовує дуже прості цикли і операції, він працює швидше інших алгоритмів, що мають таку ж асимптотичну оцінку складності.

Ідея алгоритму  полягає в переставлянні елементів  масиву таким чином, щоб його можна  було розділити на дві частини  і кожний елемент з першої частини  був не більший за будь-який елемент  з другої. Впорядкування кожної з  частин відбувається рекурсивно. Алгоритм швидкого сортування може бути реалізований як у масиві, так і в двозв’язному списку.

Швидке сортування є алгоритмом на основі порівнянь, і  не є стабільним.

Сортування  злиттям — алгоритм сортування, в основі якого лежить принцип  Розділяй та володарюй. В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається — тоді решта іншої колони додається до нової.

Під час сортування в дві допоміжні черги з  основної поміщаються перші дві  відсортовані підпослідовності, які  потім зливаються в одну і результат  записується в тимчасову чергу. Потім з основної черги беруться наступні дві відсортовані підпослідовності і так до тих пір доки основна черга не стане порожньою. Після цього послідовність з тимчасової черги переміщається в основну чергу. І знову продовжується сортування злиттям двох відсортованих підпослідовностей. Сортування триватиме до тих пір поки довжина відсортованої підпослідовності не стане рівною довжині

самої послідовності. 

Розділ 2 Практична  частина

2.1 Сортування Шелла

Сортування Шелла (англ. Shell sort) - алгоритм сортування, що є вдосконаленим варіантом сортування вставками. Ідея методу Шелла полягає в порівнянні елементів, що стоять не тільки поруч, але і на певній відстані один від одного.

Алгоритм базується на двох тезах:

1. Сортування вставками ефективне  для майже впорядкованих масивів.

2. Сортування вставками неефективне, тому що переміщує елемент тільки на одну позицію за раз.

Тому сортування Шелла виконує  декілька впорядкувань вставками, кожен  раз порівнюючи і переставляючи  елементи, що знаходяться на різній відстані один від одного. Сортування не є стабільним(не гарантує збереження порядку елементів, які вже відсортовані).

При сортуванні Шелла спочатку порівнюються і сортуються між собою значення, віддалені один від одного на деякій відстані (про вибір значення див. нижче). Після цього процедура повторюється для деяких менших значень, а завершується сортування Шелла упорядкуванням елементів при (тобто звичайної сортуванням вставками). Ефективність сортування Шелла в певних випадках забезпечується тим, що елементи «швидше» встають на свої місця (в простих методах сортування, наприклад, бульбашкової, кожна перестановка двох елементів зменшує кількість інверсій в списку максимум на 1, а при сортуванні Шелла це число може бути більше ).