Тема: Разработка учебной программы по работе с
массивами чисел «Методы сортировки».
1.3.2 Перечень документов, на основании которых создается программа
2.1 Разработка desktop приложений
2.2 GUI: библиотеки и визуальные среды разработки, сравнительная характеристика
2.3 Средства языка Java для реализации алгоритмов
3.2.1 Разработка интерфейса GUI
3.2.2 Реализация методов сортировки
3.2.3 Реализация ограничения по времени работы
4.3 Порядок и особенности работы
СПИСОК ИСПОЛЬЗОВАНЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ
Дипломный проект выполнен в соответствии с заданием на дипломное проектирование, выданным 06.04.2015 г. Темой проекта является разработка учебной программы по работе с массивами чисел «Методы сортировки».
Обычно, современным преподавателям нужно помочь усвоить студентам огромное количество информации. Это требует огромных затрат времени и сил, но, к сожалению, не всегда достигается желаемый результат. В наше время, когда информационные технологии играют огромную роль в современном обществе, каждый день человек получает большое количество информации, и усвоить все что нужно бывает невозможно. Хоть в сети интернет сейчас и можно найти практически всё, что может быть нужно, от обычной информации, до видео или программных ресурсов, это не всегда может помочь студентам в усвоении информации.
Все эти факты делают вопрос о создании программы, демонстрирующей на практике эффективность современных сортировок массивов, крайне актуальным. Связано это с тем, что при создании хорошо спланированного, информационного сайта, приходится применять не только технологические знания о сетях, и аналитические, но и творческие, что позволяет более полно раскрыть специфику специальности «Программирование в компьютерных системах».
Выбор темы для дипломного проекта связан со всеми этими причинами.
Актуальность темы
Актуальность темы обусловлена необходимостью создания учебной программы для наглядной демонстрации работы методов сортировки массивов на языке Java, так как это поможет воспринять результативность методов на конкретном примере.
Цель работы
Основной целью дипломного проекта является разработка программы для демонстрации работы алгоритмов сортировки массивов на языке Java.
Для достижения поставленной цели необходимо решить следующие задачи:
1. Изучить алгоритмы сортировки массивов разной сложности.
2. Проанализировать возможности реализации алгоритмов сортировки на языке Java.
3. Реализовать алгоритмы сортировки массивов на языке Java и обеспечить быструю и стабильную работу.
4. Разработать программу для сортировки массива различными методами и вывода времени сортировок.
Объектами исследования являются алгоритмы сортировки массивов, как быстрые и медленные, так и неэффективные.
Предметом исследования являются средства реализации алгоритмов сортировки массивов на языке Java и реализация пользовательского интерфейса программы.
Методы исследования
Методы работы основываются на изучении языка программирования Java. Исследование проводилось посредством изучения алгоритмов сортировки массивов. Подбор необходимых материалов по разработке программы осуществлялся из Internet и соответствующей литературы.
В процессе разработки программы был использован язык программирования Java.
Практическая значимость
Программа предоставляет возможность создать массив нужного нам размера в памяти компьютера, перемешать его элементы между собой и сортировать интересующим нас методом сортировки. Далее программа выводит успешность сортировки и время, затраченное на нее. Далее мы можем сортировать тот же массив другим методом и сравнить их эффективность, по затраченному времени.
На защиту выносятся результаты исследования технологий разработки программы, программа «Методы сортировки», обоснование ее экономической эффективности.
Гипотеза исследования
Использование программы «Методы сортировки», созданной в рамках дипломного проекта и технического задания, в первую очередь повлияет на снижение времени, затрачиваемого на определение эффективности различных методов сортировки массивов. Программа, имеющая такие возможности, привлечет к себе внимание в первую очередь студентов, только еще обучающимся основам программирования и поможет усвоить им тему «Сортировка массива». При внедрении программы в учебный процесс, она может сэкономить время преподавателя и студентов, демонстрируя работу методов сортировки на практике.
Структура и объем работы
Дипломный проект состоит из
введения, трех разделов, заключения, библиографического списка - включающего 15
наименований. Общий объём работы – 114 страницы, основной текст занимает 88
страницы, библиографический список – 1 страницу, приложение – 26 страниц.
Исследовательской деятельностью, связанной с дипломным проектом, является изучение массивов и методов их сортировок.
Массив — это пронумерованная последовательность величин одинакового типа, обозначаемая одним именем. Элементы массива располагаются в последовательных ячейках памяти, обозначаются именем массива и индексом. Каждое из значений, составляющих массив, называется его компонентой (или элементом массива).
Массив данных в программе рассматривается как переменная структурированного типа. Массиву присваивается имя, посредством которого можно ссылаться как на массив данных в целом, так и на любую из его компонент.
Вообще, массив – однородный, упорядоченный структурированный тип данных с прямым доступом к элементам.
Переменные, представляющие компоненты массивов, называются переменными с индексами в отличие от простых переменных, представляющих в программе элементарные данные. Индекс в обозначении компонент массивов может быть константой, переменной или выражением порядкового типа (целочисленный, логический, символьный, перечислимый, диапазон).
Если за каждым элементом массива закреплен только один его порядковый номер, то такой массив называется линейным. Вообще количество индексов элементов массива определяет размерность массива. По этом признаку массивы делятся на одномерные (линейные), двумерные, трёхмерные и т.д.
Сортировка массивов
Сортировкой называется такой процесс перестановки элементов массива, когда все его элементы выстраиваются по возрастанию или по убыванию.
Сортировать можно не только числовые массивы, но и, например, массивы строк (по тому же принципу, как расставляют книги на библиотечных полках). Вообще сортировать можно элементы любого множества, где задано отношение порядка.
Существуют универсальные алгоритмы, которые выполняют сортировку вне зависимости от того, каким было исходное состояние массива. Но кроме них существуют специальные алгоритмы, которые, например, очень быстро могут отсортировать почти упорядоченный массив, но плохо справляются с сильно перемешанным массивом (или вообще не справляются). В дипломном проекте рассматриваются быстрые, медленные и неэффективные алгоритмы сортировки.
Основной целью дипломного проекта является изучение алгоритмов сортировки, а так же реализация этих методов на языке программирования Java, разработка программы, которая покажет эффективность различных алгоритмов сортировки на одном и том же массиве. Основные требования к создаваемой программе формулируются следующим образом:
1. Полное соответствие содержания учебной программе соответствующей учебной дисциплины.
2. Комплексность, достаточная для самостоятельного изучения и практического усвоения учебного материала соответствующей дисциплины учащимися при консультационной поддержке и контроле со стороны преподавателей.
3. Удобство и наглядность навигации в программе, простота и оперативность в получении нужного результата.
4. Включение в состав предоставленных алгоритмов сортировки алгоритмы разной сложности.
5. Типизация применения экранного пространства при организации пользовательского интерфейса.
6. Возможность применения на персональных компьютерах средней производительности с типовым набором аппаратно-программных средств.
7. Предоставление возможности работы с алгоритмами сортировок, использующие разные методы подхода к сортировке массива.
8. Реализовать алгоритмы сортировки массивов на языке Java максимально эффективно, для быстрой сортировки массивов.
Программа разрабатывалась по выданному техническому заданию и реализована на языке программирования Java.
Название программы емко отображает суть функциональной части программы «Методы сортировки», где используются различные методы для реализации сортировки различных по величине массивов.
1.3.2 Перечень документов, на основании которых создается программа
Разработка программы велась на основании технического задания.
Программа «Методы сортировки» состоит из одного открытого класса Wind, который, в свою очередь включает в себя:
1. Метод public static void main(String[] args), запускающий программу;
2. Метод private void initialize(), инициализирующий графический интерфейс;
3. Методы сортировок.
2.1 Разработка desktop приложений
Несмотря на победное шествие Интернета и веб-приложений по планете, изредка всё еще встречаются задачи, которые можно решить с помощью обычной программы, просто работающей на одном отдельно взятом компьютере. Подобную задачу мы и решаем.
Для разработки приложений на языке программирования Java используется множество программ, но хотелось бы выделить некоторые из наиболее доступных и используемых на практике разработчиками программного обеспечения.
NetBeans («сетевые компоненты») — бесплатная среда с открытым исходным кодом. Быстро устанавливается. Разрешено использование в коммерческих целях. Логотип NetBeans приведен на рисунке 2.1.
 |
В нее входит развитый инструмент, позволяющий подключать различные плагины, позволяющих настроить инструмент для ваших целей. При этом нет необходимости искать эти плагины. Имеется централизованный центр, где собраны все подключаемые плагины, так же есть возможность подключить свои и сторонних разработчиков.
В редактор входит одна из лучших возможность редакторов пользовательских форм, интерфейсов и отличное средство для разработки мобильных приложений. Так же из всех бесплатных сред набор примеров, исходных кодов, создание на основе шаблонов различного тип проекты, возможность создания документации на основе комментариях.
Имеет возможность тестирование с помощью модулей JUnit. Развитое средство UML — проектирования. Поддерживает импорт проектов Eclipse.
К недостаткам можно отнести относительно большое количество ресурсов 250 Мб в развернутом виде и 350 Мб оперативной памяти в рабочем состояние это имеет ряд требований к аппаратуре: не менее 512 Мб оперативной памяти и процессор не ниже 1000 тактовой частоты. Так же не очень удобная система справок.
 |
Рисунок 2.2 – Логотип Eclipse.
Первая среда в которой стало возможно подключать плагины. Имеет несколько сайтов так называемых репозитрариев в которых есть большое количество модулей разделенных по категориям, так же есть возможность подключать свои модули.
Недостатки: так же как и NetBeans потребляет относительно много ресурсов 260 мб оперативной памяти и 335 мб на диске при работе простейшего приложения форм. Практически нет примеров и шаблонов. Отсутствует встроенный редактор пользовательских форм (требует отдельной установки). Часто встречается не совместимость плагинов от разных производителей. Нет встроенной возможности разрабатывать приложения для мобильных устройств. Не умеет самостоятельно опознавать установленные на компьютере JDK. Не поддерживает импорт проектов NetBeans.
Вывод: среда разработки Eclipse является мощнейшим средством разработки приложений пригодный для реальной разработки — Java и несомненно заслуживающий уважения и внимания. На ней и был остановлен выбор среды разработки программы на языке программирования Java в рамках дипломного проекта.
Для разработки программ на языке Java потребуется специальное программное обеспечение. Самые новые версии системного программного обеспечения, необходимого для поддержки, можно загрузить с сайта компании Sun (http://java.sun.com/): JRE, JDK. Первое приложение JRE — это программа для запуска и исполнения программ (среда выполнения Java) Java Runtime Environment (JRE). Для разработки программ также требуется комплект разработки программного обеспечения — JDK (Java Development Kit). Он содержит компилятор, стандартные библиотеки и т.п. В настоящее время имеется три Java-платформы:
1) Java 2 Platform, Standard Edition (J2SE);
2) Java 2 Platform, Enterprise Edition (J2EE);
3) Java 2 Platform, Micro Edition (J2ME).
Каждая из этих платформ предназначена для разработки опреде- ленного типа программ. Первая платформа J2SE позволяет разрабатывать обычные (desktop) локальные приложения и апплеты. Вторая платформа J2EE предназначена для разработки серверных приложений (сервлетов, jsp-страниц, компонентов JavaBeans). Третья платформа (J2ME) применяется при разработки приложений для мобильных и небольших устройств (сотовых телефонов, карманных компьютеров и др.), которые имеют существенно ограниченные аппаратные ресурсы (емкость оперативной памяти, быстродействие процессора и др.). Таким образом, в минимальный комплект для разработки программ на Java входят следующие:
-JRE — среда выполнения;
-JDK для соответствующей платформы (J2SE, J2EE, J2ME) — компилятор и библиотеки;
-среда программирования.[7].
2.2 GUI: библиотеки и визуальные среды разработки, сравнительная характеристика
Современные программы нуждаются в графическом интерфейсе пользователя (GUI). Пользователи отвыкли работать через консоль: они управляют программой и вводят входные данные посредством так называемых элементов управления (в программировании их также называют визуальными компонентами), к которым относятся кнопки, текстовые поля, выпадающие списки и т.д.
Каждый из современных языков программирования предоставляет множество библиотек для работы со стандартным набором элементов управления. Напомним, что под библиотекой в программировании набор готовых классов и интерфейсов, предназначенных для решения определенного круга задач.
В Java есть три библиотеки визуальных компонентов для создания графического интерфейса пользователя. Самая ранняя из них называется AWT. Считается, что при ее проектировании был допущен ряд недочетов, вследствие которых с ней довольно сложно работать. Библиотека Swing разработана на базе AWT и заменяет большинство ее компонентов своими, спроектированными более тщательно и удобно. Третья, самая новая библиотека, называется SWT.
Каждая библиотека предоставляет набор классов для работы с кнопками, списками, окнами, меню и т.д., но эти классы спроектированы по-разному: они имеют различный набор методов с разными параметрами, поэтому «перевести» программу с одной библиотеки на другую (например, с целью увеличения быстродействия) не так-то просто. Это почти как перейти с одного языка программирования на другой: все языки умеют делать одно и то же, но у каждого из них свой синтаксис, своя программная структура и свои многочисленные хитрости. Рассмотрим поближе некоторые из них.[6].
Библиотека java.AWT
AWT библиотека Java позволяет создавать пользовательские интерфейсы внутри самого Java апплета. AWT библиотека содержит все необходимые элементы управления такие как кнопки, edit areas, check boxes и т.д. К тому же AWT библиотека имеет несколько различных контейнеров, которые размещаются с этими элементами управления на экране.[13].
Библиотека java.swing
Swing это набор для создания богатого графического интерфейса пользователя (GUI) для ваших Java программ и апплетов. Он может быть подключен к JDK 1.1, как отдельная часть, и вошел в состав инструментария для Java2, начиная с JDK версии 1.2 и далее. В сравнении с ранее использовавшейся библиотекой AWT, библиотека Swing имеет ряд преимуществ. Однако остановимся на следующих четырех:
- богатый набор интерфейсных примитивов
- настраивающийся внешний вид на различных платформах (look and feel)
- раздельная архитектура модель-вид (model-view)
- встроенная поддержка HTML
Библиотека java.SWT
SWT – кросс платформенная библиотека компонент для построения графического интерфейса пользователя (Graphical user interface (GUI)).
Первым Java фреймуорком для построения графического интерфейса пользователя была созданная корпорацией Sun Microsystems библиотека AWT (Abstract Windowing Toolkit).
Библиотеку SWT можно использовать не только для разработки приложений на платформе Eclipse, но также и для разработки любых других приложений. При этом можно использовать любую среду разработки Java приложений Integrated Development Enviroment (IDE), например Oracle Java Developer или Borland Java Builder. Для этого достаточно включить необходимые библиотеки SWT в состав Java приложения. Фреймуорк SWT поддерживает большинство популярных операционных систем. Так же существует возможность компиляции SWT Java приложений в нативный бинарный код, что повышает производительность созданных приложений и не требует установки Java машины - Java Runtime Enviroment (JRE). Такие приложения ничем не отличаются от нативных приложений конкретной операционной системы, а использование современных IDE позволяет быстро создавать качественные кросс платформенные продукты для различных операционных систем.[11].
Дизайнер форм WindowBuilder
Для создания пользовательского интерфейса GUI на AWT/Swing в дипломном проекте использовался дизайнер форм WindowBuilder.
WindowBuilder является одним из самых простых и функциональных дизайнеров форм для создания GUI в Java. При работе над дипломным проектом использовался именно он. Для того, чтобы использовать WindowBuilder нужно иметь на компьютере установленный JDK и установленный Eclipse. Eclipse в режиме дизайнера форм и интерфейс WindowBuilder изображен на рисунке 2.3.
Рисунок 2.3 – Eclipse в режиме дизайнера форм, интерфейс WindowBuilder
2.3 Средства языка Java для реализации алгоритмов
Java является основой практически для всех типов сетевых приложений и всеобщим стандартом для разработки и распространения встроенных и мобильных приложений, игр, веб-контента и корпоративного программного обеспечения. В мире насчитывается более 9 миллионов специалистов, разрабатывающих приложения на Java, которая позволяет эффективно разрабатывать, внедрять и использовать превосходные приложения и услуги.
От портативных компьютеров до центров сбора данных, от игровых консолей до суперкомпьютеров, используемых для научных разработок, от сотовых телефонов до сети Интернет — Java используется повсюду. Логотип Java на рисунке 2.4.
 |
̶ Java используется на 97% корпоративных настольных ПК
̶ Java используется на 89% настольных ПК в США
̶ 9 млн разработчиков на Java в мире
̶ Инструмент номер 1 среди разработчиков
̶ Программа номер 1 среди разработчиков
̶ Java используется в 3 млрд мобильных телефонов
̶ Java входит в комплект поставки 100% всех проигрывателей дисков Blu-ray
̶ Используется 5 млн Java Card
̶ Java используется в 125 млн ТВ-устройств
̶ 5 из 5 основных производителей оригинального оборудования включают в комплект поставки Java ME
Технология Java протестирована, усовершенствована, расширена и проверена участниками сообщества разработчиков Java, архитекторов и энтузиастов. Java позволяет разрабатывать высокопроизводительные портативные приложения практически на всех компьютерных платформах. Доступность приложений в разнородных средах позволяет компаниям предоставлять более широкий спектр услуг, способствует повышению производительности, уровня взаимодействия и совместной работы конечных пользователей и существенному снижению стоимости совместного владения корпоративными и потребительскими приложениями. Java стала незаменимым инструментом для разработчиков и открыла для них следующие возможности:
̶ написание программного обеспечения на одной платформе и его запуск практически на любой другой платформе
̶ создание программ, работающих в веб-браузере и имеющих доступ к веб-службам
̶ разработка приложений на стороне сервера для форумов в Интернете, магазинов, опросов, обработки форм HTML и много другого
̶ объединение приложений или служб с использованием языка Java для создания высокоспециализированных приложений или служб
̶ создание многофункциональных и эффективных приложений для мобильных телефонов, удаленных процессоров, микроконтроллеров, беспроводных модулей, датчиков, шлюзов, потребительских продуктов и практически любых других категорий электронных устройств
Во многих колледжах и университетах преподаются курсы по программированию на платформе Java. Академия Oracle предоставляет учреждениям школьного, профессионального и высшего образования полный портфель программного обеспечения, учебные курсы, хостинговые технологии, факультативное обучение, поддержку и ресурсы сертификации для использования в учебных целях, а также поддержку Java для сотен тысяч студентов. Разработчики также могут повысить свою квалификацию в области программирования на Java с помощью материалов, доступных на веб-сайте Oracle для разработчиков Java, подписки на информационные рассылки, посвященные технологии Java, использования учебных пособий по Java и центров программирования для начинающих разработчиков Java, а также участия в веб-, виртуальных или проводимых инструкторами учебных курсах и сертификациях.
 |
Java для начинающих разработчиков
Юные разработчики начинают изучать языки программирования с самого раннего возраста. С помощью визуальных инструментов обучения, таких как Alice, Greenfoot и BlueJ, новое поколение может научиться программировать на языке Java и на легких в использовании языках программирования, разработанных на основе Java.[15].
Что такое JavaFX
JavaFX работает на основе Java. На платформе JavaFX разработчики могут создавать и развертывать полнофункциональные интернет-приложения (RIA), одинаково стабильно функционирующие на различных платформах. JavaFX расширяет возможности Java, позволяя разработчикам использовать любые библиотеки Java в приложениях JavaFX. Разработчики могут расширить свои возможности в Java и воспользоваться технологией презентаций, обеспечиваемой JavaFX для создания увлекательных визуальных образов.
Основные конструкции языка Java
Авторы языка Java стремились сделать его внешне похожим на широко распространенный среди программистов язык C++. Поэтому синтаксис языка Java во многом совпадает с синтаксисом C и C++. И действительно в Java сохранена лексика и основные синтаксические конструкции C++. Как и в C++ в Java определены унарные и бинарные арифметические, логические и битовые операции, несколько операций присваивания, тренарная условная операция, явные и неявные операции приведения типов (причем все перечисленные операции имеют такие же обозначения и приоритеты, что и соответствующие операции C/C++). Как и в C++ в Java определены управляющие операторы if, if-else, break, switch, return, while, do-while, for, continue (все перечисленные операторы имеют семантику аналогичную семантике соответствующих операторов C/C++). Как и в C++ в Java определены классы, имеющие закрытую (private), ограниченно доступную (protected) и общедоступную (public) части, классы служат шаблонами для порождения объектов, для классов определено отношение наследования (правда в Java отменено множественное наследование), определены конструкторы и деструкторы, указатель this, абстрактные классы. На первый взгляд может показаться, что Java - просто еще одна версия C++.[8].
Но это впечатление неверное. Язык Java существенно отличается от C++, так как при разработке Java из C++, который был взят за основу, были исключены почти все особенности C++, имеющие корни в языке C, из которого развился C++. В результате Java оказался не очередным диалектом C++, а новым языком, который лучше C++ в основном за счет того, чего в нем нет по сравнению с C++. В отличие от C++ Java позволяет писать надежные, безопасные, простые, удобные и легкие для понимания программы, хотя и более медленные, чем программы, написанные на C++.
Что же было исключено из C++ при разработке Java? Прежде всего были исключены указатели. Указатели или адреса в памяти - наиболее мощное средство написания высокоэффективных программ в окружении C/C++, но это и наиболее опасное средство этих языков. И дело даже не в том, что, как отмечают авторы языка Java, при недостаточно аккуратном обращении с указателями могут возникать трудно устранимые ошибки в C++-программе. Более существенные трудности в работе с указателями выявляются при разработке распределенных программ, когда требуется осуществить удаленный вызов функции (метода), среди параметров которой есть указатели. Еще более существенные трудности связаны с возможностью работы с произвольными адресами памяти через бестиповые указатели, так как это позволяет полностью игнорировать защиту памяти.
В языке Java нет указателей; все объекты программы расположены в куче (heap) и доступны по объектным ссылкам, которые представляют объекты во всех структурах, в которые могут входить объекты в качестве компонентов. Поскольку при работе с кучей программист не может пользоваться взаимным расположением объектов в памяти, это решение означает, что из языка Java исключена "кусочно-линейная" модель памяти системы C/C++, при которой массив - лишь точка (ячейка) памяти, на которую ссылается указатель этого массива; конечно, это решение исключило непосредственный доступ к памяти, но оно усложнило работу с элементами массивов и, естественно, является источником более низкой эффективности Java-программ по сравнению с C++-программами. Необходимо отметить, что объектные ссылки языка Java содержат информацию о классе объектов, на которые они ссылаются, так что объектные ссылки - это не указатели, а дескрипторы объектов. Наличие дескрипторов позволяет JavaVM выполнять проверку совместности типов на фазе интерпретации кода, возбуждая исключение в случае ошибки.[14].
В Java пересмотрена и концепция C/C++ динамического распределения памяти. Исключена функция освобождения динамически выделенной памяти free(), так как работа с ней сочтена сложной и чреватой многими ошибками в программе, возможность которых уменьшает надежность C++-программ. Вместо этого в Java разработана и реализована система автоматического освобождения динамически выделенной памяти (сборщик мусора). Наличие механизма автоматической сборки мусора, естественное для интерпретируемого языка, усложняет разработку оптимизирующих компиляторов для такого языка. Тем не менее как показывает практика использования Java нужда в таких компиляторах имеется.
Стремление упростить Java-программы и сделать их более понятными привело к отказу от файлов-заголовков (h-файлов) и препроцессорной обработки. По мнению авторов Java файлы-заголовки, содержащие прототипы классов и распространяемые отдельно от двоичного кода этих классов, усложняют управление версиями, а механизм поддержки этой возможности в C/C++ помогает злонамеренным пользователям получать доступ к приватным данным объектов. В Java-программах спецификация класса и его реализация всегда содержатся в одном и том же файле. Препроцессор C/C++ с его возможностями условной компиляции дает возможность писать непонятные тексты программ, что, конечно, не очень хорошо. Но отказ от препроцессора привел к невозможности параметризации классов по типам (классам) их членов, что усложняет программирование простых вещей (например, на Java, в отличие от C++, нельзя иметь массив, элементами которого являются объекты произвольного класса). И, конечно, из Java исключен ненавидимый многими программистами-педантами оператор goto, замененный на continue и break с меткой.
Кроме того из Java исключены "дублирующие" понятия и конструкции языка C++, в частности, функции (в Java есть только методы классов), а также структуры (struct) и объединения (union) (в Java для этого используются атрибуты классов).
Необходимо также отметить, что в куче размещаются все данные Java-программы. Это означает, что хотя в Java и определены данные простых типов (byte, short, int, long, char, float, double, boolean) переменные этих типов могут быть лишь атрибутами объектов. Отсюда следует, что если нужно завести переменную, например, целого типа (int), то необходимо завести объект класса Int, который имеет один атрибут типа int и два метода - соответственно чтения значения этого атрибута и записи в него нового значения.
Таким образом, несмотря на внешнее сходство с C++, Java не просто является новым языком программирования, он настолько глубоко отличается от C++, что конвертировать разумным образом C++ - программы на язык Java (или наоборот) - очень сложная задача.
Завершая краткий обзор языка Java, рассмотрим его конструкции, которых нет в C++. Это операторы package, import, interface и implements.
Оператор package, помещаемый в начале исходного программного файла, определяет пакет, то есть область в пространстве имен классов, в которой определяются имена классов, содержащихся в этом файле; внутри указанной области пространства имен можно выделить подобласти, используя все тот же оператор package; действие оператора package аналогично действию объявления директории на имена файлов. Для обеспечения возможности использования коротких имен классов, помещенных в другие пакеты, используется оператор import. Пакет, определяемый оператором package по существу является структурной частью проектируемой программной системы, в аспекте интерфейса во многом похожей на объект, но имеющей более сложную структуру (он играет роль подсистемы). Если ввести пакеты (подсистемы) в объектно-ориентированные методологии структурного проектирования программных систем, они станут еще более мощным средством поддержки программных проектов.
Оператор interface, позаимствованный разработчиками Java из языка Objective_C (там аналогичное понятие называется протоколом), открывает определение интерфейса. Интерфейс - это набор сигнатур методов без из реализации. Каждый интерфейс может быть реализован одним или несколькими классами, при этом классы, реализующие один и тот же интерфейс, могут быть никак не связаны по иерархии наследования. Класс может реализовывать любое число интерфейсов (список интерфейсов, реализуемых некоторым классом указывается в операторе implements, дополняющим определение соответствующего класса). На множестве интерфейсов тоже определена иерархия по наследованию, но она не имеет отношения к иерархии классов. В языке Java интерфейсы обеспечивают большую часть той функциональности, которая в C++ обычно представляется с помощью механизма множественного наследования.[12].
Библиотека классов языка Java
Системная библиотека классов языка Java содержит классы и пакеты, реализующие различные базовые возможности языка. Методы классов, включенных в эту библиотеку, вызываются из JavaVM во время интерпретации Java-программы. Идея реализовывать часть языковых возможностей с помощью системных библиотек была успешно осуществлена еще в языке C и его преемнике C/C++ (откуда Java и взяла эту идею). Но если в системе программирования C/C++ нужна была известная осторожность при развитии языка с помощью библиотек, так как библиотеки вносили в язык элемент интерпретации, снижая эффективность программного кода, то в системе Java и так вся программа интерпретируется на JavaVM, так что возможности расширять язык, вводя все новые и новые классы и пакеты в системную библиотеку, практически неограничены.
Выше уже было упомянуто, что с помощью библиотечных классов Thread и ThreadGroup в Java введены легковесные процессы (трэды). Для синхронизации трэдов в Java используются мониторы Хоара, с помощью которых осуществляется синхронизация очередей (с приоритетами) к совместно используемым данным. Механизм наследования позволяет вводить в управление трэдами новые возможности: можно разработать "свои трэды", наследуясь от класса Thread.
Системная библиотека Java содержит также классы String и StringBuffer, поддерживающие работу со строками. Эти классы объявлены как final, что означает, что от этих классов нельзя производить подклассы. Класс String содержит основные операции для работы со строками (слияние строк, сравнение строк, поиск и извлечение символов и т.п.). Отметим, что операция (метод) конкатенации (слияния) строк обозначается символом "+", причем это единственный случай в языке Java, когда использована перегрузка знаков операций (в отличие от C++, широко использующем перегрузку операций +, * и др., что приводит к плохо понимаемым текстам программ, в Java запрещена перегрузка знаков операций). Класс StringBuffer является близнецом класса String, но, в отличие от класса String, объекты которого нельзя изменять (новая строка - это новый объект класса String), строки, являющиеся объектами класса StringBuffer, можно изменять.
Как и в системе программирования C/C++, в системную библиотеку Java включен пакет java.io, в котором реализованы потоки ввода-вывода. Возможности ввода-вывода в Java, в основном аналогичны реализации ввода-вывода в системе C/C++.
В системную библиотеку Java входят пакеты java.lang и java.util, которые содержат наборы вспомогательных классов, широко используемых в других встроенных пакетах Java и, естественно в прикладных пакетах и классах, разрабатываемых пользователями окружения Java. В частности, пакет java.lang содержит абстрактный класс Number, представляющий собой интерфейс для работы со всеми скалярными типами, его подклассы Integer, Long, Float и Double, являющиеся классами-оболочками для значений соответствующих типов (каждый объект класса-оболочки содержит одно значение соответствующего типа и имеет методы, обеспечивающие доступ к указанному значению), а также классы-оболочки Character и Boolean. Из других классов этих пакетов можно отметить класс Math, который содержит функции с плавающей точкой, используемые в физических и технических расчетах, а также константы E (приблизительно 2.72) и PI (приблизительно 3.14) [9].
Интеграция системы Java с сетью Internet обеспечивается пакетом java.lang, входящим в системную библиотеку Java. При этом адреса абонентов, принятые в Internet, поддерживаются классом InetAddress, для поддержки дейтаграмм (пакетов протокола UDP) используются классы DatagramPacket и DatagramSocket, класс Socket поддерживает сокеты TCP/IP, для создания серверов Internet используются объекты класса ServerSocket. Наконец, имеется класс URL для связи с WWW (пользователи WWW знают, что URL, или Uniform Resource Locators - наиболее фундаментальный компонент WWW, обеспечивающий доступ к ее содержимому; в списке литературы к данной статье URL использованы для указания источников, доступных по Internet). Сетевые классы Java представляют ясный и простой в использовании интерфейс для работы в Internet, существенно упрощая написание программ для Internet.
В системную библиотеку Java включены также классы, поддерживающие разработку апплетов и упрощающие работу с окнами. Эти классы рассматриваются в следующем разделе.
Библиотека классов Java постоянно расширяется за счет новых классов и пактов. Эти классы фактически расширяют язык Java, предоставляя программистам новые возможности. В качестве примера такого расширения Java рассмотрим два пакета, реализующие для окружения Java знаменитую библиотеку STL (Standard Template Library), которая имеет большой успех у программистов, использующих C++.
Первый из этих пакетов - SJL (Simple Java Library) представляет собой набор контейнерных классов и алгоритмов, параметризованных по типам (классам) содержащихся в них объектов и разработанных таким образом, чтобы программисты моли использовать их в различных сочетаниях в своих программах. Контейнерные классы определяют контейнерные объекты (или просто - контейнеры), т.е. объекты, которые содержат в себе наборы (множества) других объектов, обеспечивая доступ к этим объектам. Примерами контейнеров является список, массив, очередь и т.п. С каждым контейнером обычно бывает связано один или несколько итераторов - объектов, обеспечивающих доступ к содержимому соответствующего контейнера в некотором порядке. SJL обеспечивает возможности библиотеки STL для пользователей системы Java.
К сожалению, в системе Java в отличие от C++ не предусмотрено препроцессора (авторы Java являются принципиальными противниками препроцессора). Поэтому параметрические (generic) классы, реализованные в языке C++ через шаблоны (templates), обрабатываемые препроцессором, и широко используемые в библиотеке STL (ведь это библиотека шаблонов), в SJL реализованы через вызовы методов соответствующих классов. В результате во время выполнения программы приходится выполнять часть функций, которые в STL выполняются в процессе компиляции (дополнительная интерпретация!), что конечно же резко снижает производительность классов библиотеки SJL по сравнению с аналогичными классами STL.
В другой, более популярной, реализации библиотеки STL для
окружения Java - пакете JGL (Java Generic Library), разработанном под
руководством самого автора STL А. Степанова, показано как в этом окружении
можно интерпретировать параметрические (generic) классы. Для этого авторы JGL
разработали наборы интерфейсов, по одному для каждого из одиннадцати видов
контейнеров (Array,
Deque, Dlist, Slist, HashSet, OrderedSet, Stack, Queue, PriorityQueue, HashMap, OrderedMap), и контейнерные
классы, реализующие эти наборы интерфейсов. Каждый интерфейс контейнера
соответствует одному из классов объектов, содержащихся в этом контейнере, так
что как только появляется новый класс объектов, включаемых в контейнер,
соответствующий набор интерфейсов должен быть пополнен еще одним интерфейсом.
Обращение к контейнеру всегда производится через один из его интерфейсов.
Конечно, по сравнению с шаблонами такой способ параметризации классов по типам
содержащихся в них объектов выглядит несколько неуклюжим. Другим недостатком
пакета JGL является возможность включать в его контейнеры только объекты, так
что элементами контейнера "массив целых значений" будут не поля типа int, а соответствующие объекты класса Int из пакета java.lang.[6].
Из описания двух способов реализации библиотеки STL для окружения Java (SJL и JGL) видно, что язык Java нуждается в более удобных средствах параметрического (generic) программирования. Предложения по расширению Java в этом направлении встречаются в разных публикациях. Однако пока эти предложения не встречают должного понимания у авторов Java.
Программирование и использование апплетов
 |
Рисунок 2.6 - Выполнение Java-апплета
Каждый апплет выбирается на компьютер его пользователя из Web с помощью браузера (авторы системы Java изготовили для этого свой браузер HotJava, однако большинство пользователей предпочитает Netscape). После этого он загружается, верифицируется и запускается на JavaVM на компьютере пользователя, имея доступ только к JavaVM и к памяти, которую он сам занимает, как показано на рисунке 2.6. Ни к каким другим ресурсам компьютера пользователя апплет доступа не имеет, что обеспечивает защиту данных и других программ пользователя от порчи и предохраняет компьютер пользователя от заражения вирусами. Защита ресурсов компьютера, на котором выполняются апплеты, загружаемые из сети, является предметом особых забот разработчиков системы Java. Поэтому в системе поддерживается четыре уровня безопасности Java-программ (в частности, апплетов).
Первый уровень реализован в компиляторе на байткод. В отличие от традиционных компиляторов C/C++, в которых память распределяется во время компиляции, в компиляторе Java распределение памяти отложено до времени выполнения. Это, естественно, замедляет интерпретацию Java-программ, но это мешает потенциальным хаккерам взламывать систему, так как доступ к исходному коду Java-программы не дает возможности организовать несанкционированный доступ к ее памяти. Это связано и с тем, что в языке Java вместо указателей используются символические объектные ссылки в кучу, причем доступ к какому-либо объекту всегда ограничивается этим объектом.
Второй уровень защиты осуществляет верификатор байткода, который просматривает загруженный апплет перед его интерпретацией, что можно заметить из рисунка 2.6. Верификатор байткода - это несложная программа для доказательства теорем, которая проверяет загруженный байткод на удовлетворение им следующих условий (эти условия могут быть нарушены из-за неполадок в работе сети и при использовании разработчиком апплета недоброкачественного компилятора Java):
̶ байткод не выдает ссылок (указателей) на объекты, расположенные вне JavaVM;
̶ байткод не нарушает ограничений по доступу к ресурсам компьютера пользователя апплета;
̶ доступ к любым объектам апплета осуществляется в соответствии с их типом (строгая типизация);
̶ все параметры инструкций JavaVM имеют правильные типы;
̶ доступ к полям объектов апплета согласован с их определением как public, private, или protected.
Такая верификация байткода стала возможной благодаря выбранной семантической модели языка Java, принятой схеме распределения памяти и сохранению информации о типах (классах) объектов Java-программы на период ее интерпретации.
Третий уровень защиты осуществляется при динамической загрузке классов при выполнении апплета на компьютере пользователя. Во время выполнения апплета он может вызывать различные классы из локальной файловой системы, а также классы с различных серверов сети. Для обеспечения большей безопасности каждый класс, загруженный из сети, выполняется в своем отдельном пространстве имен (пакете). Для классов, загруженных из локальной файловой системы, организуется общее пространство имен. Когда класс ссылается на какой-либо другой класс, загрузчик сначала пытается разрешить ссылку в пределах локального пространства имен, а затем в остальных (внешних) пространствах имен. Поэтому ни один из локальных классов не может "испортить" какой-либо внешний класс в сети. По этой же причине локальные классы не могут ошибочно ссылаться на классы из внешних (импортированных) пространств имен.
Наконец, четвертый уровень защиты связан с такой организацией интерфейсов с сетевыми протоколами (HTTP, FTP и др.), которые обеспечивают доступ не ко всей сети, а только к тем серверам, с которых загружаются классы, используемые интерпретируемым апплетом. Кроме того, имеется возможность организовать барьер, предотвращающий доступ к ресурсам компьютера пользователя апплета со стороны сети.
Отметим, что если третий и четвертый из вышеперечисленных уровней нетрудно организовать и в системах программирования других языков, то организация первых двух уровней возможна только в системе Java, так как эти уровни основаны на свойствах языка и системы программирования Java, которых нет в других языках.
Как показали недавние всесторонние исследования по безопасности Java-апплетов, вышеописанных мер безопасности пока оказалось достаточно, чтобы обеспечить безопасное распространение и выполнение апплетов. Во всяком случае, пока не известно примеров распространения вирусов через апплеты Java, но можно найти сообщения об ошибках, обнаруженных в различных компонентах системы Java.
Однако с вирусами все обстоит не так просто. Недавно компания Symantec объявила о возможности распространения двух типов вирусов с апплетами Java:
В связи с этим разработано расширение системы Norton AntiVirus (NAV) для сканирования классов (апплетов) Java на предмет обнаружения в них вирусов. Это расширение содержит сканер файлов, содержащих Java-классы, который позволит NAV обеспечить антивирусную защиту Java-кода в режиме реального времени, и монитор антивирусной службы для Java, работающий внутри Netscape или любого другого браузера для Web, поддерживаемого системой Java. Текущая версия антивирусной службы NAV сканирует апплеты, рассылаемые по Internet в файлах .CLASS, и может обнаруживать вирусы типа Java Type I, которые могут размножаться, модифицируя страницы HTML. В следующей версии предполагается реализовать новый сканер, который сможет обнаруживать более сложные вирусы, относящиеся к типу Java Type II, которые могут заражать файлы .CLASS.
Следует отметить, что требования к обеспечению безопасности апплетов автоматически выполняются для апплетов, разрабатываемых в инструментальном окружении JDK.[13].
Инструментальное окружение JDK
Инструментальное окружение Java Developer's Kit (JDK) предназначено для разработки, отладки и модификации Java-программ (в первую очередь, апплетов). В его состав входит несколько инструментальных пакетов, в частности, пакеты java.applett и java.AWT.
Поскольку большая часть апплетов являются составными частями ("активными полями") документов, распространяемых по сети, при их программировании часто возникает необходимость обмена данными с оконными системами (графический ввод/вывод в окна). В JDK программирование работы с окнами поддерживается инструментальным средством Abstract Window Toolkit (AWT), обеспечивающим возможность писать апплеты, которые можно выполнять как с оконными редакторами ОС UNIX, так и с оконными редакторами других ОС.
Для отладки программных компонент, разрабатываемых в окружении JDK (в частности, апплетов) используется отладчик JavaDebugger (JDB). Этот отладчик поддерживает простой и удобный интерфейс с пользователем JavaDebuggerAPI, его можно использовать для отладки удаленных программ совместно с браузером HotJava, а также для отладки программ, написанных на подмножестве Java для разработки скриптов - языке JavaScript.
Для работы в операционных системах Windows 95, Windows NT, UNIX (в том числе Solaris и Linux) и Macintosh текущую версию JDK можно загрузить непосредственно с Web-сервера компании Sun по адресу java.sun.com. По этому же адресу доступен и браузер HotJava, написанный на Java, и комплект документации по системе Java. Размер дистрибутива JDK (в упакованном виде) составляет 4 - 5 мегабайт. Инструментальное окружение JDK содержит библиотечные классы и пакеты, существенно упрощающие программирование и отладку апплетов.
Проблема эффективности Java-программ.
Здесь под эффективностью имеется в виду скорость выполнения Java-программ. Поскольку Java-программы интерпретируются на JavaVM, они, естественно, выполняются медленнее, чем программы, разработанные с помощью оптимизирующих компиляторов C/C++. Измерения на бенч-марках показали, что Java-программы выполняются примерно в 30 раз медленнее C-программ на однопроцессорных компьютерах (в частности, на персональных компьютерах). На параллельных компьютерных системах разрыв достигает 50 раз. Поэтому, конечно, существует проблема повышения эффективности Java-программ. В меньшей степени эта проблема актуальна для апплетов, ведь это небольшие интерактивные программы, и скорость их выполнения в большинстве случаев удовлетворяет их пользователей.
В тех редких случаях, когда возникает потребность увеличить скорость выполнения апплета, можно воспользоваться динамическим компилятором Java (just-in-time compiler), который работает параллельно с интерпретацией апплета и переводит байткод в объектный код компьютера, на котором выполняется апплет, что отображено на рисунке 2.6. Этот объектный код оформляется как обычная подпрограмма и (после загрузки) вызывается из JavaVM (при программировании на Java разрешается использовать подпрограммы, выполняемые в объектном коде компьютера, на котором работает JavaVM (native subroutines); эти подпрограммы считаются подпрограммами самой JavaVM). Как показали измерения на бенч-марках, при этом выполнение апплета ускоряется примерно в 10 раз.
Но в окружении Java разрабатываются не только апплеты. Java - универсальный язык программирования, и его удобно использовать для написания клиентских программ, библиотек, поддерживающих пользовательские интерфейсы (особенно в тех случаях, когда они должны функционировать в неоднородной сети), прикладных пакетов и т.п. Всеобщее увлечение апплетами несколько отодвинуло на второй план эту сторону Java, но это - временное явление. Уже сейчас публикуется много работ по применениям Java, не связанным с разработкой апплетов, и число таких работ будет увеличиваться хотя бы потому, что проблема программирования и распространения апплетов во многом исчерпала себя (это должно быть видно и из данной публикации). При использовании Java для разработки более сложного программного обеспечения, чем апплеты, проблемы надежности и эффективности (производительности) Java-программ, а также проблемы, связанные с необходимостью защиты глобальной сети от вирусов, должны быть поставлены по новому.
Рассмотрим проблему производительности сравнительно крупных прикладных Java-программ. Если для большинства апплетов проблемы производительности вообще не стояло, так как для пользователей они выполнялись "мгновенно", то замедление произвольных прикладных программ почти на два порядка неизбежно приведет к отказу от их использования. Разработчики системы Java и Java-приложений хорошо понимали это с самого начала, но, как свидетельствуют их ранние публикации, они надеялись, что JavaVM настолько хороший интерпретатор, что замедление от интерпретации будет несущественным. Кроме того, они рекомендовали повышать быстродействие Java-программ путем использования высокоэффективных библиотечных подпрограмм, разработанных на C/C++ (native methods). К сожалению, как показали измерения (см. выше), их надежды оправдались лишь для небольших апплетов, которые, по существу, являются CGI-скриптами и для разработки которых достаточно примитивного подмножества Java - языка JavaScript. Когда это было осознано, стали предприниматься усилия по повышению быстродействия Java-программ.
Первым шагом в этом направлении была аппаратная разработка JavaVM, предпринятая компанией Sun, но Java-процессор не оправдал возлагавшихся на него ожиданий по резкому увеличению быстродействия Java-программ. Кроме того, если для нормального выполнения Java-программ требуется специальный процессор, то это существенно меняет статус языка Java, как универсального языка для Web, так как очевидно, что далеко не во всех узлах Web имеются Java-процессоры.
Поэтому были предприняты попытки увеличить быстродействие Java-программ с помощью оптимизирующих компиляторов, переводящих Java-программу в оптимизированный объектный код компьютера, на котором она будет выполняться. Компания JavaSoft (дочерняя компания фирмы Sun по производству программного обеспечения, связанного с Java) разработала первый динамический оптимизирующий компилятор Java (just-in-time-compiler). Этот компилятор вызывается по прагме интерпретатором Java-байткода (JavaVM) и выполняется параллельно JavaVM (на однопроцессорном компьютере - в режиме разделения времени), компилируя из переданного ему байткода оптимизированный объектный код. Параллельно с компиляцией байткода JavaVM продолжает интерпретировать его. Когда компиляция завершается, динамический загрузчик загружает полученный объектный код как подпрограмму интерпретируемого байткода, а JavaVM вызывает эту подпрограмму, как она вызвала бы любую другую объектную (native) подпрограмму интерпретируемой Java-программы, и тем самым фактически прекращает интерпретацию байткода, что схематически показано на рисунке 2.6. Динамические компиляторы Java реализованы и другими компаниями, занимающимися разработкой программного обеспечения Java. Но, как уже упоминалось, применение динамического компилятора повышает быстродействие Java-программы лишь на порядок, так что проигрыш остается весьма ощутимым.
Поэтому был предпринят еще один шаг: реализованы первые оптимизирующие компиляторы Java в объектный код различных компьютеров. При этом даже не всегда используется байткод в качестве внутреннего представления исходной Java-программы. Более того, уже предпринимаются первые попытки разработки компиляторов Java для мощных многопроцессорных компьютерных систем. Реализация таких компиляторов сделает Java вполне универсальным мощным языком программирования. Правда это поставит перед разработчиками и пользователями Java новые сложные проблемы.
Использование рефлексии при разработке Java-программ
Рефлексией называется возможность менять свойства окружения, в котором выполняется программа, и за счет этого изменить поведение самой программы. Многие объектно-ориентированные языки и их системы программирования (например, CLOS, Smalltalk и др.) являются рефлексивными, т.е. содержат языковые и системные средства, с помощью которых можно менять параметры окружения. Рефлексия очень удобна при разработке программных систем, так как сообщает им дополнительную гибкость, способность настраиваться на различные окружения, возможность взаимодействовать с программами, которые выполняются в других системах программирования.
Java с самого начала разрабатывался как рефлексивный язык. В Java определен класс Object, являющийся корнем иерархии классов по наследованию: любой класс Java наследует класс Object. В классе Object определен доступ к системной информации, которую можно использовать Java-программах. Наличие класса Object уже сообщает определенные рефлексивные свойства системе Java.
Дополнительные возможности по реализации рефлексивных Java-программ обеспечиваются пакетом JRI (Java Reflection Interface), в котором определены способы определения рефлексивной информации для классов и методов системы Java. Рефлексивная информация, связанная с некоторым классом, включает в себя описание его привилегий доступа к различным классам, их полям и методам, их суперклассам, к интерфейсам, присоединенным к этим классам, а также информацию о свойствах его полей и методов.[12].
Проблема разработки рефлексивных возможностей для объектно-ориентированных языков программирования связана с проблемой реализации возможности взаимодействия различных объектно-ориентированных окружений, т.е. с проблемой разработки ORB (Object Request Broker). Сейчас уже разработано несколько коммерческих ORB для Java. Изучение этих ORB показывает, что язык Java гораздо лучше, чем, например C++, приспособлен к рефлексивному программированию и реализации ORB. Развитие рефлексивного программирования на Java будет способствовать еще более широкому распространению системы Java. Вместе с тем Java в ее текущем состоянии имеет ряд недостатков, препятствующих ее использованию для реализации распределенных прикладных систем. Отмечены следующие недостатки Java в этом плане:
̶ Отсутствие поддержки парадигмы вызова методов клиент/сервер; окружение Java, связанное с апплетами, стремится поместить сервер (апплет) на сторону клиента, что недопустимо при работе с серьезными (не игрушечными) северами.
̶ Отсутствие распределенных служб, так как Java не является системой распределенного программирования; например, Java поддерживает верификацию апплетов на каждом отдельном компьютере сети, чтобы обеспечить безопасность в пределах этого компьютера; но такой подход имеет мало общего с глобальной службой безопасности современных распределенных систем.
̶ Отсутствие хранимых (persistent) объектов и связи с СУБД.
Отсутствие языковой поддержки управления транзакциями и их журнализацией.
Перечисленные недостатки мешают применению Java для разработки серьезных распределенных систем в рамках стандарта CORBA. В настоящее время ведутся интенсивные исследования по преодолению указанных недостатков.
В заключение хочется сказать, что Java - первая система программирования, обеспечивающая возможность разработки и выполнения программ в среде WWW. Программы, разработанные в системе Java, обладают такими свойствами как переносимость, высокая надежность, адаптируемость к новым условиям их выполнения. Java позволяет уже сейчас разрабатывать высоконадежные коммерческие прикладные системы. Эти свойства привлекают к системе Java многих программистов, и в настоящее время, несомненно, Java – одна из самых популярных систем программирования. Хочется думать, что Java будет развиваться и появятся новые технологии и подходы к применению Java в самых различных областях системного и прикладного программирования.
Часто, нужно упорядочить предметы по какому-то признаку: записать данные числа в порядке возрастания, слова — по алфавиту, людей выстроить по росту. Если можно сравнить любые два предмета из данного набора, то этот набор всегда можно упорядочить. Процесс упорядочивания информации и называют «сортировкой».
Пусть у нас есть массив, заполненный пятью числами. Любой человек взглянет и расставит их в правильном порядке. Казалось бы, не сложная задача, но для информатиков намного занимательнее вопрос, как был получен ответ. Человек, скорее всего, будет работать так. Перед глазами у него записан беспорядочный набор чисел. Если числа большие и их много, ему обязательно потребуется дополнительное запоминающее устройство, например карандаш с бумагой. Но если количество чисел перевалит за пятьдесят или сто, то человеку понадобятся иные способы решения этой задачи. В рамках дипломного проекта проводится исследование программных методов решения подобных задач и эффективность отдельно взятых алгоритмов сортировки.
Анализ работы алгоритма
Предположим, что кто-то придумал еще один алгоритм сортировки. Как сравнить его с нашим. Чем он может быть лучше или хуже? Ясно, что результаты работы обоих алгоритмов обязаны совпадать, в противном случае можно сказать, что один из них работает неправильно (неоптимально). Таким образом, алгоритмы надо сравнивать по другим параметрам. Такими параметрами, в первую очередь, являются время работы алгоритма и требуемая для его работы память.
Поскольку время работы алгоритма зависит от того, на каком языке программирования был написан код, как он был скомпилирован, на каком компьютере выполняется и т. д., то мы будем считать не время работы алгоритма, а количество операций, выполняемых алгоритмом. Наш алгоритм N-1 раз выполняет поиск минимума - в первый раз минимум ищется среди N элементов, и на это требуется порядка N операций, второй раз - среди N-1 элемента, и т. д. Таким образом, на поиск минимума всего потребуется N + (N-1) + ... + 3 + 2 = (N+2)(N-1)/2 операций, что примерно равно N2/2 операций. На перестановку минимумов на свои места требуется порядка N операций. При больших N N2/2 много больше N, поэтому операциями перестановки максимума можно пренебречь, и сказать, что наш алгоритм работает за время порядка N2/2, где N - количество чисел. Алгоритмы, которые требуют порядка CN2/2 операций (где С - некоторая константа, не зависящая от N), называют квадратичными.[7].
Сортировка выбором
Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке. Если входная последовательность почти упорядочена, то сравнений будет столько же, значит алгоритм ведет себя неестественно.
Сортировка пузырьком
Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.
Дополнительная память, очевидно, не требуется. Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного. Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает это качество.
На практике метод пузырька, даже с улучшениями, работает слишком медленно. А потому - почти не применяется.
Сортировка вставками
Сортировка простыми вставками в чем-то похожа на вышеизложенные методы.
Аналогично сортировке выбором, среднее, а также худшее число сравнений и пересылок оцениваются как O(n^2), дополнительная память при этом не используется.
Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет сортирован очень быстро. Это, вкупе с устойчивостью алгоритма, делает метод хорошим выбором в соответствующих ситуациях.
Алгоритм можно слегка улучшить. Заметим, что на каждом шаге внутреннего цикла проверяются 2 условия. Можно объединить их в одно, поставив в начало массива специальный сторожевой элемент. Он должен быть заведомо меньше всех остальных элементов массива.
Сортировка Шелла
Сортировка Шелла является довольно интересной модификацией алгоритма сортировки простыми вставками.
Часто вместо вычисления последовательности во время каждого запуска процедуры, ее значения рассчитывают заранее и записывают в таблицу, которой пользуются, выбирая начальное приращение по тому же правилу: начинаем с inc[s-1], если 3*inc[s] > size.
Сортировка шейкер
Сортировка шейкер — разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки, можно отметить два обстоятельства.
Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения.
Во-вторых, при движении от конца массива к началу минимальный элемент “всплывает” на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.
Эти две идеи приводят к следующим модификациям в методе пузырьковой сортировки. Границы рабочей части массива (т.е. части массива, где происходит движение) устанавливаются в месте последнего обмена на каждой итерации. Массив просматривается поочередно справа налево и слева направо.
Лучший случай для этой сортировки — отсортированный массив (O(n)), худший — отсортированный в обратном порядке (O(n^2)).
Пирамидальная сортировка
Пирамидальная сортировка является первым из рассматриваемых методов, быстродействие которых оценивается как O(n log n).
Построение пирамиды занимает O(n log n) операций, причем более точная оценка дает даже O(n) за счет того, что реальное время выполнения downheap зависит от высоты уже созданной части пирамиды.
Вторая фаза занимает O(n log n) времени: O(n) раз берется максимум и происходит просеивание бывшего последнего элемента. Плюсом является стабильность метода: среднее число пересылок (n log n)/2, и отклонения от этого значения сравнительно малы.
Метод не является устойчивым: по ходу работы массив так "перетряхивается", что исходный порядок элементов может измениться случайным образом.
Сортировка слиянием
Сортировка слиянием — вероятно, один из самых простых алгоритмов сортировки (среди «быстрых» алгоритмов). Особенностью этого алгоритма является то, что он работает с элементами массива преимущественно последовательно, благодаря чему именно этот алгоритм используется при сортировке в системах с различными аппаратными ограничениями (например, при сортировке данных на жёстком диске, или даже на магнитной ленте). Кроме того, сортировка слиянием — чуть ли не единственный алгоритм, который может быть эффективно использован для сортировки таких структур данных, как связанные списки. Последовательная работа с элементами массива значительно увеличивает скорость сортировки в системах с кэшированием.[15].
Сортировка слиянием — стабильный алгоритм сортировки. Это означает, что порядок «равных» элементов не изменяется в результате работы алгоритма. В некоторых задачах это свойство достаточно важно.
Этот алгоритм был предложен Джоном фон Нейманом в 1945 году
Процедура слияния требует два отсортированных массива. Заметив, что массив из одного элемента по определению является отсортированным, мы можем осуществить сортировку следующим образом:
̶ разбить имеющиеся элементы массива на пары и осуществить слияние элементов каждой пары, получив отсортированные цепочки длины 2 (кроме, быть может, одного элемента, для которого не нашлось пары);
̶ разбить имеющиеся отсортированные цепочки на пары, и осуществить слияние цепочек каждой пары;
̶ если число отсортированных цепочек больше единицы, перейти к шагу 2.
Время работы сортировки слиянием составляет O(n * ln(n)).
Сортировка расческой
Сортировка расчёской — это довольно упрощённый алгоритм сортировки, изначально спроектированный Влодзимежом Добосиевичем в 1980 г. Позднее он был переоткрыт и популяризован в статье Стивена Лэйси и Ричарда Бокса в журнале Byte Magazine в апреле 1991. Сортировка расчёской улучшает сортировку пузырьком, и конкурирует с алгоритмами, подобными быстрой сортировке. Основная идея — устранить черепах, или маленькие значения в конце списка, которые крайне замедляют сортировку пузырьком (кролики, большие значения в начале списка, не представляют проблемы для сортировки пузырьком).
В сортировке пузырьком, когда сравниваются два элемента, промежуток (расстояние друг от друга) равен 1. Основная идея сортировки расчёской в том, что этот промежуток может быть гораздо больше, чем единица (сортировка Шелла также основана на этой идее, но она является модификацией сортировки вставками, а не сортировки пузырьком).
Сортировка QuickSort
Быстрая сортировка, часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.
Один из самых быстрых известных универсальных
алгоритмов сортировки массивов: в среднем (n log n) обменов при
упорядочении 
элементов;
из-за наличия ряда недостатков на практике обычно используется с некоторыми
доработками.
QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов.
Общая идея алгоритма состоит в следующем:
Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива или же число, вычисленное на основе значений элементов; от выбора этого числа сильно зависит эффективность алгоритма.
Для реализации нужно сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующие друг за другом: «меньшие опорного», «равные» и «большие».
Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.
На практике массив обычно делят не на три, а на две части: например, «меньшие опорного» и «равные и большие»; такой подход в общем случае эффективнее, так как упрощает алгоритм разделения.
Поразрядная сортировка
Этот алгоритм существенно отличается от описанных ранее.
Во-первых, он совсем не использует сравнений сортируемых элементов.
Во-вторых, ключ, по которому происходит сортировка, необходимо разделить на
части, разряды ключа. Например, слово можно разделить по буквам, число - по
цифрам...
Каждая из сортировок по i-й цифре занимает O(N) времени. Всего сортировок конечное число, таким образом, RadixSort работает за O(N), что противоречит теореме.
На самом деле, это не так. Противоречия с теоремой нет. Мы сортируем N чисел. Допустим, они все различны, тогда длина самого большое из них должна быть не менее logN.
Отсюда следует, что на самом деле сортировок не конечное число, а О(logN), и алгоритм работает за О(NlogN).
Глупая сортировка
Простейший учебный алгоритм низкой эффективности. При минимальном изменении трансформируется в пузырьковую сортировку или гномью сортировку.
Алгоритм работы прост: просматриваем массив начиная с первого индекса, по пути сравниваем соседние элементы. Если находим неотсортированную пару — меняем местами, возвращаемся в начало массива и повторяем те же действия.
Процесс заканчивается, если во время полного прохода не обнаружено ни одной неотсортированной пары.
3.2.1 Разработка интерфейса GUI
Для разработки пользовательского интерфейса программы в дипломном проекте использовался WindowBuilder – плагин для Eclipse. WindowBuilder – визуальный дизайнер интерфейсов на Swing, GWT и SWT. Для платформы Eclipse выполнен в виде плагина. Некогда WindowBuilder принадлежал компании Instntiations, но сравнительно недавно (на момент написания статьи) компания Google выкупила часть данной компании, которая занималась Java-разработками. На данный момент WindowBuilder распространяется свободно и является оптимальным решением для создания пользовательского интерфейса GUI в рамках дипломного проекта.
Элементы управления
При создании программы «Методы сортировки» использовались разные пользовательские элементы управления. Рассмотрим подробнее каждый из них.
JFrame
Класс JFrame является расширенной версией java.awt.Frame, который добавляет поддержку для архитектуры компонентов JFC / Swing. В программе.
Для начала объявляется JFrame как глобальная переменная в основном классе программы.
private JFrame frame;
Далее в функции public static void main(String[] args) JFrame задается значение setVisible(true), что означает, что фрейм будет виден пользователю.
window.frame.setVisible(true);
Далее инициализируем JFrame в методе инициализации программных компонентов private void initialize(), указывая имя в шапке окна, размеры окна, действие при нажатии кнопки выхода, возможность свободно перемещать элементы окна в режиме конструктора форм и запрет на изменение размеров окна.
frame = new JFrame("Методы сортировки");
frame.setBounds(100, 100, 600, 600);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.getContentPane().setLayout(null);
frame.setResizable(false);
В дальнейшей инициализации любого элемента управления, находящегося непосредственно в этом окне, должна сопровождаться указанием имени фрейма для расположения.
frame.getContentPane().add(button);
JButton
Класс JButton из пакета javax.Swing является наиболее часто используемой кнопкой в языке программирования Java.
Эта кнопка может содержать пиктограмму (свойство icon), иметь акселератор (свойство mnemonic), она может быть выделенной (свойство selected), может иметь всплывающую подсказку (свойство toolTipText). Кроме того, можно выбирать выравнивание надписи на кнопке (свойства horisontalAlignment и horisontalTextPosition) и определять многие другие ее свойства. Эта кнопка находится в палитре компонентов на вкладке Swing с всплывающей подсказкой javax.swing.JButton.
В программе «Методы сортировки» кнопки объявляются и инициализируются в методе инициализации элементов управления программы private void initialize(), и сразу им задаются все нужные параметры, такие как имя кнопки, надпись на кнопке, ее размер, место расположения и слушатель, определяющий действие, при нажатии кнопки.
JButton btnNewButton = new JButton("Сортировка выбором");
btnNewButton.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
// Действие, заданное разработчиком
});
btnNewButton.setBounds(23, 189, 200, 23);
frame.getContentPane().add(btnNewButton);
JLabel
JLabel это пожалуй самый простой компонент, который есть в Java Swing. С помощью JLabel можно показать текст с иконкой. Если нужен какой-то компонент, чтобы отобразить какое-то сообщение пользователю или сделать для поля ввода текстовую метку, или показать иконку — используем JLabel. Текст, который показывает JLabel выделять нельзя, только смотреть.
В программе «Методы сортировки», JLabel объявляется и инициализируется в методе инициализации, как и элемент JButton. Сначала объявляется элемент и ему присваивается имя, а далее указывается текст, содержащийся в этом элементе, задается размер элемента и его инициализация в форме.
JLabel lblNewLabel = new JLabel("Максимальное время сортировки (сек):");
lblNewLabel.setBounds(23, 66, 244, 14);
frame.getContentPane().add(lblNewLabel);
JTextField
Текстовое поле — простой и часто используемый компонент, предназначенный для ввода небольших по объему (записываемых в одну строку) текстовых данных. Для создания текстового поля в программе «Методы сортировки», JTextField объявляется как глобальный элемент управления.
private JTextField textField;
Далее элемент инициализируется в методе private void initialize(), указывается его размер, форма, к которой он относится и количество максимально возможных цифр в поле ввода.
textField = new JTextField();
textField.setBounds(271, 31, 133, 20);
frame.getContentPane().add(textField);
textField.setColumns(10);
TextArea
TextArea это поле для ввода многострочной информации. В отличие от предыдущих элементов пользовательского интерфейса, относящихся к классу javax.Swing, TextArea представитель родительского класса java.AWT.
Для обеспечения работы этого элемента, в программе «Методы сортировки» TextArea объявляется на глобальном уровне.
private TextArea textArea;
Далее, как и все элементы TextArea инициализируется в соответствующем методе и принимает параметры цвета фона для поля ввода, его размеры, отношение к форме и отменена возможность записи в поле ввода. Этот элемент в программе «Методы сортировки» предназначен только для вывода.
textArea = new TextArea();
textArea.setBackground(Color.WHITE);
textArea.setBounds(271, 96, 303, 458);
textArea.setEditable(false);
frame.getContentPane().add(textArea);
3.2.2 Реализация методов сортировки
Алгоритмы сортировки бывают разные по сложности, по скорости работы, по количеству затрачиваемой памяти и, наконец, по самой логике алгоритмов. Но какие они не были бы разные, все алгоритмы, изученные в рамках дипломного проекта, отлично реализуются на языке программирования Java.
Все алгоритмы были реализованы через функции, которые вызываются при нажатии кнопок, соответствующих выбранному методу сортировки. При нажатии кнопки сортировки, программа считывает заданное количество элементов, создаст массив чисел и заполнит его от 1 до N, скопирует имеющийся массив, для дальнейшей сортировки одного и того же массива. Потом, если массив создан, программа запустит функцию сортировки и применит ее для созданного в памяти массива чисел. Далее, программа проверяет, сортирован ли массив и выводит результат в поле вывода TextArea.
btnNewButton.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
try {
s = textField_1.getText();
maxTime = Integer.parseInt(s);
perMass = Arrays.copyOf(mass, mass.length);
startTime = System.currentTimeMillis();
vibor(perMass);
long timeSpent = System.currentTimeMillis() - startTime;
if (proverka(perMass) == true)
textArea.append("Сортировка выбором - OK.\nВремя выполнения " + timeSpent + " миллисекунд.\n");
else
textArea.append("Сортировка - Время ожидания истекло." + "\n");
}catch (Exception ex) {JOptionPane.showMessageDialog(null, "Создайте массив и задайте время!");}
}
});
Полный код в приложении А.
Рассмотрим реализованные методы сортировок в программе «Методы сортировки», созданной в рамках дипломного проекта на языке Java, описанные подробнее в пункте 3.1.
Глупая сортировка
Далее представлена реализация конкретного алгоритма сортировки на языке Java. Полный код находится в приложении А.
public static int[] stupidSort(int[] mass) {
int temp, i = 0;
int n = mass.length - 1;
while (i < n) {
if ((time - startTime) < mTime) {
if (mass[i+1] < (mass[i])) {
temp = mass[i + 1];
mass[i + 1] = mass[i];
mass[i] = temp;
i = 0;
} else {
i++;
}
}
return mass;
}
Сортировка выбором
Далее представлена реализация конкретного алгоритма сортировки на языке Java. Полный код находится в приложении А.
private static int[] vibor(int[] mass) {
for(int i = 0; i < mass.length; i++) {
int min = mass[i];
int minI = i;
for(int j = i + 1; j < mass.length; j++) {
if(mass[j] < min) {
min = mass[j];
minI = j;
}
}
if(i != minI) {
int prom = mass[i];
mass[i] = mass[minI];
mass[minI] = prom;
}
}
return mass;
}
Сортировка пузырьком
Далее представлена реализация конкретного алгоритма сортировки на языке Java. Полный код находится в приложении А.
private static int[] puzir(int[] mass) {
for(int i = mass.length-1 ; i > 0 ; i--) {
for(int j = 0 ; j < i ; j++) {
if( mass[j] > mass[j + 1] ) {
int prom = mass[j];
mass[j] = mass[j + 1];
mass[j + 1] = prom;
}
}
}
return mass;
}
Сортировка вставками
Далее представлена реализация конкретного алгоритма сортировки на языке Java. Полный код находится в приложении А.
private static int[] vstavka(int[] mass) {
int j;
for(int i = 0; i < mass.length; i++) {
int prom = mass[i];
for(j = i - 1; j >= 0 && mass[j] > prom; j--) {
mass[j + 1] = mass[j];
}
mass[j + 1] = prom;
}
return mass;
}
Сортировка шейкер
Далее представлена реализация конкретного алгоритма сортировки на языке Java. Полный код находится в приложении А.
public static void sheker(int[] mass) {
int left = 1, right = mass.length - 1;
do{
for(int i = right; i >= left; i--) {
if(mass[i - 1] > mass[i]) {
int temp = mass[i];
mass[i] = mass[i - 1];
mass[i - 1] = temp;
}
}
left++;
for(int i = left; i <= right; i++) {
if(mass[i - 1] > mass[i]) {
int temp = mass[i];
mass[i] = mass[i - 1];
mass[i - 1] = temp;
}
}
} while(left <= right);
}
Сортировка методом Шелла
Далее представлена реализация конкретного алгоритма сортировки на языке Java. Полный код находится в приложении А.
public static void shell(int[] mass) {
int dlina = mass.length / 2;
while(dlina > 0) {
for(int i = 0; i < (mass.length - dlina); i++) {
int j = i;
while((j >= 0) && (mass[j] > mass[j + dlina])) {
int temp = mass[j];
mass[j] = mass[j + dlina];
mass[j + dlina] = temp;
j--;
}
}
dlina = dlina / 2;
}
}
Сортировка слиянием
Далее представлена реализация конкретного алгоритма сортировки на языке Java. Полный код находится в приложении А.
Эта сортировка реализована с помощью двух функций, где для начала сортировки необходимо вызвать функцию sortMerge.
public static int[] sortMerge(int[] mass) {
if(mass.length < 2)
return mass;
int m = mass.length / 2;
int[] mass1 = Arrays.copyOfRange(mass, 0, m);
int[] mass2 = Arrays.copyOfRange(mass, m, mass.length);
return merge(sortMerge(mass1), sortMerge(mass2));
}
public static int[] merge(int[] mass1, int mass2[]) {
int n = mass1.length + mass2.length;
perMass = new int[n];
int i1 = 0;
int i2 = 0;
for(int i = 0; i < n; i++) {
if(i1 == mass1.length) {
perMass[i] = mass2[i2++];
}
else if(i2 == mass2.length) {
perMass[i] = mass1[i1++];
}
else {
if(mass1[i1] < mass2[i2]) {
perMass[i] = mass1[i1++];
}
else {
perMass[i] = mass2[i2++];
}
}
}
return perMass;
}
Сортировка расческой
Далее представлена реализация конкретного алгоритма сортировки на языке Java. Полный код находится в приложении А.
public static void raschestka(int[] mass) {
int size = mass.length;
boolean swapped = true;
while (size > 1 || swapped) {
if (size > 1)
size = (int) (size / 1.247330950103979);
int i = 0;
swapped = false;
while (i + size < mass.length) {
if (mass[i] > mass[i + size]) {
int t = mass[i];
mass[i] = mass[i + size];
mass[i + size] = t;
swapped = true;
}
i++;
}
}
}
Пирамидальная сортировка
Далее представлена реализация конкретного алгоритма сортировки на языке Java. Полный код находится в приложении А.
Эта сортировка реализована с помощью шести функций, где для начала сортировки необходимо вызвать функцию piramidSort.
//функция начала работы и вызова подфункций пирамидальной сортировки
public static void piramidSort(int[] a) {
buildHeap(a);
int length = a.length - 1;
while (length > 0) {
swap(a, 0, length);
heapify(a, length, 0);
length--;
}
}
//формирование кучи для пирамидальной сортировки
private static void buildHeap(int[] a) {
for (int i = a.length / 2; i >= 0; i--) {
heapify(a, a.length, i);
}
}
//переупорядочивает поддерево кучи для пирамидальной сортировки
private static void heapify(int[] a, int length, int i) {
int l = left(i);
int r = right(i);
int largest = i;
if (l < length && a[i] < a[l]) {
largest = l;
}
if (r < length && a[largest] < a[r]) {
largest = r;
}
if (i != largest) {
swap(a, i, largest);
heapify(a, length, largest);
}
}
//Возвращает индекс правого потомка текущего узла для пирамидальной сортировки
private static int right(int i) {
return 2 * i + 1;
}
//Возвращает индекс левого потомка текущего узла для пирамидальной сортировки
private static int left(int i) {
return 2 * i + 2;
}
//Меняет местами два элемента в массиве для пирамидальной сортировки
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
Поразрядная сортировка
Далее представлена реализация конкретного алгоритма сортировки на языке Java. Полный код находится в приложении А.
public static void radixSort(int[] arr) {
int cnt[][] = new int[4][];
int b[];
int i, j;
int a_len = arr.length;
if (a_len < 2) {
return;
}
for (j = 0; j < 4; j++) {
cnt[j] = new int[257];
for (i = 0; i < 257; i++) cnt[j][i] = 0;
}
b = new int[a_len];
for (i = 0; i < a_len; i++) {
for (j = 0; j < 4; j++) {
cnt[j][1 + ((arr[i] >>> (8 * j)) & 0xff)]++;
}
}
for (j = 0; j < 4; j++) {
for (i = 1; i < 256; i++) cnt[j][i] += cnt[j][i - 1];
for (i = 0; i < a_len; i++) {
b[cnt[j][(arr[i] >>> (8 * j)) & 0xff]++] = arr[i];
}
for (i = 0; i < a_len; i++) arr[i] = b[i];
}
}
Сортировка подсчетом
Далее представлена реализация конкретного алгоритма сортировки на языке Java. Полный код находится в приложении А.
public static void countingSort(int[] mass) {
int i, j, b = 0;
int max = mass.length;
int[] c = new int[max];
for (i = 0; i < max; i++) c[i] = 0;
for (i = 0; i < mass.length; i++) {
c[mass[i]] = c[mass[i]] + 1;
b = 0;
}
for (j = 0; j < max; j++) {
for (i = 0; i < c[j]; i++) {
mass[b] = j;
b = b + 1;
}
}
}
3.2.3 Реализация ограничения по времени работы
Программа «Методы сортировки» предназначена в первую очередь для студентов, что означает, что конечный пользователь может не представлять, как на практике работают алгоритмы сортировки. Некоторые алгоритмы не предназначены для сортировки огромных массивов, а создать такой массив возможность все равно остается, и может возникнуть ситуация, когда программа может начать сортировать огромный массив медленной сортировкой, что приведет, к длительному процессу, который нельзя остановить.
Для предотвращений подобных ситуаций было установлено ограничение по времени для медленных сортировок. Рассмотрим на конкретном примере.
После создания и перемешивания массива, для продолжения работы необходимо выбрать метод сортировки. Допустим, что мы хотим выбрать метод глупой сортировки. При нажатии кнопки медленного метода сортировки, программа в первую очередь проверяет, что задано в поле максимального времени выполнения алгоритма. Если поле пусто, то начинает отрабатывать исключение и появится информационное окно, указывающее на возможную ошибку, как показано на рисунке 3.1.
 |
Если поле заполнено, то программа записывает заданное время в переменную maxTime и запускает функцию сортировки. Рассмотрим этот момент на примере кода из программы «Методы сортировки».
public void actionPerformed(ActionEvent e) {
try {
s = textField_1.getText();
maxTime = Integer.parseInt(s);
perMass = Arrays.copyOf(mass, mass.length);
startTime = System.currentTimeMillis();
stupidSort(perMass);
long timeSpent = System.currentTimeMillis() - startTime;
if (proverka(perMass) == true)
textArea.append("Глупая сортировка - OK.\nВремя выполнения " + timeSpent + " миллисекунд.\n");
else
textArea.append("Сортировка - Время ожидания истекло." + "\n");
}catch (Exception ex) {JOptionPane.showMessageDialog(null, "Создайте массив и задайте время!");}
}
Далее программа переводит секунды максимального времени в миллисекунды, проверяет функцию сортировки и при каждом прохождении цикла, сравнивает прошедшее время с максимально допустимым. Если максимальное время меньше времени работы цикла, то сортировка продолжается, иначе, остановка цикла и завершение работы функции. При подобном завершении работы программа отобразит в информационном окне «Сортировка - Время ожидания истекло», как показано на рисунке 3.2. Конструкция выглядит таким образом.
long mTime = maxTime * 1000;
//начало цикла функции сортировки
long time = System.currentTimeMillis();
if ((time - startTime) < mTime) {
//тело цикла сортировки
} else {
break;
}
Рисунок 3.2 – Время ожидания истекло
4 РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ
Программа «Методы сортировки» предназначена для учебных целей и может быть использована современными студентами и преподавателями.
Программа позволяет наглядно увидеть эффективность алгоритмов сортировки массивов на практике.
К пользователем программы предъявляется некоторый набор требований: базовые навыки владение компьютером, знание основ ОС Windows. Необходимо отметить, что программа спроектирована таким образом, что соответствует обычному системному приложению и не требует понимания механизма работы программы.
Программа не требует установки, для работы необходимо скопировать каталог с программой на жесткий диск и запустить исполняемый файл «Методы сортировки».
Для работы программы необходимо:
Обеспечить постоянный доступ к exe файлу;
Установить JDK - полноценный набор библиотек и инструментов для для создания, компилирования и дебага программ на языке Java.
4.3 Порядок и особенности работы
После запуска exe - файла, открывается окно, показанное на рисунке 4.1, с помощью которого программа выполняет все свои функции.
 |
Для продолжения работы следует:
1. Записать число количества элементов массива;
2. Нажать кнопку «Создать массив»;
3. Нажать кнопку «Перемешать»;
4. Если требуется, задать максимальное время сортировки;
5. Нажать кнопку с названием выбранной сортировки;
6. Если требуется очистить историю событий, нажать кнопку «Очистить историю».
Во время выполнения программы могут возникать ситуации, когда состояние внешних данных или компьютерной системы в целом делает дальнейшие вычисления в соответствии с базовым алгоритмом невозможными или бессмысленными. Классическим примером подобной ситуации можно считать целочисленное деление на ноль. Конечного результата у данной операции быть не может, поэтому ни дальнейшие вычисления, ни попытка использования результата деления не приведут к решению задачи. Список исключительных ситуаций приведен в таблице 4.1.
Таблица 4.1 – Исключительные ситуации
|
№ |
Некорректные действия |
Сообщение |
Пути решения |
|
1 |
При создании массива, когда поле количества элементов не заполнено. |
Введите в поле число! |
Ввести количество элементов массива. |
|
2 |
При начале перемешивания массива, когда тот не создан. |
Создайте массив! |
Создать массив. |
|
3 |
При попытке начать сортировку массива, когда тот не создан. |
Создайте массив и задайте время! |
Создать массив или заполнить поле максимального времени сортировки. |
|
4 |
При попытке начать медленную сортировку массива, когда не задано максимальное время выполнения сортировки. |
Создайте массив и задайте время! |
Создать массив или заполнить поле максимального времени сортировки. |
Для освоения программы «Методы сортировки» необходимо тщательно ознакомиться с приведённым выше руководством.
В качестве контрольного задания можно использовать следующие задания:
1) Создать массив.
2) Перемешать массив.
3) Сортировать массив.
4) Очистить историю.
5 ЭКОНОМИЧЕСКИЙ РАЗДЕЛ
По сравнению с ранее существовавшими программами , данная программа обладает следующими преимуществами: а) простой графический пользовательский интерфейс; б) отслеживается хронология действий студентов; в) производит управление работой компонентов г) позволяет вводить данные в интерактивном режиме д) обрабатывает ошибочные ситуации; е) широкие возможности настройки программы.
Общий объем разрабатываемого ПП, определяется по формуле:
(1)
где V0 – общий объем разрабатываемого ПП, усл.маш. команд;
Vi – объем i- ой функции ПП, i = 1..16,
n – общее число функций.
Данный ПП является развитием определенного параметрического ряда. Поэтому ее можно отнести по степени новизны к категории 2. Коэффициент новизны в таком случае равен 1,0
Типовые программы и ПС не используются для реализации функций разрабатываемого программного продукта. Группа сложности программного продукта минимальная. При разработке использовался объектно-ориентированный язык программирования Java .
С учетом вышеизложенных характеристик рассчитаем трудоёмкость создания данной программы.
Трудоемкость разработки ПП с учетом конкретных условий разработки определяется по формуле:
(2)
где ТУР - трудоемкость разработки ПП с учетом конкретных условий разработки;
ТБ - базовая трудоемкость разработки ПП, учитывающая объем ПП и группу сложности, чел. - дни;
КУР – поправочный коэффициент, учитывающий характер среды разработки и средства разработки ПП
Общая трудоемкость разработки ПП определяется по формуле
где То – общая трудоемкость разработки ПП, чел. - дни;
ТУР - трудоемкость разработки ПП с учетом конкретных условий разработки, чел. -дни.
Коэффициент сложности ПП, определяется по формуле:
(4)
где КСЛ – коэффициент сложности ПП;
Ki – коэффициенты повышения сложности ПП, i = 1..7, зависящий от наличия у разрабатываемой системы характеристик, повышающих сложность ПП и от количества характеристик ПП
Определим трудоемкость каждого этапа разработки:
(5)
где Тi – трудоемкость i – ой стадии разработки, (чел.-дни);
Li – удельный вес трудоемкости i – ой
стадии разработки ПП, учитывающий наличие той или иной стадии, причем 
.
КН – поправочный коэффициент, учитывающий степень новизны ПП и использование при разработке ПП новых типов ЭВМ и ОС
КТ – поправочный коэффициент, учитывающий степень использования в разработке (типовых) стандартных ПП
Общая трудоемкость разработки ПП рассчитывается по формуле
(6)
где ТОБЩ - общая трудоемкость разработки ПП, (чел. - дни);
Тi – трудоемкость i – ой стадии разработки ПП, (чел. - дни), i = 1..5;
n – количество стадий разработки ПП.
Расчет трудоемкости разработки программного продукта изображен в таблице 5.1.
Таблица 5.1 – Расчет трудоемкости разработки программного продукта
|
Стадия разработки |
Трудоемкость, чел-час |
Удельный вес, к.-т |
|
Техническое задание |
4,5 |
0,06 |
|
Эскизный проект |
15 |
0,18 |
|
Технический проект |
16,5 |
0,20 |
|
Продолжение Таблица 5.1 |
||
|
Рабочий проект |
38,2 |
0,47 |
|
Внедрение |
7,5 |
0,09 |
|
Итого |
81,7 |
1 |
Для расчета оплаты труда разработчика программного продукта используем среднее значение оплаты труда программистов по региону. Средний оклад программиста составляет 20000руб. Средний фонд рабочего времени в месяц 20,6 дн.
Определим заработную плату разработчика программного продукта:
Цена на научно-техническую продукцию устанавливается на этапе технического задания до начала проведения исследований. Рассчитаем расходы на материалы и покупные изделия (рассчитывается по нормам расхода материалов методом прямого счета), расчет произведем в таблице 5.2. Норму транспортно-заготовительных расходов примем равной 10%.
Таблица 5.2 - Расчет затрат на материалы и покупные изделия
|
Наименование материала |
Цена за единицу, р. |
Норма расхода, шт. |
Стоимость, р. |
|
Бумага А4 |
0,5 |
400 |
200 |
|
Диски CD-R |
10 |
10 |
100 |
|
Тонер черный |
100 |
2 |
200 |
|
Итого |
- |
- |
500 |
|
Продолжение Таблица 5.2 |
|||
|
Транспортно-заготовительные расходы (10-15%) |
- |
- |
50 |
|
Всего |
|
|
550 |
Рассчитаем затраты на специальное оборудование для научных и экспериментальных работ (затраты на приобретение и установку оборудования для автоматизации разработки ПП, в том числе стоимость машинного времени работы на ЭВМ, принтерах, сканерах и пр.) в таблице 5.3.
Таблица 5.3 – Расчет затрат на амортизацию основных фондов
|
Наименование |
Количество, шт |
Первоначальная стоимость, руб |
На, % |
А за период, руб. |
|
Компьютер |
1 |
25000 |
25 |
6250 |
|
Принтер ч/б |
1 |
5000 |
20 |
1000 |
|
Принтер цвет |
1 |
10000 |
20 |
2000 |
|
Сканер |
1 |
3000 |
20 |
600 |
|
Итого |
|
43000 |
9850 |
Расчет затрат на эксплуатацию специального оборудования
Основная заработная плата работников, обеспечивающих функционирование ПЭВМ, в том числе:
инженера - электроника;
системного программиста;
оператора.
Затраты на электроэнергию, в том числе
- затраты на силовую электроэнергию;
где 
- затраты на силовую
электроэнергию, руб.;
FЭФ. - эффективный годовой фонд времени работы ПЭВМ, час.;
Цэ - стоимость электроэнергии на момент выполнения плановых расчетов, р./кВт-ч;
РЭВМ - суммарная мощность ПЭВМ с периферией (0,7 – 1,2 кВт/часа в зависимости от периферии), кВт.
где FНОМ – номинальный фонд времени работы оборудования за рассчитываемый период, час.;
КСМ – число рабочих смен в сутки;
a- процент плановых потерь рабочего времени (20%);
где tСМ – длительность рабочей смены, час.;
DР- количество рабочих дней в плановом периоде;
tП – продолжительность нерабочего времени в предпраздничные дни, час.;
DП – количество предпраздничных дней в плановом периоде.
затрат на электроэнергию, идущей на освещение
где 
- затраты на силовую
электроэнергию, руб;
FЭФ. - эффективный годовой фонд времени работы ПЭВМ, мин;
Цэ - стоимость электроэнергии на момент выполнения плановых расчетов, р./кВт-ч;
РОСВ - суммарная мощность, которая идет на освещение,2100 кВт.
Расходы на профилактику оборудования
где ЦОБ - балансовая стоимость одной ПЭВМ с периферией.
НПРОФ – процент расходов на профилактику, (2-4%).
Прочие производственные расходы
где 
- основная заработная
плата работников, обеспечивающих функционирование ПЭВМ;
НПР – процент прочих производственных расходов (30%).
Годовые расходы на содержание и эксплуатацию одной ПЭВМ составят:
Стоимость одного машино-часа работы ПЭВМ
где РЭС - годовые расходы на содержание и эксплуатацию 1-ой ПЭВМ;
FЭФ. - эффективный годовой фонд времени работы ПЭВМ, мин.
Расчет расходов на содержание и эксплуатацию ПЭВМ, относящихся к данному программному продукту:
Расчет затрат на эксплуатацию специального оборудования указан в таблице 5.4.
Таблица 5.4 - Расчет затрат на эксплуатацию специального оборудования
|
Показатель |
Значение |
|
1 Основная заработная плата работников, обеспечивающих функционирование ПЭВМ, в том числе: - инженера – электроника; - системного программиста; - оператора. |
99692
38215 18277 43200 |
|
2 Основная заработная плата административного персонала |
48000 |
|
3 Основная заработная плата вспомогательного персонала |
67500
|
|
Продолжение Таблица 5.4 |
|
|
4 Общая основная заработная плата работников, обеспечивающих функционирование ПЭВМ, административного и вспомогательного персонала |
215192 |
|
5 Дополнительная заработная работников, обеспечивающих функционирование ПЭВМ, административного и вспомогательного персонала |
21519 |
|
6 Отчисления единого социального налога работников, обеспечивающих функционирование ПЭВМ, административного и вспомогательного персонала |
71013 |
|
7 Амортизационные отчисления с оборудования |
9850 |
|
8 Затраты на электроэнергию, в том числе: - затраты на силовую электроэнергию; - затраты на электроэнергию, идущей на освещение. |
3158 6300 |
9 Общие затраты на электроэнергию |
9458 |
|
10 Расходы на профилактику оборудования |
860 |
|
11 Прочие производственные расходы |
29907 |
|
12 Годовые расходы на содержание и эксплуатацию одной ПЭВМ |
158299 |
|
13 Стоимость одного машино-часа работы ПЭВМ |
105,3 |
|
14 Расчет расходов на содержание и эксплуатацию ПЭВМ, относящихся к данному программному продукту |
8603 |
Расчет сметной стоимости и договорной цены разработки ПП осуществляется в таблице 5.5.
Таблица 5.5 - Расчет сметной стоимости и договорной цены разработки ПП
|
Наименование статьи затрат |
Сумма, р. |
|
1 |
2 |
|
1 Материалы и покупные изделия |
550 |
|
2 Расходы на содержание и эксплуатацию оборудования |
8603 |
|
3 Основная заработная плата исполнителей |
79320 |
|
4 Дополнительная заработная плата исполнителей (10%) |
7932 |
|
5 Взносы на обязательное страхование (30%) |
26176 |
|
6 Накладные расходы (120%) |
95184 |
|
7 Сметная стоимость разработки ПП |
209833 |
На основе данных о затратах на разработку и результатах прогнозирования объема продаж, следует определить стоимость одного комплекта программного обеспечения. Предполагается что объем реализации составит 10 шт
Стоимость выставляемого на рынок ПП определяется частью стоимости разработки ПП и прибыли организации-разработчика.
Рассчитаем стоимость ПП
руб
Частичная стоимость разработки, приходящаяся на каждый комплект ПП, определяется исходя из данных о планируемом объеме установок
Процент прибыли от одной реализации ПП
Сумма прибыли от продажи каждой установки ПП
руб
Техническая прогрессивность измеряемых показателей характеризуется коэффициентом технической прогрессивности (kТП). Расчет этого коэффициента осуществляется путем сравнения технического уровня товара-конкурента и разрабатываемого ПП по отношению к эталонному уровню ПП данного направления.
Анализируемый ПП технически прогрессивен, если КТП > 1.
В качестве эталона будет выступать ПП со следующими параметрами: объем памяти – 400 Мбайт, время обработки данных – 0,1 с, надежность – 1.
Товар-конкурент имеет следующие показатели:
1. Объем памяти – 450 Мбайт;
2. Время обработки данных – 0,6 с;
3. Время выполнения типовой операции – 3 мин;
4. Надежность – 2;
5. Срок службы – 4 года;
6. Договорная цена – 32000 р.
Результаты расчетов следует свести в таблицу 5.6.
Таблица 5.6 – Расчет коэффициента технической прогрессивности разрабатываемого ПП
|
Наименование параметра |
Вес, b |
Значение параметра |
|
|
|
|
||
|
ПЭ |
ПБ |
ПН |
||||||
|
0,2 |
400 |
450 |
415 |
0,9 |
0,96 |
0,17 |
0,19 |
|
2. Время обработки данных,с |
0,3 |
0,1 |
0,6 |
0,3 |
0,2 |
0,3 |
0,1 |
0,1 |
|
3. Количество отказов |
0,5 |
1 |
2 |
1 |
0,5 |
1,0 |
0,3 |
0,5 |
|
Продолжение Таблица 5.6 |
||||||||
|
Итого |
1,0 |
- |
- |
- |
- |
- |
0,57 |
0,79 |
Расчет коэффициента технической прогрессивности
Полученное значение коэффициента технической прогрессивности больше единицы, следовательно, разработанный ПП является технически прогрессивным.
Функциональные возможности нового ПП лучше чем у базового, если kФВ > 1. Результаты расчетов сведем в таблицу 5.7.
Таблица 5.7 - Расчет коэффициента изменения функциональных возможностей разрабатываемого ПП
|
Неизмеряемые параметры |
Балльная оценка |
|
|
базовое |
новое |
|
|
Объем памяти |
3 |
4 |
|
Функциональные возможности |
4 |
5 |
|
Быстродействие |
3 |
4 |
|
Удобство интерфейса |
4 |
5 |
|
Степень утомляемости |
2 |
3 |
|
Производительность труда |
3 |
4 |
|
Итого |
19 |
25 |
Коэффициент изменения функциональных возможностей рассчитывается по формуле
Коэффициент функциональных возможностей превышает единицу, то есть новый ПП превосходит по своим функциональным возможностям базовый в 1,3 раза.
Рассчитаем коэффициент цены потребления (kЦП) , коэффициент цены потребления вычисляется как отношение договорной цены нового ПП к договорной цене базового, то есть
Экономические параметры разрабатываемого ПП лучше чем у базового, если КЦП < 1.
В целом конкурентоспособность нового ПП по отношению к базовому можно оценить с помощью интегрального коэффициента конкурентоспособности (Ки), учитывающего все ранее рассчитанные параметры
(1.41)
Анализируемое изделие будет конкурентоспособно, если КИ >1.
КИ>1, значит новый ПП более конкурентоспособный, чем базовый ПП.
При создании программного продукта важнейшей задачей является максимизация экономической эффективности функционирования. Этой цели можно добиться прежде всего выбором методов управления и обработки информации, обеспечивающих экстремальное значение функциональных критериев качества. Абсолютное значение экономической эффективности не полностью характеризует качество, так как не учтены усилия, при которых достигается заданная эффективность. Динамику совершенствования программ более полно характеризует величина экономической эффективности, отнесенная к совокупным затратам, при которых она достигнута. Этот показатель позволяет учитывать прирост эффективности на единицу затрат и при больших затратах ограничивать качество программных средств.
Многие виды программ невозможно или очень трудно характеризовать доходом от их функционирования или непосредственной экономической эффективностью. В таких случаях при анализе качества программных средств невозможно оценивать изменение эффективности в зависимости от затрат и целесообразно из анализа исключать характеристики полной экономической эффективности и сопутствующие ей функциональные критерии качества. Тогда исследование эффективности создания комплекса программ можно проводить, минимизируя затраты в предположении, что обеспечены заданные функциональные характеристики и полная идеальная эффективность.
Показатель эффекта определяет все позитивные результаты, достигаемые при использовании ПП.
Годовой экономический эффект от производства нового ПП определяется по разности приведенных затрат на базовый и новый варианты в расчете на годовой объем выпуска:
,
где Э – годовой экономический эффект от производства ПП, р; З1, З2 – приведенные затраты на единицу выпуска ПП по базовому и новому вариантам, р; А2 – годовой объем выпуска в расчетном году, ед (для разрабатываемого ПП равен 1).
Приведенные затраты при производстве ПП представляют собой сумму текущих затрат (себестоимости) на выпуск ПП и капитальных (единовременных) вложений в ПП, вычисляемую по формуле
,
где Зi – удельные приведенные затраты на производство ПП, р; Сi – удельные текущие затраты (себестоимость) на производство ПП, р; Кр – удельные капитальные вложения в ПП, р; Ен – нормативный коэффициент эффективности капитальных вложений (0,15).
Себестоимость базового программного продукта 278260руб., по проекту – 209833руб.
Срок окупаемости проекта
Т ок=43000/68427=0,62 (года)
Сумма годового экономического эффекта
Э=68427-0,15*43000=61977 руб.
По результатам расчета необходимо сделать выводы об экономической эффективности внедрения разрабатываемого ПП.
Ранее рассчитанные показатели необходимо свести в таблицу 5.8, проанализировать ее и сделать окончательные выводы о перспективах разработки, реализации и эксплуатации нового ПП по совокупности показателей.
Таблица 5.8 - Технико-экономические показатели разработки и эксплуатации ПП
|
Показатели |
Значение |
||
|
Базовый ПП |
Новый ПП |
||
|
1 |
2 |
3 |
|
|
1 Затраты на разработку, р. |
278260 |
209833 |
|
|
2 Продажная цена ПП, р. |
32000 |
29670 |
|
|
3 Интегральный коэффициент конкурентоспособности ПП, к-т |
1,96 |
|
|
|
4 Экономический эффект от производства ПП за расчётный период |
68427 |
|
|
|
5 Сумма годового экономического эффекта |
61977 |
|
|
|
Продолжение Таблица 5.8 |
|
|
6 Расчетный срок окупаемости капвложений, лет |
0,62 |
Основной целью данного дипломного проекта была исследовательская работа по темам алгоритмы сортировки и реализация их на языке программирования Java.
У языка Java есть много преимуществ перед другими языками программирования, что позволяет решать с его помощью практически любые задачи.
Ниже перечислены основные преимущества Java:
· Язык Java прост для изучения.
При разработке Java было уделено большое внимание простоте языка, поэтому программы на Java, по сравнению с программами на других языках, проще писать, компилировать, отлаживать и изучать.
· Java - это объектно-ориентированный язык.
Это позволяет создавать модульные программы, исходный код которых может использоваться многократно.
· Язык Java не зависит от платформы.
Одним из основных преимуществ языка Java является возможность переноса программ из одной системы в другую. Поскольку программы на Java не зависят от платформы как на уровне исходного кода, так и на двоичном уровне, их можно запускать в различных системах, что особенно важно для программ, предназначенных для World Wide Web.
Широкие возможности Java, простота применения, независимость от платформы и встроенные функции защиты делают этот язык программирования одним из лучших для создания приложений для Internet и desktop приложений. Я думаю, что получение мной навыков программирования на этом языке в рамках дипломного проекта значительно повысит мою востребованность на рынке труда.
Что касается алгоритмов сортировки массивов, после окончания работы над техническим заданием можно смело сказать, что все алгоритмы отлично реализуемы на языке Java.
Мною были все цели дипломного проекта:
· Проведена огромная исследовательская работа по изучены алгоритмов сортировки массивов разной сложности.
· Возможности реализации на Java алгоритмов сортировки были найдены.
· Удалось реализовать алгоритмы сортировки массивов на языке Java и обеспечить быструю и стабильную работу.
· Разработана программа для сортировки массива различными методами и вывода времени сортировок.
В результате проделанной работы, программа «Методы сортировки» окончена, и готова к массовому внедрению в учебные заведения.
Исходя из вышесказанного следует то, что в дипломной работе, все поставленные задачи полностью выполнены.
СПИСОК ИСПОЛЬЗОВАНЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ
1 ГОСТ Р ИСО 9001 Системы менеджмента качества. Требования.
2 ГОСТ Р ИСО/МЭК 15408 — Общие критерии оценки безопасности информационных технологий.
3 ГОСТ 2.104-68 ЕСКД Основные надписи.
4 ГОСТ 2.105-95 ЕСКД Общие требования к текстовым документам.
5 ГОСТ 7.32-81 СИБИД Отчет о научно-исследовательской работе. Общие требования и правила оформления.
6 Брюсь Эккель «Философия Java» — СПб.: Питер, 2014. — 207 с.: ил.
7 Герберт Шилдт «Java. Руководство для начинающих» — СПб.: Питер, 2012. — 304 с.: ил.
8 Джошуа Блох. «Java. Эффективное программирование» » — СПб.: Стандартинформ, 2014. — 207 с.: ил.
9 Кен Арнолд, Джеймс Гослинг, Дэвид Холмс «Язык программирования Java» — СПб.: Питер, 2014. -288 с.: ил. -(Серия «В цвете»).
10 Кея Хорстманна «Java 2» 2- е изд . — СПб.: Стандартинформ, 2011. — 288 с.: ил.
11 http://www.tutorialspoint.com/swing/
12 http://berdaflex.com/ru/eclipse/books/eclipse_swt/ch01s01.html
13 http://math.sgu.ru/sites/chairs/prinf/materials/java/lesson8.htm
14 http://www.javaportal.ru/java/articles/GUISwing.html
15 https://java.com/ru/about/
При создании программы через среду разработки Eclipse программный код имеет такой вид:
import java.awt.EventQueue;
import javax.swing.JFrame;
import javax.swing.JButton;
import javax.swing.JOptionPane;
import javax.swing.JTextField;
import java.awt.event.ActionListener;
import java.awt.event.ActionEvent;
import java.util.Arrays;
import java.util.Random;
import javax.swing.JLabel;
import java.awt.TextArea;
import java.awt.Color;
public class Wind {
private JFrame frame;
private JTextField textField, textField_1;
private TextArea textArea;
static int[] mass, perMass;
String s;
static int maxTime, size;
static long startTime;
//сортировка подсчетом
public static void countingSort(int[] mass) {
int i, j, b = 0;
int max = mass.length;
int[] c = new int[max];
for (i = 0; i < max; i++) c[i] = 0;
for (i = 0; i < mass.length; i++) {
c[mass[i]] = c[mass[i]] + 1;
b = 0;
}
for (j = 0; j < max; j++) {
for (i = 0; i < c[j]; i++) {
mass[b] = j;
b = b + 1;
}
}
}
//поразрядная сортировка
public static void radixSort(int[] arr) {
int cnt[][] = new int[4][];
int b[];
int i, j;
int a_len = arr.length;
if (a_len < 2) {
return;
}
for (j = 0; j < 4; j++) {
cnt[j] = new int[257];
for (i = 0; i < 257; i++) cnt[j][i] = 0;
}
b = new int[a_len];
for (i = 0; i < a_len; i++) {
for (j = 0; j < 4; j++) {
cnt[j][1 + ((arr[i] >>> (8 * j)) & 0xff)]++;
}
}
for (j = 0; j < 4; j++) {
for (i = 1; i < 256; i++) cnt[j][i] += cnt[j][i - 1];
for (i = 0; i < a_len; i++) {
b[cnt[j][(arr[i] >>> (8 * j)) & 0xff]++] = arr[i];
}
for (i = 0; i < a_len; i++) arr[i] = b[i];
}
}
//функция начала работы и вызова подфункций пирамидальной сортировки
public static void piramidSort(int[] a) {
buildHeap(a);
int length = a.length - 1;
while (length > 0) {
swap(a, 0, length);
heapify(a, length, 0);
length--;
}
}
//формирование кучи для пирамидальной сортировки
private static void buildHeap(int[] a) {
for (int i = a.length / 2; i >= 0; i--) {
heapify(a, a.length, i);
}
}
//переупорядочивает поддерево кучи для пирамидальной сортировки
private static void heapify(int[] a, int length, int i) {
int l = left(i);
int r = right(i);
int largest = i;
if (l < length && a[i] < a[l]) {
largest = l;
}
if (r < length && a[largest] < a[r]) {
largest = r;
}
if (i != largest) {
swap(a, i, largest);
heapify(a, length, largest);
}
}
//Возвращает индекс правого потомка текущего узла для пирамидальной сортировки
private static int right(int i) {
return 2 * i + 1;
}
//Возвращает индекс левого потомка текущего узла для пирамидальной сортировки
private static int left(int i) {
return 2 * i + 2;
}
//Меняет местами два элемента в массиве для пирамидальной сортировки
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
//глупая сортировка
public static int[] stupidSort(int[] mass) {
int temp, i = 0;
int n = mass.length - 1;
long mTime = maxTime * 1000;
while (i < n) {
long time = System.currentTimeMillis();
if ((time - startTime) < mTime) {
if (mass[i+1] < (mass[i])) {
temp = mass[i + 1];
mass[i + 1] = mass[i];
mass[i] = temp;
i = 0;
} else {
i++;
}
} else {
break;
}
}
return mass;
}
//сортировка расчесткой
public static void raschestka(int[] mass) {
int size = mass.length;
boolean swapped = true;
while (size > 1 || swapped) {
if (size > 1)
size = (int) (size / 1.247330950103979);
int i = 0;
swapped = false;
while (i + size < mass.length) {
if (mass[i] > mass[i + size]) {
int t = mass[i];
mass[i] = mass[i + size];
mass[i + size] = t;
swapped = true;
}
i++;
}
}
}
//рекурсивная функция сортировки частей массива для сортировки слиянием
public static int[] sortMerge(int[] mass) {
if(mass.length < 2)
return mass;
int m = mass.length / 2;
int[] mass1 = Arrays.copyOfRange(mass, 0, m);
int[] mass2 = Arrays.copyOfRange(mass, m, mass.length);
return merge(sortMerge(mass1), sortMerge(mass2));
}
//слияние двух массивов в один отсортированный для сортировки слиянием
public static int[] merge(int[] mass1, int mass2[]) {
int n = mass1.length + mass2.length;
perMass = new int[n];
int i1 = 0;
int i2 = 0;
for(int i = 0; i < n; i++) {
if(i1 == mass1.length) {
perMass[i] = mass2[i2++];
}
else if(i2 == mass2.length) {
perMass[i] = mass1[i1++];
}
else {
if(mass1[i1] < mass2[i2]) {
perMass[i] = mass1[i1++];
}
else {
perMass[i] = mass2[i2++];
}
}
}
return perMass;
}
//функция проверки упорядоченности массива
private static boolean proverka (int[] mass) {
boolean a = true;
for(int i = 0; i < mass.length; i++) {
if(mass[i] != i)
a = false;
}
return a;
}
//сортировка выбором
private static int[] vibor(int[] mass) {
long mTime = maxTime * 1000;
for(int i = 0; i < mass.length; i++) {
long time = System.currentTimeMillis();
if ((time - startTime) < mTime) {
int min = mass[i];
int minI = i;
for(int j = i + 1; j < mass.length; j++) {
if(mass[j] < min) {
min = mass[j];
minI = j;
}
}
if(i != minI) {
int prom = mass[i];
mass[i] = mass[minI];
mass[minI] = prom;
}
} else {
break;
}
}
return mass;
}
//сортировка пузырьком
private static int[] puzir(int[] mass) {
long mTime = maxTime * 1000;
for(int i = mass.length-1 ; i > 0 ; i--) {
long time = System.currentTimeMillis();
if ((time - startTime) < mTime) {
for(int j = 0 ; j < i ; j++) {
if( mass[j] > mass[j + 1] ) {
int prom = mass[j];
mass[j] = mass[j + 1];
mass[j + 1] = prom;
}
}
} else {
break;
}
}
return mass;
}
//сортировка вставками
private static int[] vstavka(int[] mass) {
int j;
long mTime = maxTime * 1000;
for(int i = 0; i < mass.length; i++) {
long time = System.currentTimeMillis();
if ((time - startTime) < mTime) {
int prom = mass[i];
for(j = i - 1; j >= 0 && mass[j] > prom; j--) {
mass[j + 1] = mass[j];
}
mass[j + 1] = prom;
} else {
break;
}
}
return mass;
}
//функция перемешивания
public static void mix(int[] a) {
Random rnd = new Random();
for (int i = 1; i < a.length; i++) {
int j = rnd.nextInt(i);
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
//сортировка шейкер
public static void sheker(int[] mass) {
long mTime = maxTime * 1000;
int left = 1, right = mass.length - 1;
do{
long time = System.currentTimeMillis();
if ((time - startTime) < mTime) {
for(int i = right; i >= left; i--) {
if(mass[i - 1] > mass[i]) {
int temp = mass[i];
mass[i] = mass[i - 1];
mass[i - 1] = temp;
}
}
left++;
for(int i = left; i <= right; i++) {
if(mass[i - 1] > mass[i]) {
int temp = mass[i];
mass[i] = mass[i - 1];
mass[i - 1] = temp;
}
}
} else {
break;
}
} while(left <= right);
}
//сортировка методом Шелла
public static void shell(int[] mass) {
long mTime = maxTime * 1000;
int dlina = mass.length / 2;
while(dlina > 0) {
for(int i = 0; i < (mass.length - dlina); i++) {
long time = System.currentTimeMillis();
if ((time - startTime) < mTime) {
int j = i;
while((j >= 0) && (mass[j] > mass[j + dlina])) {
int temp = mass[j];
mass[j] = mass[j + dlina];
mass[j + dlina] = temp;
j--;
}
} else {
break;
}
}
dlina = dlina / 2;
}
}
public static void main(String[] args) {
EventQueue.invokeLater(new Runnable() {
public void run() {
try {
Wind window = new Wind();
window.frame.setVisible(true);
} catch (Exception e) {
e.printStackTrace();
}
}
});
}
public Wind() {
initialize();
}
private void initialize() {
frame = new JFrame("Методы сортировки");
frame.setBounds(100, 100, 600, 600);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.getContentPane().setLayout(null);
frame.setResizable(false);
JButton button = new JButton("Создать массив");
button.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
try{
s = textField.getText();
size = Integer.parseInt(s);
mass = new int[size];
for (int i = 0; i < size; i++){
mass[i] = i;
}
textArea.append("Создание массива - OK." + "\n");
}catch (Exception ex) {JOptionPane.showMessageDialog(null, "Введите в поле число!");}
}
});
button.setBounds(419, 30, 155, 23);
frame.getContentPane().add(button);
JButton btnNewButton = new JButton("Сортировка выбором");
btnNewButton.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
try {
s = textField_1.getText();
maxTime = Integer.parseInt(s);
perMass = Arrays.copyOf(mass, mass.length);
startTime = System.currentTimeMillis();
vibor(perMass);
long timeSpent = System.currentTimeMillis() - startTime;
if (proverka(perMass) == true)
textArea.append("Сортировка выбором - OK.\nВремя выполнения " + timeSpent + " миллисекунд.\n");
else
textArea.append("Сортировка - Время ожидания истекло." + "\n");
}catch (Exception ex) {JOptionPane.showMessageDialog(null, "Создайте массив и задайте время!");}
}
});
btnNewButton.setBounds(23, 189, 200, 23);
frame.getContentPane().add(btnNewButton);
JButton btnNewButton_1 = new JButton("Сортировка пузырьком");
btnNewButton_1.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
try {
s = textField_1.getText();
maxTime = Integer.parseInt(s);
perMass = Arrays.copyOf(mass, mass.length);
startTime = System.currentTimeMillis();
puzir(perMass);
long timeSpent = System.currentTimeMillis() - startTime;
if (proverka(perMass) == true)
textArea.append("Сортировка пузырьком - OK.\nВремя выполнения " + timeSpent + " миллисекунд.\n");
else
textArea.append("Сортировка - Время ожидания истекло." + "\n");
}catch (Exception ex) {JOptionPane.showMessageDialog(null, "Создайте массив и задайте время!");}
}
});
btnNewButton_1.setBounds(23, 223, 200, 23);
frame.getContentPane().add(btnNewButton_1);
JButton btnNewButton_2 = new JButton("Сортировка вставками");
btnNewButton_2.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
try {
s = textField_1.getText();
maxTime = Integer.parseInt(s);
perMass = Arrays.copyOf(mass, mass.length);
startTime = System.currentTimeMillis();
vstavka(perMass);
long timeSpent = System.currentTimeMillis() - startTime;
if (proverka(perMass) == true)
textArea.append("Сортировка вставками - OK.\nВремя выполнения " + timeSpent + " миллисекунд.\n");
else
textArea.append("Сортировка - Время ожидания истекло." + "\n");
}catch (Exception ex) {JOptionPane.showMessageDialog(null, "Создайте массив и задайте время!");}
}
});
btnNewButton_2.setBounds(23, 291, 200, 23);
frame.getContentPane().add(btnNewButton_2);
JButton btnNewButton_3 = new JButton("Сортировка QuickSort");
btnNewButton_3.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
try {
perMass = Arrays.copyOf(mass, mass.length);
startTime = System.currentTimeMillis();
Arrays.sort(perMass);
long timeSpent = System.currentTimeMillis() - startTime;
if (proverka(perMass) == true)
textArea.append("Сортировка QuickSort - OK.\nВремя выполнения " + timeSpent + " миллисекунд.\n");
else
textArea.append("Сортировка - Fail!." + "\n");
}catch (Exception ex) {JOptionPane.showMessageDialog(null, "Создайте массив!");}
}
});
btnNewButton_3.setBounds(23, 531, 200, 23);
frame.getContentPane().add(btnNewButton_3);
textField = new JTextField();
textField.setBounds(271, 31, 133, 20);
frame.getContentPane().add(textField);
textField.setColumns(10);
JButton button_1 = new JButton("Перемешать");
button_1.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
try {
mix(mass);
if (proverka(mass) == false)
textArea.append("Перемешивание - OK." + "\n");
else
textArea.append("Перемешивание - Fail!" + "\n");
}catch (Exception ex) {JOptionPane.showMessageDialog(null, "Создайте массив!");}
}
});
button_1.setBounds(23, 96, 200, 23);
frame.getContentPane().add(button_1);
JLabel label = new JLabel("Введите количество элементов массива:");
label.setBounds(23, 34, 244, 14);
frame.getContentPane().add(label);
JLabel label_1 = new JLabel("Выберете вид сортировки:");
label_1.setBounds(23, 130, 180, 14);
frame.getContentPane().add(label_1);
textArea = new TextArea();
textArea.setBackground(Color.WHITE);
textArea.setBounds(271, 96, 303, 458);
textArea.setEditable(false);
frame.getContentPane().add(textArea);
JButton btnNewButton_4 = new JButton("Очистить историю");
btnNewButton_4.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
textArea.setText("");
}
});
btnNewButton_4.setBounds(419, 62, 155, 23);
frame.getContentPane().add(btnNewButton_4);
JButton btnNewButton_5 = new JButton("Сортировка слиянием");
btnNewButton_5.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
try {
perMass = Arrays.copyOf(mass, mass.length);
startTime = System.currentTimeMillis();
sortMerge(perMass);
long timeSpent = System.currentTimeMillis() - startTime;
if (proverka(perMass) == true)
textArea.append("Сортировка слиянием - OK.\nВремя выполнения " + timeSpent + " миллисекунд.\n");
else
textArea.append("Сортировка - Fail!." + "\n");
}catch (Exception ex) {JOptionPane.showMessageDialog(null, "Создайте массив!");}
}
});
btnNewButton_5.setBounds(23, 429, 200, 23);
frame.getContentPane().add(btnNewButton_5);
JButton btnNewButton_6 = new JButton("Сортировка шейкер");
btnNewButton_6.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent arg0) {
try {
s = textField_1.getText();
maxTime = Integer.parseInt(s);
perMass = Arrays.copyOf(mass, mass.length);
startTime = System.currentTimeMillis();
sheker(perMass);
long timeSpent = System.currentTimeMillis() - startTime;
if (proverka(perMass) == true)
textArea.append("Сортировка шейкер - OK.\nВремя выполнения " + timeSpent + " миллисекунд.\n");
else
textArea.append("Сортировка - Время ожидания истекло." + "\n");
}catch (Exception ex) {JOptionPane.showMessageDialog(null, "Создайте массив и задайте время!");}
}
});
btnNewButton_6.setBounds(23, 257, 200, 23);
frame.getContentPane().add(btnNewButton_6);
JButton btnNewButton_7 = new JButton("Сортировка Шелла");
btnNewButton_7.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
try {
s = textField_1.getText();
maxTime = Integer.parseInt(s);
perMass = Arrays.copyOf(mass, mass.length);
startTime = System.currentTimeMillis();
shell(perMass);
long timeSpent = System.currentTimeMillis() - startTime;
if (proverka(perMass) == true)
textArea.append("Сортировка Шелла - OK.\nВремя выполнения " + timeSpent + " миллисекунд.\n");
else
textArea.append("Сортировка - Время ожидания истекло." + "\n");
}catch (Exception ex) {JOptionPane.showMessageDialog(null, "Создайте массив и задайте время!");}
}
});
btnNewButton_7.setBounds(23, 359, 200, 23);
frame.getContentPane().add(btnNewButton_7);
textField_1 = new JTextField("30");
textField_1.setBounds(271, 62, 133, 20);
frame.getContentPane().add(textField_1);
textField_1.setColumns(10);
JLabel lblNewLabel = new JLabel("Максимальное время сортировки (сек):");
lblNewLabel.setBounds(23, 66, 244, 14);
frame.getContentPane().add(lblNewLabel);
JButton btnNewButton_8 = new JButton("Глупая сортировка");
btnNewButton_8.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
try {
s = textField_1.getText();
maxTime = Integer.parseInt(s);
perMass = Arrays.copyOf(mass, mass.length);
startTime = System.currentTimeMillis();
stupidSort(perMass);
long timeSpent = System.currentTimeMillis() - startTime;
if (proverka(perMass) == true)
textArea.append("Глупая сортировка - OK.\nВремя выполнения " + timeSpent + " миллисекунд.\n");
else
textArea.append("Сортировка - Время ожидания истекло." + "\n");
}catch (Exception ex) {JOptionPane.showMessageDialog(null, "Создайте массив и задайте время!");}
}
});
btnNewButton_8.setBounds(23, 155, 200, 23);
frame.getContentPane().add(btnNewButton_8);
JButton btnNewButton_9 = new JButton("Сортировка расчесткой");
btnNewButton_9.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
try {
perMass = Arrays.copyOf(mass, mass.length);
startTime = System.currentTimeMillis();
raschestka(perMass);
long timeSpent = System.currentTimeMillis() - startTime;
if (proverka(perMass) == true)
textArea.append("Сортировка расчесткой - OK.\nВремя выполнения " + timeSpent + " миллисекунд.\n");
else
textArea.append("Сортировка - Fail!." + "\n");
}catch (Exception ex) {JOptionPane.showMessageDialog(null, "Создайте массив!");}
}
});
btnNewButton_9.setBounds(23, 325, 200, 23);
frame.getContentPane().add(btnNewButton_9);
JButton btnNewButton_10 = new JButton("Пирамидальная сортировка");
btnNewButton_10.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
try {
perMass = Arrays.copyOf(mass, mass.length);
startTime = System.currentTimeMillis();
piramidSort(perMass);
long timeSpent = System.currentTimeMillis() - startTime;
if (proverka(perMass) == true)
textArea.append("Пирамидальная сортировка - OK.\nВремя выполнения " + timeSpent + " миллисекунд.\n");
else
textArea.append("Сортировка - Fail!." + "\n");
}catch (Exception ex) {JOptionPane.showMessageDialog(null, "Создайте массив!");}
}
});
btnNewButton_10.setBounds(23, 393, 200, 23);
frame.getContentPane().add(btnNewButton_10);
JButton btnNewButton_11 = new JButton("Сортировка подсчетом");
btnNewButton_11.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
try {
perMass = Arrays.copyOf(mass, mass.length);
startTime = System.currentTimeMillis();
countingSort(perMass);
long timeSpent = System.currentTimeMillis() - startTime;
if (proverka(perMass) == true)
textArea.append("Сортировка подсчетом - OK.\nВремя выполнения " + timeSpent + " миллисекунд.\n");
else
textArea.append("Сортировка - Fail!." + "\n");
}catch (Exception ex) {JOptionPane.showMessageDialog(null, "Создайте массив!");}
}
});
btnNewButton_11.setBounds(23, 463, 200, 23);
frame.getContentPane().add(btnNewButton_11);
JButton btnNewButton_12 = new JButton("Поразрядная сортировка");
btnNewButton_12.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
try {
perMass = Arrays.copyOf(mass, mass.length);
startTime = System.currentTimeMillis();
radixSort(perMass);
long timeSpent = System.currentTimeMillis() - startTime;
if (proverka(perMass) == true)
textArea.append("Поразрядная сортировка - OK.\nВремя выполнения " + timeSpent + " миллисекунд.\n");
else
textArea.append("Сортировка - Fail!." + "\n");
}catch (Exception ex) {JOptionPane.showMessageDialog(null, "Создайте массив!");}
}
});
btnNewButton_12.setBounds(23, 497, 200, 23);
frame.getContentPane().add(btnNewButton_12);
}
}
Рабочие листы
к вашим урокам
Скачать
6 671 422 материала в базе
Настоящий материал опубликован пользователем Гуськова Ольга Алексеевна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Ваша скидка на курсы
40%
Курс профессиональной переподготовки
600 ч.
Курс профессиональной переподготовки
300/600 ч.
Курс повышения квалификации
36 ч. — 180 ч.
Мини-курс
4 ч.
Мини-курс
4 ч.
Мини-курс
6 ч.
(3)
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.