МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ХЕРСОНСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
Кафедра ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ
розробки програм для
Аналізу методів сортування одномірних масивів.
Курсовий проект по дисципліні В«ПрограмуванняВ»
Пояснювальна записка
Виконавець
студент групи 2КСС3 ________________________
(Підпис, дата)
Керівник
старший викладач ________________________
(Підпис, дата)
Нормоконтролер
старший преподаватель_________________________
(Підпис, дата)
РЕФЕРАТ
Курсовий проект містить: стор - 39 машинописного тексту, літературних джерел - 5, додатки - 2.
Ключові слова: ФУНКЦІЯ, ФАЙЛ, МЕТОД, МАСИВ.
У курсовому проекті розглянута модифікація і порівняння двох текстових файлів. Програма написана на мові програмування Сі та працездатна на IBM сумісних комп'ютерах. Програма має псевдографічний і графічний інтерфейси, володіє достатнім швидкодією і невеликим розміром.
ЗМІСТ
Введення .............................................. .................................................. .... 3
1. Постановка задачі ....................................... ......................................... 5
1.1. Аналіз існуючих рішень поставленої задачі ................ 5
1.2. Обгрунтування вибору методу розв'язання завдання ............................... 16
2. Розробка алгоритму розв'язання задачі ..................................... .......... 17
3. Розробка програми ................................................. ....................... 18
3.1 Опис програми і використовуваних в ній функцій ................... 18
3.1.1 Опис функції main () ............................................. .................. 21
3.1.2 Опис функції srecmg () ............................................. ............... 21
3.1.3 Опис функцій qqsort () ....................................... ...................... 22
3.1.4 Опис функції grafix () ............................................. ................. 23
3.2 Керівництво програміста ................................................ .............. 25
3.3 Керівництво оператора ................................................ .................... 26
28
Список використаної літератури ................................................ ........ 29
Додаток 1 ............................................. .............................................. 30
Додаток 2 ............................................. .............................................. 39
ВСТУП
Сі - це мова програмування загального призначення, добре відомий своєю ефективністю, економічністю, і переносимістю. Вказані переваги Сі забезпечують хорошу якість розробки майже будь-якого виду програмного продукту. Використання Сі в якості інструментального мови дозволяє одержувати достатньо швидкі і компактні програми. У багатьох випадках програми, написані на Сі, порівняні по швидкості з програмами, написаними на мові асемблера [2]. При цьому вони мають кращу наочність.
Сі поєднує ефективність і потужність в відносно малому за розміром мові. Хоча Сі не містить вбудованих компонент мови, виконують введення-виведення, розподіл пам'яті, маніпуляцій з екраном або управління процесами, тим не менш, системне оточення Сі має у своєму розпорядженні бібліотекою об'єктних модулів [3], в якій реалізовані подібні функції. Бібліотека [4] підтримує багато функцій, які вимагаються. [1]
Мова Сі - це універсальна мова програмування, для якого характерні економічність вирази, сучасний потік управління і структури даних, багатий набір операторів. Мова Сі не є ні мовою "Дуже високого рівня", ні "великим" мовою, і не призначається для деякої спеціальної області застосування, але відсутність обмежень і спільність мови роблять його більш зручним і ефективним для багатьох завдань, ніж мови, ймовірно більш потужні.
Він тісно пов'язаний з операційною системою "UNIX" [4], так як був розвинений на цій системі і так як "UNIX" та її програмне забезпечення написано на "C". Сам мову, однак, не пов'язаний з якою-небудь однією операційною системою або машиною, і хоча його називають мовою системного програмування, так як він зручний для написання операційних систем, він з рівним успіхом використовувався при написанні великих обчислювальних програм, програм для обробки текстів і баз даних [2].
2. ПОСТАНОВКА ЗАВДАННЯ
2.1 АНАЛІЗ ІСНУЮЧИХ вирішення поставлених завдань
В даний час існує безліч алгоритмів сортування [5] масивів, які застосовуються залежно від того які умови функціонування стоять перед разрабатимаемой програмою.
1. Методи вставки. Алгоритм простих вставок.
1.1. Бінарні вставки
1.2. Двоколійному вставки
1.3. Вставки одночасно декількох елементів.
1.4. Вставки з убуваючі кроком (метод Шелла)
1.5. Вставки в зв'язаний список
1.6. Вставки в кілька пов'язаних списків
2. Обмінна сортування
2.1. Метод бульбашки
2.2. Модифікація методу бульбашки
2.3. Швидке сортування.
2.4. Обмінна порозрядного сортування
2.5. Паралельна сортування Бетчера
3. Сортування за допомогою вибору
(Використання пов'язаного списку для зберігання
інформації про проміжні максимумах.)
4. Сортування за допомогою злиття
Методи вставки. Алгоритм простих вставок.
Нижче описаний основний алгоритм простих вставок, який породжує кілька модифікацій, що використовуються в завданнях. Алгоритм використовує прийом, яким користуються гравці в карти при сортування тільки що розданій колоди: чергова карта вставляється між вже впорядкованими раніше.
Опис алгоритму простих вставок. Файл, що підлягає сортуванню, в загальному випадку складається з елементів-записів, що включають інформаційну частину і ключі, за якими проводиться упорядкування за зростанням. Оскільки інформаційна частина майже не впливає на процес соріровкі, будемо припускати, що файли, використовувані в прикладах, состот тільки з елементів-ключів, а інформаційна частина записи від сутствует.
Час роботи алгоритму t приблизно оцінюється формулою:
t = a * NР… + b * N
де a, b - невідомі константи, що залежать від програмної реалізації алгоритму.
Бінарні вставки
Для прискорення числа порівнянь при пошуку місця, в яке потрібно вставити елемент X, можна використовувати логарифмічний [5] пошук. Це означає, що спочатку Х порівнюється з елементом k [j/2], потім, в залежності від результату порівняння, з елементом, лежачим посередині між 1 і j/2 або посередині між j/2 +1 і j і т.д. . При цьому чіслосравненій для кожного j дорівнює приблизно log (j). Число пересилок еле ментів при цьому не змінюється і залишається приблизно рівним NР…/4.
Час роботи алгоритму t приблизно оцінюється формулою:
t = a * NР… + b * N + c * N * logN
де a, b, c - невідомі константи, залежні від програмної реалізації алгоритму.
двоколійному вставки
Число пересилок можна скоротити приблизно в 2 рази до NР…/8, якщо допустити зрушення елементів не тільки вправо, але і вліво. Для вихідного файлу резервується місце в пам'яті, рівне 2N +1, де N - число елементів у вихідному файлі. Перший елемент пересилається в середину вихідного файлу. Надалі елементи вихідного файлу зсуваються вправо або вліво в залежності від того, в яку сторону потрібно зрушувати менше елементів. Приєднання нових елементів до вихідного файлу відбувається як справа, так і...
