Сортировка подсчетом визуализатор на языке программирования Java

ВВЕДЕНИЕ

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

Компьютерные  технологии  очень удобны для выполнения разнообразных операций, но в разных сферах применения эти операции  разные.  Потому,  каждая отдельная отрасль, которая использует специфические технические средства,  нуждается в своих собственных программах, которые обеспечивают работу компьютеров.

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

Таким образом, новые информационные технологии очень актуальны  в наше время и нуждаются в большем внимании для последующей разработки  и совершенствования. Рядом с этим, большое значение имеет также  и  программирование,  которое является  одним из фундаментальных разделов информатики и потому не может оставаться в стороне.

Программирование содержит целый ряд важных внутренних  задач.  Одной  из наиболее важных задач для программирования  является задача  сортировки.  Под сортировкой обычно понимают   перестановки   элементов   любой последовательности в определенном порядке. Эта  задача  является  одной из  важнейших потому, что ее  целью является  облегчение  последующей  обработки определенных  данных и, в первую очередь, задачи поиска. Одним  из  эффективных алгоритмов  поиска является бинарный поиск. Он работает быстрее, чем, например, линейный поиск,  но  его возможно применять лишь при условии, что последовательность  уже упорядочена, то есть отсортирована.

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

Задача сортировки в программировании не решена полностью.  Ведь,  хотя  и существует  большое количество алгоритмов сортировки, все же целью программирования является не только разработка  алгоритмов  сортировки  элементов,  но и разработка именно эффективных алгоритмов сортировки. Мы знаем, что  одну  и ту же задачу можно решить с помощью разных алгоритмов, и каждый раз изменение алгоритма приводит к новым, более или менее эффективным решениям задачи. Основными требованиями к эффективности  алгоритмов  сортировки  является,  прежде всего, эффективность по времени и экономное использование памяти.  Согласно  этим  требованиям, простые алгоритмы сортировки  (такие,  как сортировка  выбором и сортировки включением) не являются очень эффективными.

Целью курсовой  работы  является реализация простейших алгоритмов сортировки в виде апплетов на языке программирования Java.

1 ОБЗОР ТЕХНОЛОГИИ JAVA

1. Основные особенности языка

Java ˗ объектно-ориентированный язык программирования, разработанный компанией Sun Microsystems(в последующем приобретённой компанией Oracle).

Приложения Java обычно компилируются в специальный байт-код, поэтому они могут работать на любой виртуальной Java-машине (JVM) вне зависимости от компьютерной архитектуры.

Достоинство подобного способа выполнения программ состоит в полной независимости байт-кода от операционной системы и оборудования, что позволяет выполнять Java-приложения на любом устройстве, для которого существует соответствующая виртуальная машина. Другой важной особенностью технологии Java является гибкая система безопасности благодаря тому, что исполнение программы полностью контролируется виртуальной машиной. Любые операции, которые превышают установленные полномочия программы(например, попытка несанкционированного доступа к данным или соединения с другим компьютером) вызывают немедленное прерывание.

Часто к недостаткам концепции  виртуальной машины относят то, что  исполнение байт-кода виртуальной машиной  может снижать производительность программ и алгоритмов, реализованных  на языке Java. В последнее время был внесен ряд усовершенствований, которые несколько увеличили скорость выполнения программ на Java:

а) применение технологии трансляции байт-кода в машинный код непосредственно во время работы программы(JIT-технология) с возможностью сохранения версий класса в машинном коде;

б) широкое использование платформенно-ориентированного кода (native-код) в стандартных библиотеках;

в) аппаратные средства, обеспечивающие ускоренную обработку байт-кода (например, технология Jazelle, поддерживаемая некоторыми процессорами фирмы ARM).

По данным сайта shootout.alioth.debian.org, для  семи разных задач время выполнения на Java составляет в среднем в полтора-два раза больше, чем для C/C++, в некоторых случаях Java быстрее, а в отдельных случаях в 7 раз медленнее. С другой стороны, для большинства из них потребление памяти Java-машиной было в 10-30 раз больше, чем программой на C/C++. Также примечательно исследование, проведённое компанией Google, согласно которому отмечается существенно более низкая производительность и бо́льшее потребление памяти в тестовых примерах на Java в сравнении с аналогичными программами на C++.

