|
Сортировка массивов методом вставокСортировка массивов методом вставокМинистерство Образования и Науки Украины Национальный Аэрокосмический Университет им. Н. Е. Жуковского “ХАИ” Кафедра 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 ^ 1)//???? ??™?? ?????S??, ?? ??????? S©? ??????(?????,????[1]);//??? ???®???S ™?? ????? ???S??. ???? ??????(?????,????.????); ?? (????>2) ??????(??????,????[2]);//?????? ??©??S?? - ™?? ??S???. ?.????(?????);//???™???S ? ??™©???®?? ????? ? ??????. ??{//????????? ???? ????’0. ????’???v();//????®?? ??????? ???©?????. }????? (????’’0); ?.?????();//???????S ????? ? ?????? ?? ??. ??v?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?>?; ?? ((??){ ??v??)); ?????(????(????)); ??? (??? ?’0; ?>?; ?? ((??)){ ??v??)); ?????(????(????)); ??? (??? ?’?; ?>?; ??? (??? ?’0; ?>?;????? (?2); ?????? (?) {???? 1 : ??????????????(); ?????; //???????? ???? 2 : ??????????????(); ?????; //???????? } } } /////////////////??????????????////////////////// ???? ??????????????(){ ??? ?v?; ??? (??? ?’0; ?*????[?+1]){ ????????(); ?v?’*????[?+1]; ??? (??? ?’0; ??; ?--) *????[?]’*????[?-1]; *????[?]’?v?; ?????; }//?????? ????? }//??? ?????? ????? }//???? v??????? ??????? }//??? ???? v??????? ??????? ????????(); } /////////////////??????????????////////////////// ???? ??????????????(){ ??? ?v?; ??? (??? ?’0; ?*????[?]){ ??? (??? ?’?+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. |
|
