Найпростіше сортування вставками відноситься до найбільш очевидних
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
 |
КАФЕДРА ПРОГРАМУВАННЯ
Методичні вказівки та завдання до лабораторних робіт
Для студентів напряму «Комп’ютерна інженерія» з дисципліни
„АЛГОРИТМИ І МЕТОДИ ОБЧИСЛЕНЬ”
спеціальністі:
7.091501 «Комп'ютерні системи та мережі»
Спеціалізовані комп'ютерні системи»
Одеса 2009
Методичні вказівки розроблені та підготовлені до друку:
Доцентом Нікітіним Д.М., ст. викладачем Антоновой А.Р.
Методичні вказівки розглянуті
на засіданні кафедри програмування
протокол № 5 від 28 січня 2009 року
Зав. кафедрою Косой Б.В.
і затверджені методичною комісією
Факультету інформаційних технологій
протокол № від 2009 року
Голова метод. комісії Корнієнко Ю.К.
Вступ
Дисципліна “Алгоритми і методи обчислень” входить до переліку обов’язкових дисциплін циклу професійно орієнтованих дисциплін освітньо-професійної програми вищої освіти за професійним спрямування 0915 “Комп’ютерна інженерія”. Необхідними передумовами для вивчення дисципліни “Алгоритми і методи обчислень" є засвоєння студентами матеріалу дисциплін "Вища математика", “Основи програмування та алгоритмічні мові”, “Об’єктно-орієнтовано програмування”, “Основи дискретної математики”, “Теорія ймовірностей, імовірнісні процеси і математична статистика” та “ Чисельні методи в інформатиці”.
|
|
|
Вивчення дисципліни сприяє формуванню наукового рівня інженерного мислення майбутнього фахівця, містить в собі теоретичну базу, яка необхідна при вирішенні прикладних питань оптимізації в конкретних задачах дослідження інформаційних комп'ютерних систем в техніці та економіці. Основу дисципліни складає засвоювання методів дослідження операцій та реалізація відповідних алгоритмів з використанням комп'ютерної техніки. Особлива увага надається методам вирішення задач лінійного та дискретного програмування в їх практичній інтерпретації.
Мета курсу:
- ознайомити студентів з класичною теорією алгоритмів;
- надати знання з основ аналітичної теорії алгоритмів і теорії складності;
- сформувати навички в побудові алгоритмів і аналізі їх ефективності.
“Елементи сучасної технології розробки алгоритмів”
Структурний підхід до розробки алгоритмів засновується на наступних принципах:
- використання для запису алгоритмів тільки базових структур: проходження, розвилка, повторення;
- кожен алгоритм (або його функція) повинен розроблятися, як простий:
· містить єдиний вхід,
|
|
|
· не вміщає другорядних фрагментів,
· не містить нескінченних циклів,
· має єдиний вихід.
Реалізація принципів структурного програмування дозволяє впорядкувати алгоритми і позитивно впливає на етапи тестування і супроводження програм. Тестування – це процес виконування програми з метою виявлення помилок, тобто перевірка наявності помилок у його роботі. Далеко не завжди вдається після виконаного тестування вказати точне місце помилки в алгоритмі. Як правило, для цього необхідно провести додатковий аналіз алгоритму. Цей процес називається налагодженням алгоритму. Таким чином, структурний підхід до розробки алгоритму означує виконання трьох основних етапів: успадкована розробка алгоритму, тестування і налагодження розробленого алгоритму.
Розробка алгоритму програми починається з виділення її основних функцій, а потім другорядних, призначених для забезпечення основних. Кожна із цих функцій може бути представлена в програмі окремим структурним елементом, який зветься модулем. Модуль - це послідовність логічно пов'язаних фрагментів, оформлених у виді окремої частини програми. Опрацювання програми у вигляді сукупності модулів зветься принципом модульного програмування, який характеризується наступними перевагами:
|
|
|
· Велика програма, яка поділена на модулі, може розроблятися паралельно декількома програмістами (по модулях).
· Більшість функцій, що використовуються, можуть бути стандартизованими й розміщеними в бібліотеці.
· У випадках перевищення програмою реальних розмірів оперативної пам'яті можливе завантаження програми у пам'ять ЕОМ вроздріб (оверлейні програми).
· Полегшується повне тестування.
· Спрощується супровід програми.
· З'являється можливість контролю за ходом виконання проекту по контрольних точках, якими можуть служити окремі модулі.
Таким чином, модульне програмування створює умови для керування процесом розробки великих програм, маневрування людськими ресурсами, підвищення якості завершених програм, накопичення в бібліотеках досвіду розробки програм у вигляді стандартних функцій обробки даних.
В програмуванні часто виникає задача перерозташування елементів різних множин (сортування), як приклад, - у порядку збільшення або зменшення. Розглянемо декілька методів внутрішнього сортування, коли число елементів, що підлягають сортуванню, достатньо мало, так що весь процес можливо здійснити в оперативній пам'яті ЕОМ (звідси і назва - внутрішнє сортування ):
|
|
|
· Сортування вставками. Елементи розглядаються по одному, і кожен новий елемент вводиться в відповідне місце серед раніше перевірених.
· Обмінне сортування. Якщо два елементи невпорядковані, то вони міняються місцями. Цей процес повторюється до тих пір, поки елементи не будуть впорядковані.
· Сортування за допомогою вибору. Спочатку виділяється найменший (або найбільший) елемент і яким-небудь чином відокремлюється від інших, потім обирається найменший (або найбільший) елемент з тих, що лишилися, і т.д.
· Сортування підрахунком. Кожен елемент порівнюється з усіма іншими: остаточне положення елемента визначається шляхом підрахунку числа менших ключів.
Алгоритми сортування базуються на одному з наступних підходів:
- вибірка;
- обмін;
- включення (вставки);
- розподіл - елементи розподіляються по підмножинах таким чином, щоб всі молодші елементи потрапили в одну підмножину, всі старші - в другу, а посередні елементи опинилися в проміжній підмножині.
- Злиття - відсортовані підмножини поєднуються в більші сортовані підмножини методом злиття.
Швидкість алгоритму залежить від багатьох факторів. При цьому, на звичай, враховують число порівнянь. Найпростіші алгоритми вимагають порядку N2 порівнянь, а кращі - використають N log2 N порівнянь. Існує кулька десятків різних методів сортувань. Кожен метод має свої переваги й недоліки, тому той самий метод може бути ефективним для одних даних і непридатним для інших.
Сортування вставками
Найпростіше сортування вставками відноситься до найбільш очевидних.
Блок-схема алгоритму: Фрагмент програми:
 |
Program new;
Uses forms;
const n=20;
var a : array [1..n] of integer;
k : integer;
i, n, j : byte;
begin
{ введення елементів масиву А }
…………………………………..
for j : = 2 to n do
begin
i : = j-1;
k : = a[j] ;
while (i>0) and (k <= a[i]) do
begin
a[i+1] : = a[i];
i : = i –1;
end;
a[i+1] : = k;
end;
{ друк упорядкованого масиву А}
…………………………………………
end.
Масив ai , (i = 1, n) розміщається на тім же місці, після сортування впорядковуються по зростанню. Порівнюємо поточний елемент aj з aj-1 , aj-2 ... доки не виявимо місце між ai і ai+1 , куди потрібно вставити елемент aj. Тоді елементи ai+1 ... aj-1 просунемо на одне місце вперед (вверх) і помістимо новий елемент aj на ai+1 місце. Зручно поєднувати операції порівняння і переміщення, тому що елемент aj як би «проникає» на відведений йому рівень. Такий спосіб часто називають просіванням або зануренням.
Дата добавления: 2018-04-04; просмотров: 402; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!