Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Сортировка массивов методом вставок
Раздел: Рефераты по информатике, программированию
Тип: реферат Добавлен 05:38:22 17 сентября 2005 Похожие работы
Просмотров: 623 Комментариев: 4 Оценило: 3 человек Средний балл: 2 Оценка: неизвестно     Скачать

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

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

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

Кафедра 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;//Ïåðåìåííàÿ, ïðèíèìàþùàÿ äâà çíà÷åíèÿ.(Äëÿ âûõîäà)

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.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений22:12:43 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
13:26:14 24 ноября 2015
ФИГНЯ
Алексей22:40:37 26 мая 2010
малою. очень мало для реферата темболее если мне по ней задали курсяк
лёха03:23:46 22 января 2008Оценка: 2 - Плохо

Работы, похожие на Реферат: Сортировка массивов методом вставок

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(151310)
Комментарии (1844)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru