симальний серед перших i-1 елементів. p> Тоді після обміну елементів K [j] і K [m] пошук максимуму в наступному циклі по j можна здійснювати серед елементів K [L [m]] ... K [j] при началь-них значеннях X = K [L [m]], m = L [m], т.к. максимум може "оновитися" тільки за рахунок елементів, що лежать правіше локального максимуму. Таким чином середня кількість переглядаються при пошуку максимуму елементів со-скорочується приблизно в два рази.
Час роботи алгоритму t приблизно оцінюється формулою: t = a * NР… + b * N * logN
де a, b - невідомі константи, що залежать від програмної реалізації алгоритму.
Сортування допомогою злиття
Алгоритми сортування цього класу грунтуються на об'єднанні декількох (часто двох) вже упорядоченнх файлів. Розглянуті далі алгоритми вибирають з вихідного файлу впорядковані відрізки і об'єднують їх в більш довгі.
Природне двоколійному злиття
Цей алгоритм шукає впорядковані відрізки з двох кінців файлу іперепісивает їх по черзі також в обидва кінці. Повторюючи цю процедуру в циклі, ми приходимо до середини файлу, що означає закінчення сортування.
Елементи файлу пересилаються з однієї області до іншої, змінюючи напрямок пересилки. Для запам'ятовування напрямки пересилання служить мінлива s, приймаюча значення TRUE і FALSE поперемінно. Інший логічний ознака f служить сигналом продовження-закінчення алгоритму, якщо всі області злилися в кінці кінців в одну. Мінлива d приймає поперемінно значення +1 -1 і вказує напрям перегляду файлу: вперед або назад.Операція <-> позначає обмін значеннями двох змінних. Операція Я позначає інверсію логічної змінної або виразу. br/>
Час роботи алгоритму t приблизно оцінюється формулою:
t = a * N * lgN + b * N
де a, b - невідомі константи, що залежать від програмної реалізації алгоритму.
Просте двоколійному злиття.
В алгоритмі природного двоколійному злиття упорядкований відрізки файлу визначалися випадковим розташуванням елементів у вихідному файлі. У даному алгоритмі довжина відрізків фіксується на кожному кроці. У вихідній файлі всі відрізки мають довжину 1, після першого кроку вона дорівнює 2, після другого 4, після третього - 8, після к-го кроку -2 в ступені к.
Час роботи алгоритму t приблизно оцінюється формулою: t = a * N * lgN + b * N
де a, b - невідомі константи, залежать від програмної реалізації алгоритму.
1.2 ОБГРУНТУВАННЯ ВИБОРУ МЕТОДУ РІШЕННЯ ЗАВДАННЯ
Сортування масиву швидким методом є прекрасним прикладом целесооразності використання рекурсивного звернення до Програмування на мові Сі. Метод швидкого сортування був запропонований К. А. Р. Хоору в 1962р. Запропонована версія швидкої сортування, зрозуміло, не найшвидша серед усіх можливих, але зате вона з найпростіших. p> Основна стратегія прискорення алгоритмів сортування - обміни між якомога більш далекими елементами вихідного файлу - в методі швидкої сортування реалізована за рахунок того, що один з ключів у вихідному файлі використовується для розділення його на два подфайла так, щоб зліва від обраного елемента знаходилися тільки елементи з меншими ключами, а праворуч - тільки з великими.
Алгоритми сортування шляхом злиття грунтуються на об'єднанні декількох (часто двох) вже упорядоченнх файлів. Цей алгоритм шукає впорядковані відрізки з двох решт файлу і переписує їх по черзі також в обидва кінці. Повторюючи цю процедуру в циклі, ми приходимо до середини файлу, що означає закінчення сортування.
3. РОЗРОБКА АЛГОРИТМУ РІШЕННЯ ЗАВДАННЯ
В
Алгоритм розв'язання задачі гранично простий. Функція main () явлвется функцією меню і виконує опитування клавіатури . Залежно від натиснутої клавіші виконує відповідні дії програми. Для читання інформації про програму з файлу text.hlp використовується функція help (), яка працює з файловим висновком. Функція file () основна оскільки з її допомогою виконується сортування масиву (виклик функцій qqsort () і srecmg ()) визначення часу сортування виклик функції побудова гістограм. Масив складається з випадкових чисел вводяться в нього функцією генератора випадкових чисел. Далі функція file () викликає відповідні функції сортування, засікає час сортування відповідним способом, і заносить цей час в масив simvol []. Далі дані з масиву передаються у функцію grafix (), де вони використовуються при виведенні на екран гістограм в графічному режимі. Програма передбачає випадки відсутності деяких програмних елементів. У цьому випадку викликається функція Error (), яка створює вікно повідомлення в яке вписуються характеристика помилки. Так програма не буде виконуватися якщо не знайдений файл "text.hlp" або драйвер EGAVGA.BGI
.
3. РОЗРОБКА ПРОГРАМИ
В
3.1 ОПИС ПРОГРАМИ
В
Дана програма називається "TEST" (Ім'я виконуваного файлу test.exe) і призначена для аналі...
