Сортировка массивов методом вставок
Работа из раздела: «
Программирование и комп-ры»
Министерство Образования и Науки Украины
Национальный Аэрокосмический Университет
им. Н. Е. Жуковского “ХАИ”
Кафедра 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 или 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:
[pic]
Программа прелагает нам выбрать один из пунктов меню для выполнения
соответствующей операции. Итак, выбираем 1:
[pic]
Введем желаемое количество элементов массива.
[pic]
Массив создан. Теперь можно вывести массив на экран, добавить некоторое
количество элементов, найти какой-либо элемент по значению и т.д. Выведем
массив на экран.
[pic]
Также эта программа предоставляет возможность удалить какой-либо элемент,
введя его порядковый номер. Допустим, мы хотим удалить элемент под
номером 7 со значением 89, затем выведем снова массив на экран:
[pic]
Теперь добавим 6 элементов к существующему массиву:
[pic]
В программе реализована функция чтения из файла. Если задано три
параметра запуска программы, то она принимает argv[2], как название
файла, из которого будет происходить считывание информации. Если же
задано меньшее количество параметров, то InsetSort предложит ввести
названии файла в течении выполнения программы.
Перед выбором пункта 7 (Open File) необходимо очистить массив (пункт
6), иначе программа сигнализирует об ошибке. А после выбора элемента меню
7 введем название считываемого файла данных, если это необходимо.
(Первым элементом файла должно быть число, значение которого равно
количеству элементов в файле.) Проделаем вышеуказанные действия и выведем
результат на экран:
[pic]
При выборе пункта 9 у нас будет возможность отсортировать массив
элементов, как по возрастанию, так и по убыванию. Например, отсортируем
существующий массив по возрастанию и выведем результат на экран:
[pic]
В итоге мы получили отсортированный массив и массу удовольствия при
работе в этой чудотворной программе. А кроме этого еще и файл отчёта, в
который были записаны все шаги к полной сортировке массива.
Помните, что файл будет создан только после корректного завершения
программы InsetSort.
Исходный код программы с комментариями
-----------------------------------------------------------------
?“??.X??
#????v?? ??v??.??
??? ???v();
???????? ?;
???? ?????[20],??????[20];
??? *????[100]’{0},?’0,??????????;
////////////////////?“??/////////////////////
??? ????(??? ????,???? *????[]){
// ??? ?[10];
??? ????’0;//?S?S?S????, ??????????? ™®? ????S???.(??? ®???™?)
??????????’????;
?? (????>1)//???? ??™?? ?????S??, ?? ??????? S©?
??????(?????,????[1]);//??? ???®???S ™?? ????? ???S??.
????
??????(?????,????.????);
?? (????>2)
??????(??????,????[2]);//?????? ??©??S?? - ™?? ??S???.
?.????(?????);//???™???S ? ??™©???®?? ????? ? ??????.
??{//????????? ???? ????’0.
????’???v();//????®?? ??????? ???©?????.
}????? (????’’0);
?.?????();//???????S ????? ? ?????? ?? ??.
??v?<>?;
?? (?<0 || ?>9) ??v?<9);
?????? (?)
{???? 1 : ???????????(); ?????; //???? ??? ????
???? 2 : “??????????(); ?????; //“?? ???????
???? 3 : ?????????(); ?????; //????? ????
???? 4 : ?????????????(); ?????; //?????? ???????
???? 5 : ????????(); ?????; //???? ????
???? 6 : ?’0; ?????; //????? ????
???? 7 : ????????(); ?????; //???? ????
???? 8 : ???????????(); ?????; //???? ???????
???? 9 : ?v????v(); ?????; //???? ????
???? 0 : ???v?? -1;
//????
}
???v?? 0;
}//???v
-----------------------------------------------------------------
?v??.???
#????v?? ??v??.??
?????? ??? *????[100],?,??????????;
?????? ???????? ?;
????? ??? ?’100;
//////////////////???????????//////////////////
???? ???????????(){
?? (?!’0) {??v?<>?;
?? ((?<1)||?>?){
??v?<?));
?????(????(????));
??? (??? ?’0; ?>?;
?? ((?<1)||((?+?)>?)){
??v?<?));
?????(????(????));
??? (??? ?’?; ?<(?+?); ?++){
????[?]’??? ???;
*????[?]’????()%100;}
?’?+?;
}
////////////////////?????????///////////////////
???? ?????????(){
?? (?’’0) ??v?<>?;
?? ((?<0)||(?>?)) ??v?<?));
??v?<>?;
??? (??? ?’0; ?>?;
?? (?<1 || ?>2) ??v?<2);
?????? (?)
{???? 1 : ??????????????(); ?????; //????????
???? 2 : ??????????????(); ?????; //????????
}
}
}
/////////////////??????????????//////////////////
???? ??????????????(){
??? ?v?;
??? (??? ?’0; ?<(?-1); ?++){
?? (*????[?]>*????[?+1]){
????????();
?v?’*????[?+1];
??? (??? ?’0; ?<(?+1); ?++){
?? (?v?<*????[?]){
??? (??? ?’?+1; ?>?; ?--)
*????[?]’*????[?-1];
*????[?]’?v?;
?????;
}//?????? ?????
}//??? ?????? ?????
}//???? v??????? ???????
}//??? ???? v??????? ???????
????????();
}
/////////////////??????????????//////////////////
???? ??????????????(){
??? ?v?;
??? (??? ?’0; ?<(?-1); ?++){
?? (*????[?]<*????[?+1]){
????????();
?v?’*????[?+1];
??? (??? ?’0; ?<(?+1); ?++){
?? (?v?>*????[?]){
??? (??? ?’?+1; ?>?; ?--)
*????[?]’*????[?-1];
*????[?]’?v?;
?????;
}//?????? ?????
}//??? ?????? ?????
}//???? v??????? ???????
}//??? ???? v??????? ???????
????????();
}
///////////////////???? ????/////////////////////
???? ????????(???? ?[20]){
?? (?!’0) {??v?<>????????;
?’????????;}
???????? ??(?,???::????????);
?? (! ??) ??v?<>?;
??? (??? ?’0; ?>*????[?];
?++;
}
}//?? (! ??)...
}
}
-------------------------------------------------------------------
?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.
