СКАЧАТЬ РАБОТУ БЕСПЛАТНО -
1. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ
Большинство систем автоматизации деятельности университета построены на основе модульной архитектуры и, как правило, в качестве одного из модулей выступает компонент, обеспечивающий автоматизацию работы библиотеки. В связи с тем, что такие библиотечные системы нацелены на внедрение в ВУЗ в целом, в них отсутствует ряд разделов и функций, имеющих важное значение для деятельности кафедры.
Основная цель использования информационных систем – достижение необходимой степени динамизма в управлении через распределение ресурсов и контроль их использования. Это позволяет организовать работу так, чтобы своевременно удовлетворять новые потребности и быстро оценивать появляющиеся возможности. В частности быстрое получение необходимой информации средствами электронной библиотеки.
Основным процессом в ВУЗе является образовательный процесс. В рамках этого процесса происходит прием, обработка, хранение и передача разнообразной информации. От того, как налажено управление информацией, зависит эффективность работы.
Самой важной функцией используемых вузами библиотечных систем является минимизация затрат на получение необходимой информации в требуемом виде по запросам студентов и преподавателей. Понятно, что вся информация должна храниться в структурированном виде, быть актуальной и одновременно с этим защищенной.
1.1 Анализ существующих систем
При создании любой информационной системы встает вопрос о целесообразности ее разработки в связи с тем, что возможно уже существуют рабочие программные продукты данного типа, и легче приобрести их, а не тратить время и ресурсы на создание нового.
Поэтому перед началом работы по созданию данного программного продукта был проведен анализ существующих систем библиотечной деятельности.
1.1.1 Национальная библиотека Украины имени Вернадского
Эта библиотека состоит из трех основных разделов: "Информационные ресурсы", "Интернет-путеводители", "Национальные доклады НАН Украины".
В разделе "Информационные ресурсы" содержаться большое число подразделов, связанных с непосредственной деятельностью библиотеки (Система каталогов, Предоплаченные ресурсы, Реферативная база данных, Электронные научные профессиональные издания, Электронный фонд, Научная периодика Украины, Тематические собрания, Научные учреждения, Аналитические материалы СИАЗ, Научные биографии ученых, Библиотечные новости, Информация о Библиотеке). Следует отметить, что при переходе в некоторые из выше указанных подразделов открывается окно поиска, и дальше пользователь ищет интересующую его информацию в базе данных библиотеки, такая возможность будет реализована и в ниже приведенных разделах.
Раздел "Интернет-путеводители" даёт возможность получить ссылки на самые различные интернет ресурсы. Назначение ресурсов легко можно понять из названий подразделов (Поисковые системы, Органы государственной власти, Библиотеки Украины, Национальные университеты, Национальные библиотеки, Энциклопедии и словари, Электронные библиотеки, Газеты и Интернет-издания).
Раздел "Национальные доклады НАН Украины" в его подразделах содержится информация об острых социально политических аспектах жизни государства (Новый курс: реформы в Украине. 2010-2015, Социально-экономическом состоянии Украины: последствия для народа и государства).
В данной библиотеке реализована возможность работы на нескольких языках. Следует отметить, что некоторые из подразделов срабатывают как ссылки на нужный интернет ресурс, а не материал в библиотеке.
Недостатком является нечеткая каталогизация, из-за чего сложно определить в каком разделе находиться необходимая книга.
1.1.2 Электронная библиотека Наука и Техника
Эта система является интересным примером автоматизации библиотечной деятельности. Обладает как позитивными, так и негативными свойствами. К положительным чертам можно отнести следующее:
- реализована возможность работы на нескольких языках;
- разбита на сравнительно небольшое число разделов (Книги, Статьи, Журналы, Нобелевские лауреаты, Подписка, Карта сайта, Аудитория, Награды, Организация, Издания, Для авторов, Для редакторов). Что делает её хорошо структурированной;
- на главной странице реализованы разделы новых поступлений и ссылки на интересные издания;
- существует возможность поиска.
Недостатком являет не очень удобный интерфейс. Расположение элементов на странице не всегда позволяет быстро найти нужный раздел или ссылку.
1.1.3 Научно-техническая библиотека ХАИ
Обладает очень удобным интерфейсом. Реализован электронный каталог и система поиска. Разбита на несколько разделов.
Раздел о библиотеке даёт возможность узнать непосредственно о деятельности библиотеки, разбит на несколько подразделов (О библиотеке, История, Структура библиотеки, Правила библиотеки, Режим работы).
Раздел издания библиотеки, делится на несколько подкаталогов, в которых содержится информация, помогающая пользователям сориентироваться в выборе нужной литературы (Биобиблиография, Рекомендательные списки, Бюллетень новых поступлений, Список периодических изданий).
Раздел интернет-ресурсы (Полезные ссылки, Патентные ресурсы, Открытый доступ).
Раздел услуги. В подразделах вы сможете найти информацию об услугах, которые предоставляет библиотека (Виртуальная справка, Виртуальные выставки, Системы МБА и ЭДД, Литературная гостиная).
Раздел обменный фонд (Книги в читательском формуляре, Буккроссинг).
Также здесь можно найти контактную информацию работников библиотеки, прочитать последние новости и многое другое.
1.1.4 Результаты анализа
Был проведен анализ большого количества существующих библиотек. Выше приведены наиболее известные примеры решений задач автоматизации библиотечной деятельности. Все они обладают своими преимуществами и недостатками. Но все они созданы для больших государственных или образовательных учреждений. Данная же работа направлена на создание системы для малой структуры (кафедры).
Поэтому, взятая за основу система электронной библиотеки ХАИ (выбрана как наиболее удачная), была упрощена до уровня решения необходимых задач.
1.2 Постановка задачи
Как было уже сказано ранее, целью этой работы является разработка проекта (и последующая его реализация) электронной библиотеки для малой структуры.
Система должна включать следующие возможности:
- хранить электронные книги:
1) книга;
2) краткое описание.
- хранить электронные методички:
1) методичка;
2) краткое описание.
- добавление и постоянное обновление материалов связанных с учебным процессом:
1) добавление вопросов к модулям и экзаменам:
2) возможность преподавателей оповещать студентов о событиях, связанных с изменением учебного процесса.
- скачивание электронных книг и методичек
- 1.3 Сравнительный анализ средств разработки WEB-приложений.
На сегодняшний день существует большое количество средств разработки Web-приложений. Предлагаю остановиться на трёх лидерах этого рынка, а именно Java Server Pages(JSP), PHP, ASP.NET.
Рис. 1 Средства разработки Web-приложений
1.3.1 Преимущества технологии Java Server Pages
Преимущества:
- Кросплатформенность
- Разделение ролей.
- Многократно используемые компоненты и библиотеки тэгов.
- Разделение динамического и статического содержимого.
- Поддержка скриптинга и акций.
Недостатки:
- сложность освоения
- неудобства при разработке
- малое количество хостингов
1.3.2 Преимущества технологии PHP
Преимущества:
- Кроссплатформенность
- Широкая распространенность
- Открытый исходный код
- Большое количество готовых решений и библиотек
- Низкая стоимость поддержки приложений
Недостатки:
- Недостаточно развитое ООП
- Несогласованный синтаксис встроенных функций и порядок их параметров
- Отсутствие многопоточности
1.3.3 Преимущества технологии ASP.NET
Преимущества:
- Кроссплатформенность
- Полноценный язык.
- Компиляция программ.
- Идентичность среды разработки и деплоймента.
- Полная поддержка юникода.
- Большое количество стандартных библиотек
- Использование MS SQL очень мощного и удобного инструмента при работе с базами данных
- Поддержка Microsoft
Недостатки:
- большой размер готовой html страницы
- возможны неудобства в работе с Javascript и Ajax
1.3.4 Результаты анализа
Были исследованы самые популярные на сегодняшний день средства разработки Web-приложений. Очевидно, что технология ASP.NET гораздо лучше подходит для решения поставленной задачи. Это обусловлено рядом экономических и технических аспектов. Так как при выборе этой технологии на сторону разработчика становится весь коммерческий аппарат Microsoft. Это же обуславливает и преимущества с технологической стороны вопроса. Более подробный анализ будет приведен в главе №4 при обосновании выбора инструментальных средств.
2. РАЗРАБОТКА МОДЕЛЕЙ
2.1 Карта сайта
Общепринято, что карта сайта это одна из страниц, аналогичная содержанию книги. На ней представлен полный перечень разделов, либо всех страниц, имеющихся на сайте. Ниже изображено представление карты моего сайта в виде инфологической модели.
Рис. 2.1 Карта сайта
Основываясь на вышеприведенной инфологической модели, была разработана концептуальная модель сайта.
Страница login.aspx (страница авторизации). На ней пользователь может ввести свой логин и пароль для входа в систему под определённой ролью. При нажатии на кнопку входа (при условии что логин и пароль введены верно) пользователь переходит на страницу default.aspx. При нажатии на кнопку регистрации переход происходит на страницу registration.aspx.
Рис. 2.2 Страница входа
Страница registration.aspx (страница регистрации). Здесь пользователь, введя свои данные, может пройти регистрацию. Для этого необходимо правильно заполнить все поля формы (фамилия, имя, логин, пароль, e-mail) и, нажав кнопку, зарегистрироваться, после чего вся информация о нём будет занесена в базу данных, а сам пользователь перейдёт на страницу default.aspx.
Рис. 2.3 Страница регистрации
Страница default.aspx (главная страница). Содержит краткую информацию о кафедре. На ней расположены кнопки с названиями главных разделов библиотеки. При нажатии на эти кнопки можно перейти на соответствующие им страницы, такие как специальная литература (specialliterature.aspx), художественная литература (artliterature.aspx), новости кафедры (news.aspx).
Здесь же реализована функция поиска. Если в специальное окно ввести название книги или Ф.И.О автора, то после нажатия функциональной кнопки произойдёт переход на страницу с результатами поиска search.aspx.
Рис. 2.4 Главная страница
Страница specialliterature.aspx (страница специальной литературы). Содержит ряд разделов, в которых хранится литература и информация о ней. Названия разделов соответствуют названию предметов. Напротив них приведены ФИО преподавателей.
Вверху реализована навигационная панель для быстрого перемещения по сайту. Так, нажав кнопку Главная или Художественная литература, можно перейти в соответствующие разделы.
Рис. 2.5 Страница специальной литературы
Страница subject.aspx (страница предмета) Таких страниц несколько, но, поскольку все они устроены по одному принципу, ниже приведен пример только одной из них. Слева идёт перечень книг, методичек и их авторов, справа напротив каждой из них размещены функциональные кнопки при нажатии на которые можно либо скачать, либо просмотреть интересующий вас материал. Реализована навигационная панель.
Рис. 2.6 Страница предмета
Страница artliterature.aspx (страница художественной литературы). По своей структуре похожа на страницу специальной литературы, но отличается тематикой и названием разделов (например, вместо названия предметов разбиение происходит на жанры). Реализована навигационная панель.
Рис. 2.7 Страница художественной литературы
Страница genre.aspx (страница жанра). Как и в случае страницы предмета их несколько, но в силу того что они по своей структуре идентичны мы рассмотрим только одну. Слева список книг и их авторов, справа функциональные кнопки при нажатии на которые можно скачать или просмотреть интересующую литературу(также, как это выполнено на странице предмета). Реализована навигационная панель.
Рис. 2.8 Страница жанра
Страница news.aspx (страница новостей). Здесь пользователь может узнать о последних новостях из жизни кафедры. Посмотреть даты готовящихся мероприятий. Реализована навигационная панель.
Рис. 2.9 Страница новостей
Страница search.aspx (страница поиска). На этой странице отображаются результаты поиска. Если поиск происходил по Ф.И.О автора, то выводится список всех его произведений. Если же по названию книги, то все книги с таким названием. Справа размещены функциональные кнопки при нажатии на которые можно скачать или просмотреть интересующий вас материал (аналогично тому как это реализовано на страницах предмета и жанра). Реализована навигационная панель.
Рис. 2.10 Страница поиска
2.2 UML диаграммы
UML (Unified Modeling Language — унифицированный язык моделирования) — язык графического описания для объектного моделирования в области разработки программного обеспечения. UML является языком широкого профиля, это открытый стандарт, использующий графические обозначения для создания абстрактной модели системы, называемой UML-моделью. UML был создан для определения, визуализации, проектирования и документирования в основном программных систем.
Использование UML не ограничивается моделированием программного обеспечения. Его также используют для моделирования бизнес-процессов, системного проектирования и отображения организационных структур.
Также он позволяет разработчикам программного обеспечения достигнуть соглашения в графических обозначениях. Для этого выработано представление общих понятий (таких как класс, компонент, обобщение (generalization), объединение (aggregation) и поведение). В результате можно больше сконцентрироваться на проектировании и архитектуре.
После анализа UML были выделены его основные преимущества:
- UML объектно-ориентированный, в результате чего методы описания результатов анализа и проектирования семантически близки к методам программирования на современных объектно-ориентированных языках;
- UML позволяет описать систему практически со всех возможных точек зрения и разные аспекты поведения системы;
- Диаграммы UML сравнительно просты для чтения после достаточно быстрого ознакомления с его синтаксисом;
- UML расширяет и позволяет вводить собственные текстовые и графические стереотипы, что способствует его применению не только в сфере программной инженерии;
- UML получил широкое распространение и динамично развивается.
2.2.1 Разработка Use Case диаграммы
Для создания любых программных продуктов первым делом определяются требования, которым должна удовлетворять система. Однако если написать эти требования на бумаге, то часто можно получить список функций, по которому трудно судить будет ли будущая система выполнять свое назначение и сможет ли она облегчить пользователю выполнение его работы. Непонятно какие из выполняемых функций более важны и для кого.
Для того, чтобы более точно понять как должна работать система, все чаще используется описание функциональности системы через варианты использования (Use Case или прецеденты). Варианты использования это - описание последовательности действий, которые может осуществлять система в ответ на внешние воздействия пользователей или других программных систем. Варианты использования отражают функциональность системы с точки зрения получения значимого результата для пользователя, поэтому они точнее позволяют ранжировать функции по значимости получаемого результата.
Суть диаграммы вариантов использования состоит в следующем. Проектируемая система представляется в виде множества сущностей или актеров, взаимодействующих с системой с помощью вариантов использования.
Рис. 3 Use Case диаграмма
При этом актером (actor) или действующим лицом называется любая сущность, взаимодействующая с системой извне. Это может быть человек, техническое устройство, программа или любая другая система, которая может служить источником воздействия на моделируемую систему так, как определит сам разработчик. Вариант использования служит для описания сервисов, которые система предоставляет актеру. Диаграмма вариантов использования может дополняться пояснительным текстом, который раскрывает смысл или семантику составляющих ее компонентов.
Как видно из разработанной диаграммы система рассчитана на три вида пользователей ("актёров") с разными уровнями доступа: преподаватель, студент, модератор.
Студент обладает правами просмотра, поиска и скачивания данных с сервера.
Модератор назначается из числа студентов (обладает всеми их правами по принципу наследования) и получает возможность добавления, удаления книг, а также редактирования информации о них в разделе художественной литературы. Этот уровень доступа также позволяет делать запрос по всем данным художественной литературы.
Преподаватель обладает всеми правами модератора и пользователя (используется вышеуказанный принцип наследования). Он обладает возможностью редактировать раздел специальной литературы: удалять, добавлять книги и при необходимости вносить изменения в сами учебные пособия. Ему доступна возможность запроса данных по специальной литературе.
Следует отметить, что, по сути, все преподаватели являются администраторами системы.
Разработка этой диаграммы решила следующие задачи:
- определены общие границы и контекст моделируемой предметной области;
- сформулированы общие требования к функциональному поведению проектируемой системы;
- разработана исходная концептуальная модель системы для ее последующей детализации в форме логических и физических моделей;
- подготовлена исходная документация для взаимодействия разработчиков системы с ее заказчиками и пользователями.
2.2.2 Разработка диаграммы классов
Центральное место в объектно-ориентированном программировании занимает разработка логической модели системы в виде диаграммы классов. Диаграмма классов (class diagram) служит для представления статической структуры модели системы в терминологии классов объектно-ориентированного программирования. Диаграмма классов может отражать, в частности, различные взаимосвязи между отдельными сущностями предметной области, такими как объекты и подсистемы, а также описывать их внутреннюю структуру и типы отношений.
Диаграмма классов представляет собой граф, вершинами которого являются элементы типа "классификатор", связанные различными типами структурных отношений. Диаграмма классов может также содержать интерфейсы, пакеты, отношения и даже отдельные экземпляры, такие как объекты и связи.
Прежде чем приступать к разработке диаграммы следует понимать, что такое класс в языке UML. Он служит для обозначения множества объектов, которые обладают одинаковой структурой, поведением и отношениями с объектами других классов, разновидности отношений приведены в таблице (рис 13). Графически класс изображается в виде прямоугольника, который дополнительно может быть разделен горизонтальными линиями на разделы или секции. В этих разделах могут указываться имя класса, атрибуты (переменные) и операции (методы).
Рис. 4 Мощность отношений
Рис. 5 Диаграмма классов
Ниже приведено описание разработанной мной диаграммы. А именно перечислены все классы, их атрибуты (переменные, связанные с классом или объектом), выполняемые операции, связи и взаимодействия.
Гость. У этого класса одна операция (просмотр). Служит для просмотра данных библиотеки. Связь от одного ко многим с классом "данные библиотеки". Атрибутов нет.
Студент. Атрибуты это информация о студенте (фамилия, имя, e-mail), а операции это скачивание и поиск. Связан с классами "вход в систему" и "литература", а также с классом "гость" (по принципу наследования), благодаря чему ему доступна операция просмотра.
Модератор. Атрибуты это информация о модераторе (id, имя, фамилия, логин, пароль, e-mail). Связан с классом "редактирование х/л" (связь один ко многим), а также с классом "студент" (принцип наследования), что позволяет наследовать операции студента и гостя (просмотр, скачивание, поиск).
Преподаватель. Атрибуты это информация о преподавателе (id, имя, фамилия, e-mail), связан с классом "редактирование с/л" (связь один ко многим) и с классом "модератор" (показывает наследование) соответственно по принципу описанному выше он наследует все операции и свойства модератора.
Вход в систему. Операции это авторизация. При входе в систему пользователи получают свои права доступа (Студент – простой пользователь, модератор – назначенный из числа студентов, преподаватель – обладающий правами администратора). Атрибутов нет.
Данные библиотеки. Операции это получение данных (получает данные от класса "литература", передавая их запрашивающему гостю). Связан с классом "литература" (связь один ко многим)
Литература. Промежуточный класс не обладает операциями или атрибутами. Он является совокупностью классов "специальная литература" и "художественная литература" (это показано при помощи соответствующей связи). Также он связан с классами "данные библиотеки" и "студент" (способ их связи был описан выше). Это означает что запрос к данным хранящимся в этом классе, студент (и все наследующие его) может сделать напрямую. Для гостя, который производит запрос через данные библиотеки, будет доступен только просмотр.
Художественная литература. Атрибуты это информация о книгах (автор, жанр, название книги). Связана с классом "<перечисление> жанры" (связь один к одному)
<перечисление> Жанры. Класс перечисления жанров не имеет атрибутов и операций (по сути это список имеющихся жанров).
Редактирование х/л. Не обладает операциями и атрибутами. Связан с классом "художественная литература" (связь от многого к одному) и с интерфейсным классом редактирования ""interface" редактирование".
Специальная литература. Атрибуты это информация о предметах, книгах и методичках (предмет, название методички, название книги, автор) связан с классом "<перечисление> предметы" (связь от одного к одному).
<перечисление> Предметы. Не обладает операциями и атрибутами (по сути это перечисление существующих предметов)
Редактирование с/л. Класс редактирования связан с классом "специальная литература" (связь от много к одному) и интерфейсным классом редактирования ""interface" редактирование" (по тому же принципу что и класс "редактирование х/л").
"interface" Редактирование. Операции это удаление, добавление, изменение. Суть заключается в том, что модератор, делая запрос через класс "редактирование х/л," может редактировать класс "художественная литература". В свою очередь преподаватель, делая запрос через класс "редактирование с/л," может производить те же операции с классом "специальная литература". Это сделано для того что бы каждый мог работать с данными библиотеки в соответствии со своим уровнем доступа.
3. РАЗРАБОКА АЛГОРИТМОВ
3.1 Алгоритмы поиска
Прежде всего следует понимать, что поиск данных это раздел информатики, изучающий алгоритмы для поиска и обработки информации как в структурированных (базы данных) так и неструктурированных (текстовый документ) данных. Он неразрывно связан с понятием фильтрации данных (вывод данных нужных пользователю в результате созданного им запроса). Для данной работы интерес представляет именно работа с базами данных.
Самая распространённая задача, которую решают приложения работающие с базами данных - это поиск необходимых записей по заданному критерию.
В этой работе рассмотрены два возможных критерия поиска:
- Поиск по названию книги или методички
- Поиск по ФИО Автора.
Следует отметить, что существует довольно большое количество алгоритмов для решения поставленной задачи. Вот основные из них:
- Алгоритм Гровера GSA (Grover search algorithm) — быстрый квантовый алгоритм решения задачи перебора, то есть нахождения решения уравнения (1)f(x) = 1 где f есть булева функция от n переменных. Предполагается, что функция f задана в виде черного ящика, или оракула, то есть в ходе решения мы можем только задавать оракулу вопрос типа: "чему равна f на данном x", и после получения ответа использовать его в дальнейших вычислениях). То есть задача решения уравнения (1) является общей формой задачи перебора; здесь требуется отыскать "пароль к устройству f", что классически требует прямого перебора всех N = 2n вариантов.
- Поиск A* в информатике и математике, алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной). Порядок обхода вершин определяется эвристической функцией "расстояние + стоимость" (обычно обозначаемой как f(x)). Эта функция — сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет) и эвристической оценкой расстояния от рассматриваемой вершины к конечной (обозначается как h(x)). Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Например, для задачи маршрутизации h(x) может представлять собой расстояние до цели по прямой линии, так как это физически наименьшее возможное расстояние между двумя точками.
- Алгоритм поиска по ключевым словам именно он был выбран для решения поставленной задачи. Не самый быстрый, но очень простой в реализации.
БД где хранятся данные построена следующим образом: в одной из таблиц хранящей атрибуты книг и методичек, есть колонки с ключевыми словами и фразами. По ним и реализуется поиск нужного материала на основе введенных пользователем данных.
После старта алгоритма происходит запрос на список всех ключевых слов для каждой книги или методички. Полученный список сравнивается с тем что ввёл пользователь и выводится результат после чего алгоритм завершается.
Ниже алгоритм приведен в виде блок-схемы.
Рис. 6 Алгоритм поиска по ключевым словам
3.1.1 Алгоритм поиска по названию книг и методичек
В общем виде алгоритм представлен ниже в виде блок-схемы. Когда он начинает действовать делается запрос на сервер по всем книгам и методичкам с искомым названием (это происходит по алгоритму поиска ключевых слов, который описан выше). После того как выбраны все совпадения, на странице поиска отображаются все поля соответствующие критериям выбора (выводятся все книги и методички в названии которых были использованы введённые слова или фразы) и алгоритм завершается.
Рис. 7 Алгоритм поиска по названию книги и методички
3.1.2 Алгоритм поиска по ФИО автора
Этот алгоритм реализуется схожим образом с предыдущем. Точно также когда он начинает выполнятся, происходит запрос на сервер по всем книгам и методичкам написанных заданным автором (ФИО которого было введено в поле поиска). Он, как и в предыдущем случае, выполняется по алгоритму поиска ключевых слов. После того как выбраны все совпадения, на странице поиска отображаются все поля соответствующие критериям выбора (названия книг и методичек написанных заданным автором) и алгоритм завершается. Ниже он представлен в виде блок-схемы.
Рис. 8 Алгоритм поиска по ФИО автора
3.2 Алгоритмы сортировки
Алгоритм сортировки — это алгоритм для упорядочения элементов, в том числе и в базе данных. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:
Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = | A | . Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n*n) идеальное поведение для упорядочения — O (n).
Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют O( log n) памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы (так как всё это потребляет O(1)). Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.
Также существует классификация алгоритмов сортировки:
- Устойчивость — устойчивая сортировка не меняет взаимного расположения равных элементов.
- Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
- Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O(n log n), , но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.
Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:
- Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте, без дополнительных затрат. В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти.
|
