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

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

Кафедра 302

Домашнее задание по курсу
„Программирование и алгоритмические языки”
по теме
„СОРТИРОВКА МАССИВОВ МЕТОДОМ ВСТАВОК”

Выполнил
студент 326 группы
Чаплыгин В. И.
Проверил
Момот М. А.

Харьков
2003

Содержание

Постановка задачи ……………………………………………………………… 3
Теоретическое обоснование и алгоритм решения задачи …………………… 3
Пример работы программы ……………………………………………………. 4
Исходный код программы с комментариями …………………………………. 9
Список литературы …………………………………………………………… 13
Приложение 1 блок-схема программы ……………………………………… 14
Приложение 2 блок-схема функции сортировки (SortByIncrease()) ……… 15

Постановка задачи

Задание
Упорядочить массив x по убыванию или возрастанию (т.е. переставить его элементы так чтобы для всех k выполнялось xk<=xk-1 или 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
^ <~~
10 41 54 66 27 42 80 61 43 37
^ <~~
10 27 41 54 66 42 80 61 43 37
^ <~~
10 27 41 42 54 66 80 61 43 37
^ <~~
10 27 41 42 54 61 66 80 43 37
^ <~~
10 27 41 42 43 54 61 66 80 37
^ <~~
10 27 37 41 42 43 54 61 66 80

см. приложение 2.

Пример работы программы
Запускаем программу InsetSort

Программа прелагает нам выбрать один из пунктов меню для выполнения соответствующей операции. Итак, выбираем 1

Введем желаемое количество элементов массива.

Массив создан. Теперь можно вывести массив на экран, добавить некоторое количество элементов, найти какой-либо элемент по значению и т.д. Выведем массив на экран.

Также эта программа предоставляет возможность удалить какой-либо элемент, введя его порядковый номер. Допустим, мы хотим удалить элемент под номером 7 со значением 89, затем выведем снова массив на экран

Теперь добавим 6 элементов к существующему массиву

В программе реализована функция чтения из файла. Если задано три параметра запуска программы, то она принимает argv[2], как название файла, из которого будет происходить считывание информации. Если же задано меньшее количество параметров, то InsetSort предложит ввести названии файла в течении выполнения программы.
Перед выбором пункта 7 (Open File) необходимо очистить массив (пункт 6), иначе программа сигнализирует об ошибке. А после выбора элемента меню 7 введем название считываемого файла данных, если это необходимо.
(Первым элементом файла должно быть число, значение которого равно количеству элементов в файле.) Проделаем вышеуказанные действия и выведем результат на экран

При выборе пункта 9 у нас будет возможность отсортировать массив элементов, как по возрастанию, так и по убыванию. Например, отсортируем существующий массив по возрастанию и выведем результат на экран

В итоге мы получили отсортированный массив и массу удовольствия при работе в этой чудотворной программе. А кроме этого еще и файл отчёта, в который были записаны все шаги к полной сортировке массива.
Помните, что файл будет создан только после корректного завершения программы InsetSort.

Исходный код программы с комментариями








 








































 
 



 


 
 









































































































 




 
 






























































































Список литературы

Лафоре Р. Объектно-ориентированное программирование в С++, 4-е изд. — СПб. Питер, 2003. – 928 с. ил.
Дейтел Х.М., Дейтел П.Дж. Как программировать на С++.. – М. Бином, 1999. — 1024 с.
Страуструп Б. Язык программирования С++, 3-е изд. — СПб.; М. Невский Диалект — Бином, 1999. — 991 с.

4. Керниган Б., Ритчи Д. Язык программирования Си.Пер. с англ., 3-е изд., испр. — СПб. Невский Диалект», 2001. — 352 с. ил.

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

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