РЕФЕРАТ
СОРТИРОВКА, ПРЯМЕ ВКЛЮЧЕННЯ, ЧИСЛО порівняння, середня число порівнянь, ГРАФІК ЗАЛЕЖНОСТІ, МАКСИМАЛЬНЕ ЧИСЛО порівняння, мінімальний число порівнянь,
У цій роботі було розглянуто метод сортування прямим включенням (вставкою). Всі елементи умовно поділяються на готову послідовність a1 ... ai - 1 і вхідну ai ... an. Hа кожному кроці, починаючи з i=2 і збільшуючи i на 1, беремо i-елемент вхідної послідовності і вставляємо його на потрібне місце в готову.
Були проведені два експерименти з п'ятьма масивами різної довжини, в яких проводився пошук десяти різних ключів по десять разів на кожному масиві. Експерименти дозволили побачити роботу методу і розрахувати середнє, максимальне і мінімальну кількість порівнянь при проведенні пошуку.
Основними моментами проведеного дослідження були складання таблиць і графіків залежності порівнянь, що дало можливість зробити висновок про те, що результати великої кількості експериментів проведених практичним шляхом дозволяють підтверджувати результати проведені теоретичним шляхом.
ЗМІСТ
ВСТУП
. ЛІТЕРАТУРНИЙ ОГЛЯД ПО алгоритм сортування прямим включенням
1.1 Короткі теоретичні відомості про алгоритм пряме включення
.2 Вибір матеріалу для проведення теоретичного дослідження
2. ДОСЛІДЖЕННЯ алгоритм сортування МЕТОДОМ ПРЯМОГО ВКЛЮЧЕННЯ
2.1 Теоретичне дослідження алгоритму пряме включення
.2 Практичне дослідження алгоритму пряме включення
ВИСНОВОК
Список використаної літератури
ДОДАТОК E - Код програми № 1
ДОДАТОК F - Код програми № 2
ВСТУП
Метою курсової роботи є закріплення отриманих знань у другому семестрі, де мною були вивчені основні структури даних і алгоритми, які працюють з ними. Серед цих алгоритмів широко відомий метод пряме включення, який і буде досліджено в курсовій роботі. Дослідження будуть проведені теоретичними та практичними методами, на підставі яких будуть складені таблиці і графіки залежностей.
1. ЛІТЕРАТУРНИЙ ОГЛЯД ПО алгоритмів ПРЯМОГО ВКЛЮЧЕННЯ
1.1 Короткі теоретичні відомості про алгоритм пряме включення
В одній з книг [1, 442-444] розповідається про принцип роботи алгоритму бінарного пошуку в масиві. Ідея даного методу полягає в тому, що кожного разу, маючи вже впорядкований масив з K елементів, ми додаємо ще один елемент, включаючи його в масив таким чином, щоб впорядкованість не порушена. Сортування може проводитися одночасно з введенням масиву.
Для пошуку місця i-ro елемента кожен раз буде потрібно виконати від 1 до i - 1 операцій порівняння, тобто в середньому i / 2 операцій порівняння. Значення i змінюється від 2 до п, тобто виконується п - 1 прохід, в кожному з яких відбувається в середньому від 1 до п / 2 порівнянь. Таким чином, сумарно в середньому для виконання завдання потрібно виконати (nl) (n / 2 + 1) / 2=(n2 + п - 2) 1 А операцій порівняння. Звідки обчислювальна складність методу в середньому також дорівнює Вср (п2), хоча час виконання приблизно в два рази менше, ніж у попереднього методу. Цікаво, що в даному випадку обчислювальна складність залежить від вихідного розташування елемент...
