Міністерство Освіти і Науки України
Національний Аерокосмічний Університет ім. М. Є. Жуковського "ХАІ"
Кафедра 302
Домашнє завдання з курсу
"Програмування та алгоритмічні мови" на тему:
"Сортування масиву методом вставок"
Виконав: студент 326 групи
Чаплигін В. І.
Перевірив:
Момот М. А.
Харків
2003
Зміст
1. Постановка завдання ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 3
2. Теоретичне обгрунтування та алгоритм розв'язання задачі ... ... ... ... ... ... ... ... 3
3. Приклад роботи програми ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 4
4. Вихідний код програми з коментарями ... ... ... ... ... ... ... ... ... ... ... ... .... 9
5. Список літератури ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 13
6. Додаток 1: блок-схема програми ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 14
7. Додаток 2: блок-схема функції сортування (SortByIncrease ()) ... ... ... 15
Постановка завдання
Завдання:
Упорядкувати масив x за зменшенням або зростанням (тобто переставити йогоелементи так щоб для всіх k виконувалося xk = xk-1відповідно), використовуючи такий алгоритм сортування (впорядкування): сортування вставками: нехай перший k елементів масиву вже впорядкованіпо не зменшенню; береться (k +1)-й елемент і розміщується серед перших kелементів так, щоб впорядкованими виявилися вже k +1 перших елементів;цей метод застосовується при k від 1 до n-1.
Основні вимоги до програми:
. У програмі повинні використовуватися функції, для яких випливає явно зіставити прототипи (оголошення, описи), визначення та виклики.
. Як мінімум в одній функції мають бути параметри за замовчуванням і відповідно в програмі повинні бути виклики такої функції в різній формі.
. Використовувати всі цикли З ++.
. Доступ до елементів масиву по [] та *.
. Заповнення масиву випадковим чином.
. Програма повинна створюватися з проекту, що містить кілька файлів вихідного коду (*. h, *. срр).
. Повинні використовуватися умовного компіляція (варти включення).
. Програма повинна мати дружній інтерфейс - основні операції повинні викликатися через відповідні елементи текстового меню.
. Ітерації в текстовий файл звіту.
. Передача імені файлу звіту у командному рядку.
. Зчитування вихідних даних з файлу.
. Використання параметрів командного дані для.
Теоретичне обгрунтування методу
«Сортування за допомогою прямого включення» та алгоритм розв'язання задачі
Метод грунтується на наступному: вважається, що перед розглядом запису
R [j] попередні записи R [1], R [2 ],..., R [j-1] вже впорядковані, і R [j]вставляється у відповідне місце. Сортування таблиці починається зідругого запису. Її ключ порівнюється з ключем першого запису, і, якщовпорядкованість порушена, то записи R [1] і R [2] переставляються. Потім ключзапису R [3] порівнюється з ключами записів R [2] і R [1]. Як тількипрограма виявляє, що (j +1)-й елемент масиву менше (при сортуванніза зростанням) j-го елемента, вона копіює значення цього елемента вбуферну змінну і з початку масиву до j аналізує, поки значеннябуферної змінної не буде менше будь-якого елемента х. Потім шматокмасиву, починаючи з х і до j, переміщується на одну клітинку в бікзростання, і на що утворилося місце х записується значенняпереміщуваного елементу. Далі продовжується переміщення за основниммасиву до елемента n-1 (тому що ми порівнюємо j-й і (j +1)-й елементи):
41 54 10 66 27 42 80 61 43 37
^ >?;
?? ((??)){
?? v ?>?;
?? ((??))?? V ?>?;
??? (???? '0;? 2)?? V ?>????????;
?'????????;}
???????? ??(?,???::????????);
?? (!??)?? V ?>*????[?];
?++;
)
}//?? (! ??)...
)
)
------------------- ------------------------------------------------
? v ??.?
//?? ™ ????? S? ?????? ®???? S ???.
#?????? __? v ??_?
#?????? __? v ??_?
#???? v??
#???? v??
#???? v??
#???? v??
#???? v??
#???? v??
?????? ???? ??????[ 20];
//????????? ???????.
???? ???????????();
???? "??????????();
???? ?????????();
???? ?????????????();
???? ????????();
???? ?????????();
???? ???????????();
???? ? v???? v ();
???? ??????????????();
???? ??????????????();
???? ????????(????? [20 ]'??????);
#?????
Список літератури
1. Лафоре Р. Об'єктно-орієнтоване програмування в С + +, 4-е изд. -
СПб.: Питер, 2003. - 928 с.: Ил.
2. Дейтел х.м., Дейтел П.Дж. Як програмувати на С + + .. - М.: Бином,
1999. - 1024 с.
3. Страуструп Б. Мова програмування С + +, 3-е изд. - СПб.; М.: Невский
Діалект - Бином, 1999. - 991 с.
4. Керніган Б., Рітчі Д. Мова програмування Сі.Пер. з англ., 3-еизд., испр. - СПб.: "Невський Діалект", 2001. - 352 с.: Ил.
Примітка 1.
Примітка 2.
