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

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

Национальный Аэрокосмический Университет

Им. Н. Е. Жуковского “ХАИ”

Кафедра 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:

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

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

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

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

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

В программе реализована функция чтения из файла. Если задано три параметра запуска программы, то она принимает argv[2], как название файла, из которого будет происходить считывание информации. Если же задано меньшее количество параметров, то InsetSort предложит ввести названии файла в течении выполнения программы.

Перед выбором пункта 7 (Open File) необходимо очистить массив (пункт 6), иначе программа сигнализирует об ошибке. А после выбора элемента меню 7 введем название считываемого файла данных, если это необходимо.

(Первым элементом файла должно быть число, значение которого равно количеству элементов в файле.) Проделаем вышеуказанные действия и выведем результат на экран:

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

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

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

Исходный код программы с комментариями

—————————————————————– MAIN. CPP

#include “func. h”

Int menu();

Ofstream f;

Char fname[20],foname[20];

Int *MasP[100]={0},n=0,argcGlobal;

////////////////////MAIN/////////////////////

Int main(int argc, char *argv[]){

// int M[10];

int bool=0;//Результаты поискаaða ìaiiàÿ, ïðèiè ìàþùàÿ aâà çià÷aièÿ.(Äëÿ âûõîaà)

argcGlobal=argc;

if (argc>1)//Åñëè çàaài ïàðà ìaòð, òî ïðèiÿòu aãî

strcpy(fname, argv[1]);//êàê iàçâàièa aëÿ ôàeëà îò÷aòà.

else

strcpy(fname,”Log. txt”);

if (argc>2)

strcpy(foname, argv[2]);//Âòîðîe àðão ìaiò – aëÿ ÷òaièÿ.

f. open(fname);//Ñîçaàièa è ïîaãîòîâêà ôàeëà ê çàïèñè.

do{//Âûïîëiÿòu ïîêà bool=0.

bool=menu();//Áàçîâàÿ ôoiêoèÿ ïðîãðà ì ìû.

}while (bool==0);

f. close();//Çàêðûòèa ôàeëà è çàïèñu ià ÆÄ.

cout<<“\n\n\n\n\n\n\n\n\n\n”;

cout<<“InsetSort. v 0.3 (C) 2003-2004 Created by Chaplygin Vasilij.”;

cin. get();

cin. get();

return 0;

}

////////////////////MENU////////////////////

Int menu(){

cout<<endl<<” Main Menu:”<<endl;

cout<<” 1. Make New List.” <<endl;

cout<<” 2. Add Element.” <<endl;

cout<<” 3. Print List.” <<endl;

cout<<” 4. Delete Element.”<<endl;

cout<<” 5. Save List.” <<endl;

cout<<” 6. Erase List.” <<endl;

cout<<” 7. Open File.” <<endl;

cout<<” 8. Find Element.” <<endl;

cout<<” 9. Sort List.” <<endl;

cout<<” 0. Exit.” <<endl;

cout<<endl<<“Your choice : “;

int i;

do

{cin>>i;

if (i<0 || i>9) cout<<endl<<“Error! Try again : “;

}

while (i<0 || i>9);

switch (i)

{case 1 : MakeNewList(); break; //Make New List

case 2 : AddElements(); break; //Add Element

case 3 : PrintList(); break; //Print List

case 4 : DeleteElement(); break; //Delete Element

case 5 : SaveList(); break; //Save List

case 6 : n=0; break; //Erase List

case 7 : OpenList(); break; //Open File

case 8 : FindElement(); break; //Find Element

case 9 : SubMenu(); break; //Sort List

case 0 : return -1; //Exit

}

return 0;

}//menu

—————————————————————– func. cpp

#include “func. h”

Extern int *MasP[100],n, argcGlobal;

Extern ofstream f;

Const int N=100;

//////////////////MakeNewList//////////////////

Void MakeNewList(){

if (n!=0) {cout<<endl<<“Error! You have existing list.”;

cout<<endl<<“Erase your prvious list ang try again.”<<endl;}

else {cout<<endl<<“Input quantity of elements: “;

do{

cin>>n;

if ((n<1)||n>N){

cout<<endl<<“The quantity is incorrect!”<<endl;

cout<<“Max quantity of elemets: “<<N<<endl;

cout<<“Try again: “;}

}while ((n<1)||(n>N));

srand(time(NULL));

for (int i=0; i<n; i++){

MasP[i]=new int;

*MasP[i]=rand()%100;}

}

}

//////////////////AddElements///////////////////

Void AddElements(){

cout<<endl<<“Input quantity of elements: “;

int p;

do{

cin>>p;

if ((p<1)||((n+p)>N)){

cout<<endl<<“The quantity is incorrect!”<<endl;

cout<<“You have “<<N-n<<” free cells.”<<endl;

cout<<“Try again: “;}

}while ((p<1)||((n+p)>N));

srand(time(NULL));

for (int i=n; i<(n+p); i++){

MasP[i]=new int;

*MasP[i]=rand()%100;}

n=n+p;

}

////////////////////PrintList///////////////////

