Министерство Образования и Науки Украины

Национальный Аэрокосмический Университет им. Н. Е. Жуковского “ХАИ”

Кафедра 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, *.срр).

. Должны использоваться уловная компиляция (стражи включения).

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

. Итерации в текстовый файл отчета.

. Передача имени файла отчета в командной строке.

. Считывание исходных данных из файла.

. Использование параметров командной 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 анализирует, пока значение буферной переменной не будет меньше какого-либо элемента х. Затем кусок массива, начиная с х и до 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 с.: ил.

[pic]

Примечание 1.

[pic]

Примечание 2.