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

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

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

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

Кафедра 302

Домашнее задание по курсу

 „Программирование
и алгоритмические языки”

по теме:

„СОРТИРОВКА МАССИВОВ МЕТОДОМ ВСТАВОК”

Выполнил:

студент 326 группы

Чаплыгин В. И.

Проверил:

Момот М. А.

Харьков

2003

Содержание

1.  
Постановка задачи
……………………………………………………………… 3

2.  
Теоретическое обоснование и алгоритм
решения задачи …………………… 3

3.  
Пример работы программы
……………………………………………………. 4

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

5.  
Список литературы
…………………………………………………………… 13

6.  
Приложение 1: блок-схема программы
……………………………………... 14

7.  
Приложение 2: блок-схема функции сортировки
(SortByIncrease()) ……… 15

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

Задание:

Упорядочить
массив x по  убыванию
или возрастанию (т.е. переставить его элементы так чтобы для всех k выполнялось x_k<=x_k-1 или x_k>=x_k-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;//Ïåðåìåííàÿ,
ïðèíèìàþùàÿ
äâà
çíà÷åíèÿ.(Äëÿ
âûõîäà)

  argcGlobal=argc;

  if (argc>1)//Åñëè
çàäàí
ïàðàìåòð, òî
ïðèíÿòü åãî

    strcpy(fname,argv[1]);//êàê
íàçâàíèå
äëÿ ôàéëà
îò÷åòà.

  else

     strcpy(fname,"Log.txt");

  if (argc>2)

    strcpy(foname,argv[2]);//Âòîðîé
àðãóìåíò -
äëÿ ÷òåíèÿ.

  f.open(fname);//Ñîçäàíèå
è
ïîäãîòîâêà
ôàéëà ê
çàïèñè. 

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

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

  }while (bool==0);

  f.close();//Çàêðûòèå
ôàéëà è
çàïèñü íà ÆÄ.

  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

//Ïîäêëþ÷àåì
ñòðàæè
âêëþ÷åíèé.

#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];

//Ïðîòîòèïû
ôóíêöèé.

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.