Void PrintList(){

if (n==0) cout<<endl<<“List is empty.”<<endl;

else{

cout<<endl;

for(int i=0; i<n; i++){

if (i%10==0) cout<<endl;

cout<<setw(3)<<*MasP[i];}

cout<<endl;

}

}

////////////////DeleteElement///////////////////

Void DeleteElement(){

if (n==0) cout<<endl<<“List is empty.”<<endl;

else{

cout<<endl<<“Input number of element: “;

int p;

do{

cin>>p;

if ((p<0)||(p>n)) cout<<endl<<“Error! Try again: “;}

while ((p<0)||(p>n));

cout<<endl;

for (int j=(p-1); j<n; j++)

MasP[j]=MasP[j+1];

MasP[n]=0;

n–;

}

}

////////////////////Save List/////////////////////

Void SaveList(){

if (n==0) cout<<endl<<“List is empty.”<<endl;

else{

for (int i=0; i<n; i++){

if (i%10==0) f<<endl;

f<<setw(3)<<*MasP[i];}

f<<endl;

}

}

///////////////////FindElement////////////////////

Void FindElement(){

if (n==0) cout<<endl<<“List is empty.”<<endl;

else{

cout<<endl<<“Input the value, which must be finded: “;

int a, s=0; cin>>a;

for (int i=0; i<n; i++){

if (*MasP[i]==a) {

cout<<endl<<(i+1)<<“-th element”<<” – “<<*MasP[i];

s=i;}}

if (s==0) cout<<endl<<“The existing list hasn’t element with this value”;

cout<<endl;

}

}

//////////////////SubWork(Sort)///////////////////

Void SubMenu(){

if (n==0) cout<<endl<<“List is empty.”<<endl;

else{

cout<<endl<<” Sub Menu:”<<endl;

cout<<” 1. Sort list by increase.”<<endl;

cout<<” 2. Sort list by decrease.”<<endl<<endl;

int i;

cout<<“Your choice: “;

do {

cin>>i;

if (i<1 || i>2) cout<<endl<<“Error! Try again : “<<endl;

}while (i<1 || i>2);

switch (i)

{case 1 : SortByIncrease(); break; //Increase

case 2 : SortByDecrease(); break; //Decrease

}

}

}

/////////////////SortByIncrease//////////////////

Void SortByIncrease(){

int buf;

for (int i=0; i<(n-1); i++){

if (*MasP[i]>*MasP[i+1]){

SaveList();

buf=*MasP[i+1];

for (int j=0; j<(i+1); j++){

if (buf<*MasP[j]){

for (int q=i+1; q>j; q–)

*MasP[q]=*MasP[q-1];

*MasP[j]=buf;

break;

}//Incert place

}//for Incert place

}//Find unsorted element

}//for Find unsorted element

SaveList();

}

/////////////////SortByDecrease//////////////////

Void SortByDecrease(){

int buf;

for (int i=0; i<(n-1); i++){

if (*MasP[i]<*MasP[i+1]){

SaveList();

buf=*MasP[i+1];

for (int j=0; j<(i+1); j++){

if (buf>*MasP[j]){

for (int q=i+1; q>j; q–)

*MasP[q]=*MasP[q-1];

*MasP[j]=buf;

break;

}//Incert place

}//for Incert place

}//Find unsorted element

}//for Find unsorted element

SaveList();

}

///////////////////Open File/////////////////////

Void OpenList(char s[20]){

if (n!=0) {cout<<endl<<“Error! You have existing list.”;

cout<<endl<<“Erase your prvious list ang try again.”<<endl;}

else {

if (argcGlobal<3){

cout<<endl<<“Input file name: “;

char *FileName=new char[20];

cin>>FileName;

s=FileName;}

ifstream fo(s, ios::nocreate);

if (! fo) cout<<“File not found.”<<endl;

else{

int b;

fo>>b;

for (int i=0; i<b; i++){

if (n==N) break;

MasP[n]= new int;

fo>>*MasP[n];

n++;

}

}//if (! fo)…

}

}

——————————————————————- func. h

//Результаты поискаîaêëþ÷àa ì ñòðàæè âêëþ÷aièe.

#ifndef __func_h

#define __func_h

#include <iostream. h>

#include <fstream. h>

#include <stdlib. h>

#include <iomanip. h>

#include <string. h>

#include <time. h>

Extern char foname[20];

//Результаты поискаðîòîòèïû ôoiêoèe.

Void MakeNewList();

Void AddElements();

Void PrintList();

Void DeleteElement();

Void SaveList();

Void EraseList();

Void FindElement();

Void SubMenu();

Void SortByIncrease();

Void SortByDecrease();

Void OpenList(char s[20]=foname);

#endif

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

1. Лафоре Р. Объектно-ориентированное программирование в С++ , 4-е изд. – СПб.: Питер, 2003. – 928 с.: ил.

2. Дейтел Х. М., Дейтел П. Дж. Как программировать на С++ .. – М.: Бином, 1999. – 1024 с.

3. Страуструп Б. Язык программирования С++ , 3-е изд. – СПб.; М.: Невский Диалект – Бином, 1999. – 991 с.

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

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

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


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