Идеи, заложенные в концепцию и  различные реализации среды виртуальной  машины Java, вдохновили множество энтузиастов на расширение перечня языков, которые могли бы быть использованы для создания программ, исполняемых на виртуальной машине. Эти идеи нашли также выражение в спецификации общеязыковой инфраструктуры CLI, заложенной в основу платформы .NET компанией Microsoft [1].

1.2 Классификация платформ Java

Внутри Java существуют несколько основных семейств технологий:

• Java SE ˗ Java Standard Edition, основное издание Java, содержит компиляторы, API, Java Runtime Environment; подходит для создания пользовательских приложений, в первую очередь — для настольных систем.
• Java EE ˗ Java Enterprise Edition, представляет собой набор спецификаций для создания программного обеспечения уровня предприятия.
• Java ME ˗ Java Micro Edition, создана для использования в устройствах, ограниченных по вычислительной мощности, например в мобильных телефонах, КПК, встроенных системах;
• JavaFX ˗ технология, являющаяся следующим шагом в эволюции Java как Rich Client Platform; предназначена для создания графических интерфейсов корпоративных приложений и бизнеса.
• Java Card ˗ технология предоставляет безопасную среду для приложений, работающих на смарт-картах и ​​других устройствах с очень ограниченным объемом памяти и возможностями обработки [1].

1.3 Java и Microsoft

Компанией Microsoft была разработана собственная реализация JVM (MSJVM), включавшаяся в состав различных операционных систем, начиная с Windows 98 (также входила в Internet Explorer от версии 3 и выше, что позволяло использовать MSJVM в ОС Windows 95 и Windows NT 4 после установки IE3+ на данные ОС).

MSJVM имела cущественные отличия от Sun Java, во многом ломающие основополагающую концепцию переносимости программ между разными платформами:

• отсутствие поддержки программного интерфейса вызова удаленных методов (RMI);

• отсутствие поддержки технологии JNI;

• наличие нестандартных расширений, таких как средства интеграции Java и DCOM, работающих только на платформе Windows.

Тесная интеграция Java с DCOM и Win32 ломала многоплатформенную суть языка. Впоследствии это явилось поводом для судебных исков со стороны Sun Microsystems к Microsoft. Суд принял сторону компании Sun Microsystems. В конечном счёте между двумя компаниями была достигнута договорённость о возможности продления срока официальной поддержки пользователей нестандартной Microsoft JVM до конца 2007 года, но не более.

В 2005 году компанией Microsoft для платформы .NET был представлен Java-подобный язык J#, не соответствующий официальной спецификации языка Java и исключённый впоследствии из стандартного инструментария разработчика Microsoft Visual Studio, начиная с Visual Studio 2008 [1].

1.4 Java и Android

Язык Java активно используется для создания мобильных приложений под операционную систему Android. При  этом программы компилируются в  нестандартный байт-код, для использования  их виртуальной машиной Dalvik. Для  такой компиляции используется дополнительный инструмент, а именно Software Development Kit, который предназначен для x86-машины под операционной системой Linux. Его  разработали представители компании Google.

Разработку приложений можно  вести в среде Eclipse, используя  при этом плагин — Android Development Tools (ADT). Версия JDK при этом должна быть 5.0 или  выше [1].

1.5 Применения  платформы Java

Следующие успешные проекты  реализованы с привлечением Java (J2EE) технологий: RuneScape, Amazon, eBay, Yandex (неоднозначная  информация в отношении Java), LinkedIn, Yahoo!.

Следующие компании в основном фокусируются на Java (J2EE) технологиях: SAP, IBM, Oracle. В частности, СУБД Oracle включает JVM как свою составную часть, обеспечивающую возможность непосредственного программирования СУБД на языке Java, включая, например, хранимые процедуры [1].

1.6 Производительность

Программы, написанные на Java, имеют репутацию более медленных и занимающих больше оперативной памяти, чем написанные на языке Си. Тем не менее, скорость выполнения программ, написанных на языке Java, была существенно улучшена с выпуском в 1997—1998 годах так называемого JIT-компилятора в версии 1.1 в дополнение к другим особенностям языка для поддержки лучшего анализа кода (такие как внутренние классы, класс StringBuffer, упрощенные логические вычисления и т. д.). Кроме того была произведена оптимизация виртуальной машины Java — с 2000 года для этого используется виртуальная машина HotSpot. По состоянию на февраль 2012 года, код Java 7 приблизительно лишь в 1.8 раза медленнее кода, написанного на языке Cи.

