Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
МОДЕЛЬ РЕАЛІЗАЦІЇ ОБЧИСЛЮВАЛЬНОГО ЕКСПЕРИМЕНТУ В СЕРЕДОВИЩІ WebOAP
Інформація про навчальний заклад
ВУЗ:
Херсонський державний університет
Інститут:
Не вказано
Факультет:
РТ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2011
Тип роботи:
Магістерська робота
Предмет:
Інформатика та обчислювальна техніка
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ,
МОЛОДІ ТА СПОРТУ УКРАЇНИ
ХЕРСОНСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ
ФАКУЛЬТЕТ ФІЗИКИ, МАТЕМАТИКИ ТА ІНФОРМАТИКИ
ЗАТВЕРДЖУЮ
до захисту в ДЕК
Перший проректор університету
_________професор О.В. Мішуков
“___”___________ 2011 р.
САГАН РОМАН ВАЛЕНТИНОВИЧ
МОДЕЛЬ РЕАЛІЗАЦІЇ ОБЧИСЛЮВАЛЬНОГО ЕКСПЕРИМЕНТУ В СЕРЕДОВИЩІ WebOAP
8.080201. ІНФОРМАТИКА
Випускна робота освітньо-кваліфікаційного рівня «Магістр»
ПОГОДЖЕНО
Декан факультету Науковий керівник
________ доцент Кузьмич В.І. _______ професор О.В Співаковський “___”___________ 2011 р. “___”___________ 2011 р.
Завідувач кафедри інформатики Рецензент
______ професор О.В Співаковський ____________________________
“___”___________ 2011 р. ___”___________ 2011 р.
Херсон – 2011 ЗМІСТ
Вступ 3
Розділ 1. Оцінювання складності алгоритмів 7
1.1. Визначення вимог алгоритмів 7
1.2. Оцінка програм (оцінка алгоритму сортування) 10
1.3. О-складність алгоритмів та їх аналіз 12
Висновки до розділу 1 21
Розділ 2. Алгоритми сортування 22
2.1. Прості алгоритми сортування 22
2.2. Складні алгоритми сортування .33
Висновки до розділу 2 38
Розділ 3. Розробка модуля результатів обчислювального експерименту 41
3.1. Структура інтегрованого середовища WebОАП 41
3.2. Принцип роботи обчислювального експерименту 44
3.3. Модуль обробки результатів обчислювального експерименту 47
3.4. Порівняльна характеристика старої та нової версій продукту 51
3.5. Технології, які використовувались під час розробки продукту 53
Висновки до розділу 3 53
Висновки 55
Список використаних джерел 57
ВСТУП
Сучасне суспільство дедалі більше набирає рис інформаційного. При цьому, інформаційне суспільство вимагає нового, більш якісного рівня освіти й нових методів її надання. Ці вимоги зумовлені більшим залученням людей у процеси, де потрібна висока вузькопрофесійна освіченість, а також постійною потребою в перекваліфікації працівників, оскільки технології розвиваються дуже швидко.
Більшість вищих навчальних закладів України вже не в змозі оперативно змінювати навчальні курси, швидко реагувати на зміну запитів споживачів освітніх послуг.
На фоні цих тенденцій вимоги суспільства до освіти помітно змінилися. Системи дистанційного навчання набувають актуального значення в Україні, а сучасні інформаційні технології дозволяють задовольнити запити спільноти.
Дистанційні курси розміщуються на Web-сторінці, з додатком способів самотестування, а контактування із студентом здійснюється за допомогою інтерактивних засобів (відео-, аудіо-зв’язок, звичайний чат) або електронної пошти.
В Україні розвиток систем дистанційного навчання знаходиться на початковій стадії запровадження. Використання дистанційної освіти здійснюється переважно у складі звичайної освіти.
Деякі вищі навчальні заклади освіти України запроваджують паралельне використання дистанційної освіти з метою залучення більшої кількості студентів та напрацювання досвіду роботи з новітніми інформаційними технологіями для подальшого повного переходу лише на дистанційну систему навчання.
За ступенем використання систем віртуальної освіти в Україні можна визначити три напрями:
Навчальні заклади, вся робота яких будується виключно на інтернет-технологіях. Через всесвітню мережу здійснюється все: вибір навчального курсу, його оплата, заняття із студентами, передача контрольних завдань та їх перевірка, а також складання проміжних і підсумкових іспитів. Такі учбові центри називаються віртуальними університетами. Цей напрямок тільки починає активно запроваджуватись.
Найбільш численний напрямок складають навчальні заклади, що поєднують різні традиційні форми денного і дистанційного навчання з технологічними інтернет-нововведеннями. Наприклад, деякі вищі навчальні заклади частину своїх програмних курсів переводять у віртуальну форму, зокрема, створюють лінгафонні класи для навчання іноземним мовам без викладача. У свою чергу, центри дистанційного навчання, хоч і спираються на інтернет-технології, але в той же час не відмовляються від практики проведення очних екзаменаційних сесій. У будь-якому випадку, комп’ютеризованою є тільки частина процесу.
Навчальні центри, для яких інтернет служить лише внутрішнім комунікаційним середовищем. Вони можуть створювати для себе сайти-візитівки, на яких розміщують інформацію про навчальні програми (плани), семінари, розклад студентських занять, університетські новини, фотографії і віртуальні екскурсії, а також бібліотечні каталоги. По суті, це всього лише реклама традиційних вищих навчальних закладів, що сама по собі не несе ніякого освітнього навантаження.
На базі Херсонського державного університету створено «Херсонський віртуальний університет», організація роботи якого дозволяє у зручній для користувача формі надавати освітні послуги. Крім отримання інформації студенти і викладачі мають можливість користуватися різноманітними інтегрованими середовищами, серед яких «Віртуальна біологічна лабораторія, 10 клас», «Основи алгоритмізації та програмування», «Історія педагогіки», «Віл’ям Шекспір та Ренессанс», «Математична логіка» тощо.
Команда магістрантів 2011 року створює нову версію програмного середовища, в якому реалізується демонстрація порівняння ефективності алгоритмів пошуку та сортування. Основною перевагою середовища є організація самостійної роботи. Воно містить наступні компоненти:
парсер;
редактор програмного коду;
візуалізатор процедур пошуку та сортування;
модуль обробки результатів обчислювального експерименту.
Метою магістерського дослідження є теоретичне обґрунтування та практичне створення модуля, який демонструє користувачу результати обчислювального експерименту в сприятливому вигляді.
Об’єкт дослідження: інтегроване середовище курсу “Основи алгоритмізації та програмування” WebОАП.
Предмет дослідження: модуль обробки результатів обчислювального експерименту.
Гіпотеза дослідження полягає у припущенні, що організація обчислювального експерименту сприятиме пошуку оптимального розв’язання задач пошуку та сортування.
Згідно з метою та гіпотезою дослідження потребує вирішення таких завдань:
аналіз розробок, пов’язаних з ефективністю в алгоритмах пошуку та сортування;
теоретичне обґрунтування проблеми оцінки складності алгоритмів;
створення модуля, який демонструє користувачу результати обчислювального експерименту;
внесення модулю організації обчислювального експерименту в інтегроване середовище WebОАП.
Практичне значення роботи полягає у можливості проаналізувати особливості певних алгоритмів та усвідомити закономірності їх поведінки на тих чи інших наборах даних, а також зробити висновок щодо ефективності методів сортувань на цих наборах за допомогою графічного представлення залежності між наступними атрибутами:
набір змінних;
кількість порівнянь;
кількість присвоювань;
час виконання алгоритму.
Структура роботи. Магістерське дослідження складається із вступу, трьох розділів, висновків, списку використаних джерел, модулю обробки результатів обчислювального експерименту інтегрованого середовища курсу “Основи алгоритмізації та програмування” WebОАП.
РОЗДІЛ 1
ОЦІНЮВАННЯ СКЛАДНОСТІ АЛГОРИТМІВ
Визначення вимог алгоритмів
Велика кількість актуальних завдань досліджень та проектування вимагають для свого рішення можливості попереднього оцінювання складності алгоритмів і обчислень, а також реалізації програм. Поняття складності зумовлено безпосередньо з розробкою та реалізацією конкретних алгоритмів і програм. Труднощі вирішення проблем складності визначаються неоднозначністю методів розробки конкретних програм і різноманітністю алгоритмічних мов, технологій програмування, а також значним впливом суб’єктивних факторів. Постановка і розв’язання нової задачі доцільні, якщо за їхньою допомогою покращуються результати деякого процесу, чи процес реалізується за незначних витрат ресурсів. Очікуваний у цьому випадку виграш вдається звичайно оцінити за наявністю прогнозу змінюваних параметрів процесу, що розглядається.
Інтерес до проблеми оцінки складності алгоритмів виник після появи перших ЕОМ у середині минулого століття. Тому основні публікації з цієї проблеми з’явилися в 60-х, 70-х роках. ЕОМ були реальним конструктивним способом реалізації алгоритмів, що потребував складних обчислень, але параметри перших ЕОМ виявилися досить скромними, тому проблема складності реалізації алгоритмів вирішувалася з позиції оцінки можливостей використання алгоритмів і визначення відповідних вимог до ЕОМ, у першу чергу за обсягом оперативної пам’яті та швидкодії. Швидкий прогрес у сфері вдосконалення параметрів ЕОМ вже у 80-ті роки минулого століття зняв обмеження з продуктивності ЕОМ, тому інтерес до оцінки складності втратив актуальність. Проте на початку XXI століття досягнення в галузі розвитку сучасних інформаційних технологій настільки розширили масштаби застосування ЕОМ, що число машинних алгоритмів, впроваджуваних на практиці, почало невпинно зростати. У зв’язку з цим проблему оцінки складності алгоритмів пов’язують із пошуком найбільш ефективної їх реалізації. Вирішення цих задач також потребує оцінки складності алгоритмів, що знов зумовлює актуальність проблеми.
Алгоритм розв’язання масової задачі описує розв’язання будь-якого її екземпляра. Екземпляри багатьох задач можна охарактеризувати значенням деякого числового параметра. Наприклад, довжиною масиву чи кількістю чисел, які треба прочитати з клавіатури. Або натуральним числом, про яке ми хочемо дізнатися, чи просте воно. Найчастіше цим параметром є кількість скалярних значень, обробка яких задається алгоритмом. Кажуть, що екземпляр задачі має розмір N, якщо задається даними, складеними з N скалярних значень (наприклад, масивом із N елементів).
Нехай позначає алгоритм розв’язання деякої масової задачі. Позначимо через кількість елементарних дій у процесі розв’язання цього екземпляра задачі за алгоритмом , а через - максимум кількості елементарних дій серед усіх екземплярів розміру n.
Наприклад, якщо при сортуванні обміном масив спочатку відсортований навпаки, то слідом за кожним порівнянням відбувається обмін. А це ще три присвоювання. Якщо нехтувати допоміжними операціями із змінами індексів, то .
Кожному відповідає певне значення , тобто ми маємо функціональну залежність між розмірами та максимальними кількостями елементарних дій, які виконуються за алгоритмом . Ця функція називається складністю алгоритму . Алгоритми практично всіх реальних задач мають складність, монотонно неспадну за .
Аналітичне задання функції для реальних алгоритмів, як правило, неможливе й непотрібне. Велике практичне значення має так званий порядок зростання за . Він задається за допомогою іншої функції з простим аналітичним виразом, яка є оцінкою для .
Функція є оцінкою для функції , або є функцією порядку , коли існують такі додатні скінченні числа і , що за деякого при всіх
.
Така залежність між функціями позначається за допомогою знака .
Для оцінки складності переважної більшості реальних алгоритмів достатньо логарифмічної, степеневої та показникової функцій, а також їх сум, добутків та підстановок. Усі вони монотонно зростають і задаються простими аналітичними виразами.
Приклад 1. , оскільки за маємо
Аналогічно неважко довести, що , .
Приклад 2. Ефективність алгоритму бульбашкового сортування , алгоритму лінійного пошуку , бінарного пошуку .
Тепер означимо поняття складності задачі. Алгоритми пошуку в упорядкованому масиві свідчать, що одна й та сама задача може мати алгоритми розв’язання з різною складністю. Неформально, під складністю задачі розуміють найменшу зі складностей алгоритмів її розв’язання. Іншими словами, задача має складність порядку , якщо існує алгоритм її розв’язання зі складністю і не існує алгоритмів зі складністю .
Наприклад, складність задачі пошуку в упорядкованому масиві визначається складністю алгоритму двійкового пошуку, тому й оцінюється функцією . Задача сортування масиву має складність порядку .
1.2. Оцінка програм (оцінка алгоритму сортування)
На сьогодні існує багато алгоритмів сортування даних. Вони містять операції порівняння та обміну. Від їх кількості на наборі даних визначається складність алгоритму, тобто його ефективність.
Для більшості проблем існує багато різних алгоритмів. Який з них обрати для розв’язання конкретної задачі? Це питання дуже ретельно опрацьовується в програмуванні.
Ефективність програми (коду) є дуже важливою її характеристикою. Користувач завжди вважає за краще більш ефективне рішення навіть в тих випадках, коли ефективність не є вирішальним фактором.
Ефективність програми має дві складові: пам'ять (або простір) і час. Просторова ефективність вимірюється кількістю пам’яті, яка необхідна для виконання програми.
Комп’ютери володіють обмеженим об’ємом пам’яті. Якщо дві програми реалізують ідентичні функції, то та, яка використовує менший об’єм пам’яті, характеризується більшою просторовою ефективністю. Іноді пам'ять стає домінуючим фактором при оцінці ефективності програм. Проте в останні роки у зв’язку з швидким її здешевленням, ця складова ефективності поступово втрачає своє значення. Тимчасова ефективність програми визначається часом, необхідним для її виконання. Кращий спосіб порівняння ефективності алгоритмів полягає в зіставленні їх порядків складності. Цей метод застосовний як до тимчасової, так і до просторової складності. Порядок складності алгоритму виражає його ефективність зазвичай через кількість даних, що обробляються. Наприклад, деякий алгоритм може істотно залежати від розміру оброблюваного масиву. Якщо, скажімо, час обробки подвоюється з подвоєнням розміру масиву, то порядок тимчасової складності алгоритму визначається як розмір масиву. Порядок алгоритму – це функція, яка домінує над точним вираженням тимчасовій складності.
Функція має порядок , якщо є константа і лічильник , такі що , для .
O-функції виражають відносну швидкість алгоритму залежно від деякої змінної (або змінних).
Існують три важливих правила для визначення складності алгоритму.
або .
дорівнює домінанті і
Тут позначає константу, а і – функції.
Перше правило декларує, що постійні множники не мають значення для визначення порядку складності.
З другого правила виходить, що порядок складності при множенні двох функцій дорівнює помноженню їх складностей.
З третього правила виходить, що порядок складності суми функцій визначається як порядок домінанти першого і другого доданків, тобто вибирається найбільший порядок.
1.3. О-складність алгоритмів та їх аналіз
Складність обчислювальних процесів – це поняття теорії складності обчислень, оцінка ресурсів (зазвичай часу) необхідних для виконання алгоритму.
Розглянемо існуючі складності алгоритмів.
. Більшість операцій в програмі виконуються тільки раз або лише декілька разів, тобто алгоритмами константної складності. Будь-який алгоритм, що завжди вимагає незалежно від розміру даних одного і того ж часу, має константну складність.
. Час роботи програми лінійний, зазвичай, коли кожен елемент вхідних даних потрібно обробити лише лінійне число разів.
, , . Поліноміальна складність. – квадратична складність, – кубічна складність.
. Коли час роботи програми логарифмічний, програма починає працювати набагато повільніше зі збільшенням N. Такий час роботи зустрічається зазвичай в програмах, які ділять велику проблему на маленькі і вирішують їх окремо.
. Такий час роботи мають ті алгоритми, які ділять велику проблему на маленькі, а потім, вирішивши їх, сполучають їх рішення.
. Експоненціальна складність. Такі алгоритми найчастіше виникають в результаті підходу іменованого як «метод грубої сили». Якщо розмірність задачі зростає лінійно, час її розв’язання зростає експоненціально.
Програміст повинен уміти проводити аналіз алгоритмів і визначати їх складність. Тимчасова складність алгоритму може бути порахована виходячи з аналізу його управляючих структур (табл.1.1.). Загальна складність обчислюється за рахунок складання усіх управляючих структур.
Таблиця 1.1. – Аналіз структур та їх складність
Вид управляючої структури
Складність
Присвоювання
Простий вираз
S1;
S2;
Домінанта для та
If <умова> then
S1
else
S2;
Домінанта для
і і
For i := 1 to N do
S1
End.
У таблиці , і позначають відповідно складність обчислення S1, S2 і обчислення для умови.
Алгоритми без циклів і рекурсивних викликів мають константну складність. Якщо немає рекурсії і циклів, усі структури, що управляють, можуть бути зведені до структур константної складності. Отже, і увесь алгоритм також характеризується константною складністю.
Визначення складності алгоритму в основному зводиться до аналізу циклів і рекурсивних викликів.
Наприклад, розглянемо деякий алгоритм обробки елементів масиву.
For i := 1 to N do
Begin
…
End;
Складність цього алгоритму , оскільки тіло циклу виконується разів, і складність тіла циклу дорівнює .
Якщо один цикл вкладений в інший і обидва цикли залежать від розміру однієї і тієї ж змінної, то уся конструкція характеризується квадратичною складністю. Наступний алгоритм описує саме цю ситуацію.
For i := 1 to N do
For j := 1 to N do
Begin
…
End;
Складність цієї програми , оскільки тіло зовнішнього циклу виконується разів і тіло внутрішнього циклу також виконується разів, і складність тіла внутрішнього циклу дорівнює .
Також можна оцінити складність програми "Трійки Піфагора".
Існують два способи аналізу складності алгоритму : висхідний (від внутрішніх керуючих структур до зовнішніх) і низхідний (від зовнішніх до внутрішніх). Керуючі структури позначимо літерами , , , , .
Writeln('Ведіть обмеження'); Readln(N);
small:=1;
While small < N do
begin
next:=small;
While next <=N do
begin
last:=next;
While last <=N do
begin
if (last <= small*2) and (next <= small*2) and
(last*last = small*small+next*next) then
begin
writeln(small); writeln(next); writeln(last);
end;
inc(last);
end;
inc(next);
end;
inc(small);
end;
Тепер коли всі керуючі структури позначені, можна починати визначати складність алгоритму:
;
;
;
;
Складність цього алгоритму .
Як правило, близько 90% часу роботи програми вимагає виконання повторень і тільки 10% складають безпосередньо обчислення. Аналіз складності програм показує, на які фрагменти випадають ці 90% – це цикли найбільшої глибини вкладеності. Повторення можуть бути організовані у вигляді вкладених циклів або вкладеної рекурсії.
Ця інформація може використовуватися програмістом для побудови більш ефективної програми таким чином. Передусім можна спробувати скоротити глибину вкладеності повторень. Потім слід розглянути можливість скорочення кількості операторів в циклах з найбільшою глибиною вкладеності. Якщо 90% часу виконання складає виконання внутрішніх циклів, то 30%-е скорочення цих невеликих секцій призводить до 90%*30%=27%-му зниженню часу виконання усієї програми.
Аналізом ефективності алгоритмів займається окремий розділ математики і знайти найбільш оптимальну функцію буває не так вже й просто.
Оцінимо алгоритм бінарного пошуку в масиві – дихотомію.
Суть алгоритму: йдемо до середини масиву і шукаємо відповідність ключа значенню серединного елементу. Якщо нам не вдається знайти відповідності, ми дивимося на відносний розмір ключа і значення серединного елементу і потім переміщуємося в нижню або верхню половину списку. У цій половині знову шукаємо середину і знову порівнюємо з ключем. Якщо не виходить, знову ділимо на половину поточний інтервал.
Function search( low, high, key: integer ): integer;
var mid, data: integer;
begin
while low <= high do
begin
mid := ( low + high ) div 2;
data := a[mid];
if key = data then search := mid
else if key < data then high := mid – 1
else low := mid + 1;
end;
search := -1;
end;
Рішення:
Перша ітерація циклу має справу з усім списком. Кожна подальша ітерація ділить навпіл розмір підсписку. Так, розмірами списку для алгоритму є
Врешті-решт буде таке ціле , що або
Оскільки – це перше ціле, для якого , то повинен бути вірно або
З цього виходить, що
Візьмемо логарифм кожної частини нерівності і отримаємо
Значення – це найбільше ціле, яке .
Отже, .
Зазвичай задача, що розв’язується, має природний "розмір", який ми називаємо . Зрештою нам би хотілося отримати вираження для часу, необхідного програмі для обробки даних розміру , як функцію від . Зазвичай нас цікавить середній випадок – очікуваний час роботи програми на "типових" вхідних даних, і гірший випадок – очікуваний час роботи програми на найгірших вхідних даних. Кращий випадок цікавий тоді коли проводиться експеримент з метою дослідити будь-який алгоритм сортування і виявити найменший витрачений час.
Деякі алгоритми добре вивчені в тому сенсі, що відомі точні математичні формули для середнього і гіршого випадків. Такі формули розробляються за допомогою ретельного вивчення програм з метою знаходження часу роботи в термінах математичних характеристик, і потім роблячи їх математичний аналіз.
Декілька важливих причин такого роду аналізу:
1. Програми, які написані на мові високого рівня, транслюються в машинні коди, і зрозуміти скільки часу знадобиться для виконання того або іншого оператора може бути важко.
2. Багато програм дуже чутливі до вхідних даних, і їх ефективність може дуже сильно від них залежати. Середній випадок може виявитися математичною фікцією не пов'язаною з тими даними на яких програма використовується, а гірший випадок маловірогідний.
Кращий, середній і гірший випадки дуже великий вплив несуть в сортуванні (табл.1.2.).
Таблиця 1.2. – Об'єм обчислень при сортуванні
В кращому випадку
В середньому випадку
В гіршому випадку
Бульбашкою
Вибором
Швидке
O-аналіз складності отримав широке поширення у багатьох практичних застосуваннях. Проте необхідно чітко розуміти його обмеженість.
До основних недоліків підходу можна віднести наступні:
1) для складних алгоритмів отримання O-оцінок, як правило, або дуже трудомістко, або практично неможливо;
2) часто важко визначити складність "в середньому";
3) O-оцінки занадто грубі для відображення тонших відмінностей алгоритмів;
4) O-аналіз дає занадто мало інформації (чи зовсім її не дає) для аналізу поведінки алгоритмів при обробці невеликих об'ємів даних.
Розгляд складності в O-визначеннях – далеко нетривіальне завдання. Зокрема, ефективність двійкового пошуку визначається не глибиною вкладеності циклів, а способом вибору кожної чергової спроби.
Ще одна складність – визначення "середнього випадку". Зазвичай зробити це досить важко через неможливість оцінювання умов роботи алгоритму. Іноді алгоритм використовується як фрагмент великої, складної програми. Іноді ефективність роботи апаратури і/або операційної системи, або деякої компоненти компілятора істотно впливає на складність алгоритму. Часто один і той же алгоритм може використовуватися в безліч різних застосувань.
Через труднощі, пов'язані з проведенням аналізу тимчасової складності алгоритму "в середньому", часто доводиться задовольнятися оцінками для гіршого і кращого випадків. Ці оцінки по суті визначають нижню і верхню межі складності "в середньому". Власне, якщо не вдається провести аналіз складності алгоритму "в середньому", залишається наслідувати один із законів Мерфі, згідно яким оцінка, отримана для найгіршого випадку, може служити хорошою апроксимацією складності "в середньому".
Основним недоліком O-функцій є їх достатньо велика грубість. Якщо алгоритм виконує деяке завдання за с, тоді як для її ж вирішення за допомогою алгоритму потрібно с, то в мільйон разів швидше, ніж . Проте і мають одну і ту ж тимчасову складність .
Алгоритми сортування оцінюються за швидкістю виконання та ефективністю використання пам’яті.
Час – основний параметр, який характеризує швидкодію алгоритму. Називається також обчислювальною складністю. Для впорядковування важливі гірша, середня та краща поведінки алгоритму при вхідній множині . Якщо на вхід алгоритму подається множина , то позначимо . Для алгоритму хороша поведінка – це і погана – це . Ідеальна поведінка для впорядковування . Алгоритми сортування, які використовують тільки абстрактну операцію порівняння ключів завжди потребують хоча б порівнянь.
Пам'ять – алгоритми потребують виділення додаткової пам’яті для тимчасового зберігання даних. Як правило, ці алгоритми потребують пам’яті. При оцінюванні не враховується місце, яке займає даний масив і незалежні від вхідної послідовності затрати, наприклад, на зберігання коду програми (так як все це потребує ). Алгоритми сортування, які не потребують додаткової пам’яті, відносять до сортувань «на місці», тобто до сортувань, в яких не використовується копіювання масиву.
Висновки до розділу 1
Інтерес до проблеми оцінки складності алгоритмів виник вже після появи перших ЕОМ. Досягнення в галузі розвитку сучасних інформаційних технологій розширили масштаби застосування ЕОМ і число машинних алгоритмів почало невпинно зростати. З’явилась потреба у найбільш ефективній їх реалізації.
У розділі аналізуються підходи до оцінки складності алгоритмів. Оскільки ефективність програми є дуже важливою її характеристикою, користувач завжди вважає за краще більш ефективне рішення навіть в тих випадках, коли ефективність не є вирішальним фактором. Ми зазначаємо, що програміст повинен уміти проводити аналіз алгоритмів і визначати їх складність. У своєму дослідженні ми наводимо варіанти такого аналізу.
РОЗДІЛ 2
АЛГОРИТМИ СОРТУВАННЯ
2.1. Прості алгоритми сортування
Сортування – це процес перестановки об’єктів даної множини в певному порядку. Мета сортування – полегшити наступний пошук елементів у відсортованої множині.
Алгоритм сортування – це алгоритм, який призначений для впорядкування елементів у списку або у масиві. У випадку, коли елемент списку має декілька полів, поле, що служить критерієм порядку, називається ключем сортування.
Прості алгоритми сортування, усім відомі як сортування обміном, вставками та вибором можуть мати складність в гіршому випадку . Більш ефективні алгоритми, наприклад, пірамідальне сортування мають складність . Існують ситуації, коли прості алгоритми випереджають складні по ефективності, наприклад, сортування вставками на невеликих наборах може бути найкращим. Такі випадки можуть самі стати об’єктами досліджень.
Критеріями оцінки методів сортування є:
кількість операцій порівняння пар ключів;
кількість перестановок елементів;
економне використання пам’яті.
За допомогою програмного середовища можна розв’язувати різні задачі, у тому числі автоматично здійснювати потрібне сортування даних. Сортування може знадобитися в різних випадках, наприклад, коли потрібно відобразити візуально розподіл даних. Для тих чи інших даних існують певні методи сортувань, які покращують продуктивність та швидкість сортування саме для цього типу даних.
Слід відзначити, що хоча складні алгоритми потребують меншої кількості операцій, ці операції є більш складними. Тому при відносно малій кількості елементів що сортуються, прості методи сортування працюють достатньо швидко.
Задачі сортування послідовностей є дуже відомими і поширеними. В загальному вигляді вони формулюються так:
Дана послідовність довжини заданого типу, на якому існують операції >, <, >=, <=. Необхідно відсортувати послідовність, тобто переставити її елементи таким чином, щоб для кожного виконувалось відношення , де , а є однією з зазначених операцій.
Розглянемо алгоритми сортування, в яких не використовується копіювання масиву, тобто сортування «на місці». Іншими словами сортуванню не потрібна допоміжна пам'ять, ми сортуємо елементи масиву, використовуючи тільки пам'ять, яку займає сам масив. Зручною мірою ефективності таких алгоритмів сортування є число необхідних порівнянь в процесі сортування та число необхідних пересилань елементів.
Ефективні алгоритми сортування потребують порядку порівнянь, де – кількість елементів, а – кількість необхідних порівнянь.
Розглянемо деякі прості методи сортування, які потребують кількість порівнянь порядку .
Методи сортування без копіювання масиву можна поділити на три основних класи:
сортування вибором;
сортування вставками;
сортування обміном.
Сортування вибором
При сортуванні вибором обирається елемент з найбільшим значенням ключа і обмінюється положеннями з останнім. Потім те ж саме повторюється для елементу. Знайдений елемент з найбільшим значенням ключа обмінюється положеннями з передостаннім елементом і т.д. (рис.2.1.). Метод називається сортуванням вибором, оскільки він працює за принципом вибору найбільшого елемента з числа невпорядкованих.
Рис.2.1. Схематичне зображення сортування простим вибором
Наведемо код реалізації сортування простим вибором.
#include "stdafx.h"
#include <iostream>
#include <conio.h>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int n, i, j, temp;
cout<<"please insert size of array ";
cin>>n;
int a[100];
for (i = 0; i < n; i++)
{
cout<<"please insert "<<i<<" element ";
cin>>a[i];
}
for (i = 0; i < n; i++)
{
for( j = n - 1; j >= i; j--)
if (a[j-1] > a[j])
{
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
for (i = 0; i < n; i++)
{
cout<<a[i]<<" ";
}
getch();
return 0;
}
Приклад роботи алгоритму сортування вибором.
Масив (4 1 5 2 3) з п’яти елементів ().
Перший етап:
Максимальний елемент «5» обмінюється місцями з елементом «3», який знаходиться на позиції .
(4 1 5 2 3) (4 1 3 2 5)
Другий етап:
Максимальний елемент «4» обмінюється місцями з елементом «2», який знаходиться на позиції .
(4 1 3 2 5) (2 1 3 4 5)
Третій етап:
В даному випадку елемент «3» є максимальним і розташовується на позиції , тому фізично обмін відбувається, але масив не змінюється.
(2 1 3 4 5) (2 1 3 4 5)
Четвертий етап
Максимальний елемент «2» обмінюється місцями з елементом «1», який знаходиться на позиції .
(2 1 3 4 5) (1 2 3 4 5)
Сортування вибором не є складним в аналізі та порівнянні його з іншими алгоритмами, оскільки жоден з циклів не залежить від даних у списку. Знаходження найбільшого елементу вимагає перегляду усіх елементів (у даному випадку здійснюється порівняння), і після цього, перестановки його на останню позицію. Знаходження наступного елементу вимагає перегляду елементів ( порівняння), і так далі, для порівнянь. Алгоритм не використовує додаткової пам’яті. Існує також варіант сортування методом вибору, в якому на кожному етапі відшукуються й встановлюються на свої місця як мінімальний, так і максимальний елементи.
Сортування вставками
У сортуванні вставками елементи поділяються на вже впорядковану та невпорядковану послідовності. Спочатку впорядкована частина містить тільки один елемент. Наступний елемент, що розташовується на початку невпорядкованої частини, вставляється на підходяще місце впорядкованої частини. При цьому впорядкована частина подовжується на один елемент, а невпорядкована – зменшується. Сортування завершується коли зникає невпорядкована частина (рис.2.2).
Рис.2.2. Схематичне зображення сортування простими вставками
Наведемо код реалізації сортування простими вставками.
#include "stdafx.h"
#include <iostream>
#include <conio.h>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int n, i, j, temp;
cout<<"please insert size of array ";
cin>>n;
int a[100];
for (i = 0; i < n; i++)
{
cout<<"please insert "<<i<<" element ";
cin>>a[i];
}
for (i = 1; i < n; i++)
{
temp = a[i];
j = i - 1;
while (j >= 0 && a[j] > temp)
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = temp;
}
for (i = 0; i < n; i++)
{
cout<<a[i]<<" ";
}
getch();
return 0;
}
Приклад роботи алгоритму сортування вставками.
Масив (4 1 5 2 3) з п’яти елементів ().
Перший етап:
В даному випадку вважається, що елемент «4» є впорядкованою частиною масиву, відносно якого сортується невпорядкована частина, тобто частина, що починається з другого елементу.
(4 1 5 2 3) (1 4 5 2 3)
Другий етап:
На другому етапі впорядкована частина містить вже два елементи: «1» та «4», тому сортування починається з третього елементу.
(1 4 5 2 3) (1 4 5 2 3)
Третій етап:
Впорядкована частина складається з елементів «1», «4» та «5» На черзі четвертий елемент, який вставляється в впорядковану частину
(1 4 5 2 3) (1 2 4 5 3)
Четвертий етап:
Останній п’ятий елемент з невпорядкованої частини вставляється у впорядковану.
(1 2 4 5 3) (1 2 3 4 5)
Невпорядкована частина зникла, а тому алгоритм припиняє роботу.
Сортування вставками – простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям. Однак має цілу низку переваг:
ефективний за звичай на маленьких масивах, на наборах даних до десятків елементів може бути найкращим;
ефективний на наборах даних, які вже частково відсортовані;
це стійкий алгоритм сортування (не змінює порядок елементів, які вже відсортовані);
може сортувати список під час його отримання;
не потребує тимчасової пам’яті, навіть під стек;
є стабільним алгоритмом.
Сортування обміном
Основна характеристика сортування обміном – перестановка місцями двох сусідніх елементів, якщо вони розташовані не так, як потребує відсортований масив. Проходи по масиву повторюються до тих пір, доки на черговому проході не виявиться, що обміни більше не потрібні, що означатиме – масив відсортований. При проході алгоритму, елемент, що стоїть не на своєму місці, «спливає» до необхідної позиції як бульбашка, звідси і назва алгоритму (рис.2.3).
Рис.2
19.06.2013 12:06-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора