Министерство Образования и Науки Украины
Национальный Аэрокосмический Университет им. Н. Е. Жуковского “ХАИ”
Кафедра 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.