Некоторые платформы предлагают аппаратную поддержку выполнения для  Java[источник не указан 436 дней]. К примеру, микроконтроллеры выполняющие код Java на аппаратном обеспечении вместо программной JVM, а также основанные на ARM процессоры, которые поддерживают выполнение байткода Java через опцию Jazelle [1].

1.7 Основные возможности

• автоматическое управление памятью;
• расширенные возможности обработки исключительных ситуаций;
• богатый набор средств фильтрации ввода/вывода;
• набор стандартных коллекций: массив, список, стек и т. п.;
• наличие простых средств создания сетевых приложений (в том числе с использованием протокола RMI);
• наличие классов, позволяющих выполнять HTTP-запросы и обрабатывать ответы;
• встроенные в язык средства создания многопоточных приложений;
• унифицированный доступ к базам данных:
• на уровне отдельных SQL-запросов — на основе JDBC, SQLJ;
• на уровне концепции объектов, обладающих способностью к хранению в базе данных — на основе Java Data Objects (англ.) и Java Persistence API;
• поддержка обобщений(начиная с версии 1.5);
• параллельное выполнение программ [1].

1.8 Java-апплет

Аппле́т (англ. applet от application ˗ приложение и -let ˗ уменьшительный суффикс) ˗ это несамостоятельный компонент программного обеспечения, работающий в контексте другого, полновесного приложения, предназначенный для одной узкой задачи и не имеющий ценности в отрыве от базового приложения.

Java-апплет – прикладная программа, чаще всего написанная на языке программирования Java в форме байт-кода. Java-апплеты выполняются в веб-браузере с использованием виртуальной Java машины (JVM), или в Sun's AppletViewer, автономном инструменте для тестирования апплетов. Java-апплеты были внедрены в первой версии языка Java в 1995 году. Java-апплеты обычно пишутся на языке программирования Java, но могут быть написаны и на других языках, которые компилируются в байт‐код Java, таких, как Jython.

Апплеты используются для предоставления интерактивных возможностей веб-приложений, которые не могут быть предоставлены HTML. Так как байт-код Java платформо-независим, то Java-апплеты могут выполняться с помощью плагинов браузерами многих платформ, включая Microsoft Windows, UNIX, Apple Mac OS и GNU/Linux. Такие программы с открытым исходным кодом, как applet2app, могут быть использованы для преобразования апплета в самостоятельные программы на Java или исполняемые файлы Linux и Windows.

Преимущества использования Java-апплетов:

а) кроссплатформенность;

б) апплет может работать на «всех» установленных к этому времени версиях Java, а не только с последней версией; однако, если апплет требует последнюю версию JRE, то клиент будет вынужден ждать более длительной загрузки;

в) апплет поддерживается большинством браузеров;

г) он кэшируется в большинстве браузеров, а потому будет быстро загружаться при возвращении на веб-страницу, но апплет может сохраняться в кэше и создавать проблемы после выхода новых версий;

д) он может иметь полный доступ к машине, на которой выполняется, если пользователь согласен на это;

е) апплет может улучшить использование: после первого запуска апплета, когда JVM уже выполняется и быстро запускается, преимущественно у постоянных пользователей Java, однако JVM придется перезапускать каждый раз, когда запускается новый браузер;

ж) он может запуститься с сопоставимой(но обычно медленнее) скоростью на других компилируемых языках, таких как C++, но во много раз быстрее, чем JavaScript;

з) он может перенести работу с сервера к клиенту, делая Интернет-решение с большим числом пользователей / клиентов.

Java-апплет обладает следующими  недостатками:

а) он требует установки Java-расширения(plug-in), которое не во всех браузерах доступно по умолчанию;

б) он не может запуститься до тех пор, пока не запустится виртуальная Java-машина, и это может занять значительное время при первом запуске;

в) создание и дизайн хорошего пользовательского интерфейса с использованием апплетов считается более сложной задачей, чем с помощью технологии, основанной на HTML;

г) некоторые организации допускают только программное обеспечение, установленное администраторами. В результате многие пользователи не могут видеть апплеты по умолчанию;

