Файл: Анпоо колледж воронежского института высоких технологий.docx

АНПОО «КОЛЛЕДЖ ВОРОНЕЖСКОГО ИНСТИТУТА ВЫСОКИХ ТЕХНОЛОГИЙ»
Факультет ________________________ обучения

(дневного, заочного)

Направление (Специальность) _____________"_____________________________________"

шифр название

________________________________________________
Пояснительная записка к курсовой работе

По дисциплине

ТЕХНОЛОГИЯ РАЗРАБОТКИ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

на тему "Внешняя сортировка. Каскадная сортировка.

(типизир.файлы)"
Выполнил: студент группы ________________

название группы

______________________________

ФИО студента

Подпись студента: _______________________

Руководитель: ___________________________

должность, научная степень

______________________________
ФИО руководителя
Дата сдачи работы: ____.________.________

Дата защиты работы: ____.________.________

Оценка (зачёт):____________________________
Подпись руководителя: ___________________

Воронеж

2022

Задание на проектирование

1. 
   Проанализировать и описать принципы внешней сортировки, каскадной сортировки (типизир.файлы)
   
2. 
   Построить обобщённую и детальную схемы реализации задачи, построить модульную структуру программной системы, описать диалог взаимодействия с пользователем, построить модели разрабатываемой системы.
   
3. 
   В результате выполнения курсовой работы должна быть разработана программа с ее полным описанием в пояснительной записке (текстовая часть курсовой работы).
   

Содержание

Введение

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

---

сравнительной сортировки заключается в том, что они требуют линейного времени — O(nlogn) в худшем случае, но для реальных данных (например, почти отсортированных данных) и не Алгоритмы, основанные на сравнении, могут работать лучше. Сортировка подсчетом может повысить производительность.

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

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

Актуальность сортировки данных подчеркивается многими современными исследованиями [1-5]. Например, в работе [1] авторы систематизировали и сравнили методы сортировки данных в буферной памяти, детально рассмотрели внешнюю сортировку [2]. Актуальными проблемами сортировки данных занимались ученые в работе [3].Применением методов внешней и внутренней сортировки для баз данных занимались[4,5].

Задачами курсового проектирования являются:

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

---

---

Раздел 1.

1.1 Алгоритмы сортировки

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

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

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

---

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

Напомним, что сектор - это основная единица ввода-вывода. Другими словами, все чтения и записи на диск выполняются для одного или нескольких полных секторов. Размер сектора обычно равен двум, в диапазоне от 512 до 16K байт, в зависимости от операционной системы, размера и скорости дискового накопителя. Размер блока, используемый для внешних алгоритмов сортировки, должен быть равен или кратен размеру сектора.

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

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

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

---