Разработка программы сортировки одномерного массива с помощью гномьей сортировки
Характеристика описания среды программирования С++. Исследование возможности задания элементов массива вручную и с помощью генератора случайных чисел. Расчет количества затраченных итераций для сортировки гномья. Проведение тестирования программы.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 31.01.2017 |
| Размер файла | 183,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Содержание
1. Теоретическая часть
1.1 Описание среды программирования C++
2. Практическая часть
2.1 Реализация программного продукта позволяющего проводить сортировку одномерного массива фиксированной размерности
2.2 Тестирование программы
Заключение
Список литературы
Приложение
1. Теоретическая часть
Гномья сортировка (англ. Gnome sort) -- алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков.
Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на текущий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.
Дик Грун
Алгоритм концептуально простой, не требует вложенных циклов. Время работы {\displaystyle O\left(n^{2}\right)}. На практике алгоритм может работать так же быстро, как и сортировка вставками.
Алгоритм находит первое место, где два соседних элемента стоят в неправильном порядке и меняет их местами. Он пользуется тем фактом, что обмен может породить новую пару, стоящую в неправильном порядке, только до или после переставленных элементов. Он не допускает, что элементы после текущей позиции отсортированы, таким образом, нужно только проверить позицию до переставленных элементов.
Пример: массив сортировка генератор тестирование
Если мы хотим отсортировать массив с элементами [4] [2] [7] [3] от большего к меньшему, то на итерациях цикла while будет происходить следующее:
· [4] [2] [7] [3] (начальное состояние: i == 1, j == 2);
· [4] [2] [7] [3] (ничего не произошло, но сейчас i == 2, j == 3);
· [4] [7] [2] [3] (обмен a[2] и a[1], сейчас i == 1, а j == 3 по-прежнему);
· [7] [4] [2] [3] (обмен a[1] и a[0], сейчас i == 3, j == 4);
· [7] [4] [3] [2] (обмен a[3] и a[2], сейчас i == 2, j == 4);
· [7] [4] [3] [2] (ничего не произошло, но сейчас i == 4, j == 5);
· цикл закончился, т. к. i не < 4.
1.1 Описание среды программирования C++
Borland C++ -- среда программирования (IDE), разработанная фирмой Borland для создания программ на языках программирования Си и C++. Каждая версия среды включает компилятор, поддерживающий свой стандарт языка программирования. Первоначально, среда программирования использовалась для создания программ под DOS, но с появлением и распространением Windows и Windows NT, были предложены средства для разработки приложений для этих операционных систем. Borland C++ исторически восходит к Turbo C, но, в отличие от Turbo C, поддерживает объектно-ориентированное программирование. За время своего развития среда разработки дополнялась специализированными библиотеками, предназначенными для быстрой разработки приложений. В частности, примером применения объектно-ориентированного подхода для создания приложений под DOS стала библиотека Turbo Vision, в то время как аналогичным примером применения объектно-ориентированного подхода для создания приложений под Windows стала библиотека Object Windows Library. C++Builder объединяет в себе комплекс объектных библиотек (STL, VCL, CLX, MFC и др.), компилятор, отладчик, редактор кода и многие другие компоненты. Цикл разработки аналогичен Delphi. Большинство компонентов, разработанных в Delphi, можно использовать и в C++Builder без модификации, но обратное утверждение не верно. C++Builder содержит инструменты, которые при помощи drag-and-drop действительно делают разработку визуальной, упрощает программирование благодаря встроенному WYSIWYG-редактору интерфейса и пр.
2. Практическая часть
2.1 Реализация программного продукта позволяющего проводить сортировку одномерного массива фиксированной размерности.
Сортировка гномья.
«Гномья» сортировка
Рисунок 2.1 алгоритм сортировка гномья
Описание алгоритма:
Гном смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Если нет предыдущего горшка (назад идти некуда), то он шагает вперёд; если нет следующего горшка (вперёд идти некуда), то сортировка закончена.
Ниже расположен программный код, позволяющий производить гномью сортировку одномерного массива фиксированной размерности.
//Подключаем необходимые библиотеки
#include<stdlib.h>
#include<conio.h>
#include<iostream.h>
//главный функция(метод) программы в котором реализован метод гномьей сортировки
int main()
{
const int N=10;
int A[N],i,tmp;
randomize();
for(i=0;i<N;i++)
{
A[i]=random(10);
cout<<A[i]<<" ";
}
cout<<endl;
//алгоритм гномьей сортировки
i = 0;
while (i < N)
{
if (i == 0 || A[i - 1] <= A[i]) ++i;
else
{
tmp = A[i];
A[i] = A[i - 1];
A[i - 1] = tmp;
--i;
}
}
//функция программы которая выводит числа по возрастанию
for(i=0;i<N;i++)
cout<<A[i]<<" ";
getch();
return 0;
}
2.2 Тестирование программы
Теперь проведем гномью сортировку одномерного массива в программе
Заключение
В результате выполнения поставленной задачи было создано приложение позволяющее производить сортировку одномерного массива фиксированной размерности методом сортировки - гномья.
Приложение разработано в среде С++.
Поставленные задачи решены, цель курсовой работы достигнута.
Список литературы
1. Язык программирования C++. Лекции и упражнения, 6-е издание Автор: Стивен Прата Издательство: Вильямс Год: 2012
2. C++: базовый курс Автор: Герберт Шилдт Издательство: Вильямс Год: 2008
Приложение
int main()
{
const int N=10;
int A[N],i,tmp;
randomize();
for(i=0;i<N;i++)
{
A[i]=random(10);
cout<<A[i]<<" ";
}
cout<<endl;
i = 0;
while (i < N)
{
if (i == 0 || A[i - 1] <= A[i]) ++i;
else
{
tmp = A[i];
A[i] = A[i - 1];
A[i - 1] = tmp;
--i;
}
}
for(i=0;i<N;i++)
cout<<A[i]<<" ";
getch();
return 0;
}
int main()
{
const int N=10;
int A[N],i,tmp;
randomize();
for(i=0;i<N;i++)
{
A[i]=random(10);
cout<<A[i]<<" ";
}
cout<<endl;
i = 0;
while (i < N)
{
if (i == 0 || A[i - 1] <= A[i]) ++i;
else
{
tmp = A[i];
A[i] = A[i - 1];
A[i - 1] = tmp;
--i;
}
}
getch();
return 0;
}
Размещено на Allbest.ru
...Подобные документы
Модификация и сравнения двух текстовых файлов. Программа, написанная на языке программирования Cи и работоспособна на IBM совместимых компьютерах. Псевдографический и графический интерфейсы. Анализ программы методом сортировки одномерного массива.
курсовая работа [116,2 K], добавлен 21.02.2008Исследование основных особенностей алгоритмов быстрой и поразрядной сортировки данных. Построение графиков зависимости времени сортировки от количества элементов в файле и от степени перемешенности элементов. Описания сортировки чисел и строковых данных.
лабораторная работа [1,2 M], добавлен 23.07.2012Создание программы визуализации методов сортировки массива, особенности и направления ее практического применения. Выбор и обоснование среды программирования. Разработка руководства пользователя. Листинг программы и оценка эффективности ее использования.
дипломная работа [1,0 M], добавлен 15.06.2014Анализ основных алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Сортировка пузырьком, методами вставок, выбора, методом Шелла, быстрая сортировка. Операция разделения массива внутренней сортировки.
курсовая работа [161,7 K], добавлен 17.12.2015Составление программы сортировки по возрастанию массив из 20 шестнадцатеричных чисел, просматривающей все исходные числа во внешней памяти и выбирающей самое большое число. Блок-схема алгоритма работы программы. Таблица команд и число их выполнения.
курсовая работа [23,1 K], добавлен 24.05.2015Программы линейной структуры. Составление программы, которая по заданному номеру и значению соответствующего элемента вычисляет значение всех остальных элементов треугольника. Формулирование одномерного массива с помощью генератора случайных чисел.
отчет по практике [1,2 M], добавлен 01.12.2012Разработка программы для осуществления сортировки данных методами "Выбора" с использованием языка C# и Visual Studio 2012. Плавный метод сортировки. Основные фазы сортировки во внутреннем представлении пирамиды. Программа сортировки методами выбора.
курсовая работа [637,6 K], добавлен 29.11.2014Краткое описание языка программирования С++. Алгоритм линейного выбора элемента, методов минимального (максимального) элемента и челночной сортировки. Анализ и разработка приложения, организующего сортировку массива данных пятью методами сортировки.
реферат [614,8 K], добавлен 12.04.2014Решения задачи графическим и программным способами. Описание алгоритма решения графическим способом, укрупненная схема алгоритма. Ввод элементов двумерного массива, вывод преобразованного массива, разработка программы на языке pascal, листинг программы.
курсовая работа [115,5 K], добавлен 22.05.2010Анализ эффективности методов сортировки данных в языке Turbo Pascal. Разработка эскизного и технического проекта программы. Сортировка без и с использованием дополнительной памяти, за исключением небольшого стека (массива). Сортировка связанных списков.
курсовая работа [359,0 K], добавлен 23.05.2012Исторические предпосылки разработки тестирования. Виды электронных тестов и их роль в программировании. Этапы разработки программы для решения задачи быстрой сортировки. Пользовательский интерфейс, отладка, алгоритм программы. Файл теста в формате XML.
курсовая работа [1,5 M], добавлен 27.01.2014Анализ структуры топологической сортировки в программной среде. Метод топологической сортировки с помощью обхода в глубину. Программа, реализующая топологическую сортировку методом Демукрона. Создание карты сайта и древовидная система разделов.
курсовая работа [1,3 M], добавлен 22.06.2011Общая характеристика организации массива в виде двоичного дерева. Особенности линейного и двоичного поиска заданного элемента массива. Методика упорядочения массива методом сортировки деревом. Инструкции и текст программы для нечисленной обработки данных.
курсовая работа [242,3 K], добавлен 12.11.2010Изучение алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Отличительные черты сортировки включением, выбором, разделением, сортировки Шелла, обменной сортировки. Сравнение методов: плюсы и минусы.
курсовая работа [203,8 K], добавлен 03.12.2010Обработка массивов элементов любого типа как главное назначение алгоритмов сортировки. Анализ наиболее используемых алгоритмов сортировки: пузырьком, выбором, вставками, методом Шелла и быстрой сортировкой. Основные требования к алгоритмам сортировки.
реферат [189,8 K], добавлен 06.12.2014GetMatrDop как процедура определяет значение элемента транспонированной матрицы дополнений. Знакомство с этапами разработки в среде Turbo Pascal программы сортировки элементов, находящихся на главной диагонали матрицы. Особенности тестирования программы.
курсовая работа [780,4 K], добавлен 20.11.2014Алгоритмы сортировки методами простых вставок и пузырька. Зависимость среднего времени сортировки от числа сортируемых элементов. Функции, осуществляющие сортировку любого количества элементов методом простых вставок, на основе сортировки таблицы адресов.
курсовая работа [557,1 K], добавлен 26.05.2010Понятие алгоритма и сортировки. Способы и алгоритмы сортировки массивов. Быстрая сортировка Хоара. Описание алгоритма "быстрой сортировки". Реализация на языке программирования. Анализ наихудшего разбиения. Вероятностные алгоритмы быстрой сортировки.
курсовая работа [291,5 K], добавлен 22.03.2012Составление программы для нахождения минимального и максимального элементов массива. Программа вычисления корней квадратных алгебраических уравнений. Ранжирование одномерного массива по заданному признаку. Формирование массивов с помощью функции random.
контрольная работа [1,0 M], добавлен 30.04.2013Понятие и основной принцип действия алгоритмов сортировки информации. Сравнительное исследование и анализ эффективности методов сортировки Шелла и Флойда в виде графиков зависимостей количества сравнений и числа перестановок элементов от объёма данных.
контрольная работа [573,6 K], добавлен 09.11.2010