д) апплеты могут потребовать использования определенного JRE.

Еще одной альтернативой апплетов для клиента Java является Java Web Start, который запускается вне браузера. В дополнение к функциям, доступным в апплете, простой доступ к полям предоставляет программам Java Web Start доступ по чтению и/или записи определенных файлов, хранящихся у клиента, а также к буферу обмена клиента [1].

1.9 Сравнение сред разработки Java и .Net

.Net и J2EE имеют отличия в технических деталях. Мы рассмотрим два наиболее существенных отличия, а именно технологии реализации многоплатформенности и многоязыковой поддержки.

 Многоплатформенность. Для разработчика важно то, что и .Net, и J2EE предоставляют средства для создания Web-служб. До сих пор J2EE могла гордиться своей поддержкой многоплатформенности, но, если верить Microsoft, более это не является прерогативой J2EE. Microsoft позиционирует .Net как платформу с двухступенчатой компиляцией, что позволяет создавать среду выполнения для любой платформы, подобно Java. Eric Rutter, старший вице-президент Microsoft запустил информацию о переносе .Net на FreeBSD. FreeBSD – это операционная система, производная от BSD (Berkeley Software Distribution) Unix. Он объявил, что Microsoft в самом деле занимается созданием среды выполнения для FreeBSD. Создание такой среды нарушило бы гегемонию Java в области платформенной независимости, однако не стоит пока полагаться на эту информацию. Создание CLR для наиболее популярных операционных систем может занять много лет. Более того, однажды, Microsoft уже делала подобные заявления в отношении переноса DCOM (Distributed Component Object Model) на другие платформы. Однако такой перенос так и не был осуществлен.

  Таким образом, на сегодняшний день единственной средой разработки, поддерживающей многоплатформенность, является J2EE.

Многоязыковая поддержка. Единственной языковой основой J2EE является Java, что сильно отличается от .Net, где поддерживается более двух дюжин языков, включая Fortran, COBOL, C++ и Visual Basic. Можно, конечно, поспорить насчет того, что единственный язык является более элегантным решением, однако надо признать, что .Net предлагает более простое решение для организаций, которые хотят пользоваться знаниями, которые уже имеются у их разработчиков. Ведь для тех разработчиков, которые используют языки, отличные от Java, .Net дает возможность создавать Web-службы на привычном им языке с минимальными затратами на переобучение.

 В то время как вокруг . Net и J2EE бушуют споры, мы должны четко понимать, что представляет собой каждая из платформ. Каждая из технологий позволяет создавать Web-службы, доступные потребителям, использующим самые разные технологии. Web-служба на платформе .Net может вызывать J2EE Web-службу и наоборот, поскольку все Web-службы удовлетворяют одинаковым стандартам. Более того, даже если выяснится, что одна из технологий имеет преимущество, то эффективно использовать это преимущество сможет только высоко квалифицированный программист. Инструменты и средства хороши настолько, насколько хорош программист, их использующий.

 Если рассуждать с точки  зрения развития отрасли программного  обеспечения, то некоторые полагают, что результат соревнования технологий .Net и J2EE будет зависеть от работы отделов маркетинга. Эти технологии настолько похожи, что разница между ними отнюдь не является существенной.

 Web-службы создают однородное представление для неоднородной среды.  И если это верно, то Web-службы должны прекратить споры о том, какая из платформ является лучшей; разработчикам нет нужды беспокоиться о платформе, разрабатывая сервисы, поскольку Web-службы обеспечивают однородное представление.

  Лучше всего попробовать разработать Web-службы и с помощью .Net, и с помощью J2EE. Тогда можно быстро понять, какая из платформ лучше. Выбирая поставщика, многие используют такое эмпирическое правило: если в настоящий момент вы используете платформу Microsoft, то выбирайте .Net, в противном случае – J2EE.

1.10 Преимущества языка программирования Java

