Сортировка масивів методом вставок

Министерство Освіти і Науки Украины.

Національний Аерокосмічний Університет їм. М. Є. Жуковського «ХАИ».

Кафедра 302.

Домашнє завдання з курсу.

«Програмування і алгоритмічні мови» по теме:

«СОРТУВАННЯ МАСИВІВ МЕТОДОМ ВСТАВОК».

Виконав: студент 326 группы.

Чаплыгин У. И.

Проверил:

Момот М. А.

Харьков.

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, *.срр).

. Повинні використовуватися уловная компіляція (варти включения).

. Програма повинен мати дружній інтерфейс — основні операції повинні викликатися через відповідні елементи текстового меню.

. Ітерації в текстовий файл отчета.

. Передача імені файла звіту в командної строке.

. Зчитування вихідних даних із файла.

. Використання параметрів командної cтроки.

Теоретичне обгрунтування метода.

«Сортування з допомогою прямого включення» і алгоритм виконання завдання Метод полягає в наступному: вважається, і розглядом записи 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 аналізує, поки значення буферної перемінної нічого очікувати менше будь-якого елемента x. Потім шматок масиву, починаючи з x і по j, переміщається однією осередок убік зростання, і утворене місце x записується значення переміщуваного елемента. Далі триває переміщення основному масиву до елемента n-1 (т.к. ми порівнюємо j-й і (j+1)-й елементи): 41 54 10 66 27 42 80 61 43 37 ^ >?;

?? ((??)){.

??v?>?;

?? ((??)) ??v?>?;

??? (??? ?'0; ?2) ??v?>???;

?'???;}.

??? ??(?,???:???);

?? (! ??) ??v?>*???[?];

?++;

}.

}//?? (! ??)…

}.

}.

—————————————————————————————————;

?v???

//??™???P.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 з.: ил.

[pic].

Примітка 1.

[pic].

Примітка 2.