Одно из главных преимуществ  языка Java – его независимость от платформы, на которой выполняются программы. Таким образом, один и тот же код можно запускать под управлением операционных систем Windows, Linux, FreeBSD, Solaris, Apple Mac и др. Это становится очень важным, когда программы загружаются посредством глобальной сети интернет и используются на различных платформах.

 Другим не менее важным  преимуществом Java является большая схожесть с языком программирования C++. Поэтому тем программистам, которые знакомы с синтаксисом С и С++ будет просто освоить Java.

 Кроме того, Java – полностью объектно-ориентированный язык, даже в большей степени, чем С++. Все сущности в языке Java являются объектами, за исключением немногих основных типов(primitive types), например чисел. В свое время объектно-ориентированное программирование(ООП) заменило структурное программирование.

 Важно и то, что разрабатывать  на Java программы, которые не содержат ошибок, значительно легче, чем на С++.

 Все дело в том, что разработчиками  языка Java из компании Sun был проведен фундаментальный анализ программ на языке С++. Анализировались "узкие места" исходного кода, которые и приводят к появлению трудновыявимых ошибок. Поэтому было принято решение проектировать язык Java с учетом возможности создавать программы, в которых были бы скрыты наиболее распространенные ошибки.

 Для этого было сделано  следующее: 

а) Разработчики исключили возможность явного выделения и освобождения памяти.

К примеру, память в Java освобождается автоматически с помощью механизма сбора мусора. Получается, что программист застрахован от ошибок, которые возникают от неправильного использования памяти.

б) Введение истинных массивов и запрещение указателей.

Теперь программисты не могут стереть  данные из памяти по причине неправильного  использования указателей.

г) Была исключена возможность перепутать оператор присваивания с оператором сравнения на равенство. Как правило, проблема со знаком "=" очень часто приводит в С и С++ к логическим ошибкам, которые не так просто обнаружить. Особенно в крупных программах.

д) Полностью исключено множественное наследование. Оно было заменено новым понятием – интерфейсом, идея которого была позаимствована из языка Objective C.

 Интерфейс дает программисту  практически все, что тот может  получить от множественного наследования, избегая при этом сложностей, которые возникают при управлении  иерархиями классов.

Выбранная среда программирования хороша тем, что Java одинаково хорошо функционирует и на Windows, и на юниксовидных системах.

2.  АЛГОРИТМИЧЕСКИЙ АНАЛИЗ

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

Разработать апплет на языке Java, который выполняет следующие действия:

а) формирует и выводит массив случайных чисел;

б) выводит сформированный массив;

в) отражает шаги сортировки;

г) выводит отсортированный массив.

2.2 Исходные данные к проекту

Исходными данными к проекту  является массив, в котором 20 элементов, сформированных программой случайно на промежутке от 0 до 9.

2.3 Описание алгоритма сортировки подсчетом

Сортировка подсчетом - специализированный алгоритм, который очень хорошо работает, если элементы данных — целые числа, значения которых находятся в  относительно узком диапазоне. Этот алгоритм работает достаточно быстро, например, если значения находятся  между 1 и 1000.

    Если список  удовлетворяет этим требованиям,  сортировка подсчетом выполняется  невероятно быстро.

    Выдающаяся скорость  сортировки подсчетом достигается  за счет того, что при этом  не используются операции сравнения. 

Идея вот в чем: для  каждого элемента найти, сколько  элементов, меньших определенного  числа, и поместить это число  на соответствующие место. Делается это так: за линейный проход по массиву мы для каждого из возможных значений подсчитываем, сколько элементов имеют такое значение. Потом добавляем к каждому из найденных чисел суму всех предыдущих. Получая, таким образом, сколько есть элементов, значения которых не больше данного значения. Далее, опять-таки за линейный проход, формируем из исходного массива новый отсортированный. При этом следим, чтобы два одинаковых элемента не были записаны в одно место.

2.4 Анализ алгоритма для его визуализации

Из рассмотрения алгоритма следует, что его визуализация должна выполняться  следующим образом:

 • показать массив A, заполненный  начальными значениями;

 • отразить ход решения  задачи – процесс заполнения  массива С, основанный на значениях  элементов массива А;

 • показать подсчет частичных  сумм в массиве С;

 • отразить процесс последнего  этапа решения задачи – заполнения  массива В.

3 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

3.1 Структура программного  комплекса

Апплет состоит из 4 классов: CountSortApplet, CSCanvas, CSControls и AutoThread.

Таблица 3.1 – Содержимое класса CountSortApplet

Таблица 3.2 – Содержимое класса CSCanvas

Продолжение таблицы 3.2

Таблица 3.3 – Содержимое класса CSControls