Файл: Методы сортировки данных: эволюция и сравнительный анализ. Примеры использования(Понятие данных и массивов данных).pdf

Алгоритмы сортировки разделяются по свойствам и классификации:

- Устойчивость — устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами.

- Естественность поведения — эффективность метода при обработке уже упорядоченных или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

- Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O( n • log n), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:

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

В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.

- Внешняя сортировка оперирует запоминающими устройствами большого объёма, но не с произвольным доступом, а последовательным (упорядочение файлов), то есть в данный момент «виден» только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным во внешней памяти производится намного медленнее, чем операции с оперативной памятью.

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

Объём данных не позволяет им разместиться в ОЗУ.

Также алгоритмы классифицируются по:

- потребности в дополнительной памяти или её отсутствию

- потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствию таковой.

Для моделирования сортировки были выбраны 3 алгоритма из разных классификаций и с разными свойствами , для более точногой оценки.

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

---

количество шагов алгоритма, необходимых для упорядочения

количество сравнений элементов

количество перестановок, производимых при сортировке

Мы рассмотрим только три простейшие схемы сортировки. [8]

Метод «пузырька»

Метод «пузырька» является наиболее простым методом сортировки. Если представить, что массив (таблица) располагается вертикально, то легко можно понять его идею. Подобно большим пузырькам всплывают вверх элементы с большим значением. При первом проходе вдоль массива, берется первый элемент, начиная проход «снизу», и поочередно сравнивается с последующими. При этом:

• если встречается с наименьшим значением (более «легкий») элемент, то они меняются местами;
• если встречается с более «тяжелым» элементом, конечный становится «эталоном» для сравнения, и все следующие сравниваются с ним.

В итоге в самом верху будет наибольший элемент массива.

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

Хочется заметить, что надобности рассматривать ранее «всплывшие» элементы при втором и дальнейших проходах нет, так как уже известно, что они больше оставшихся. Говоря иначе, элементы, стоящие на позициях выше j не нужно проверять во время j-го прохода.

Теперь приведём текст программы упорядочения массива M[1..N]:

Для перестановки элементов местами во всех алгоритмах сортировки станет стандартная процедура swap:

Заметим, что в случае если массив M — глобальный, то процедура имеет возможность содержать лишь аргументы (а не результаты). Не считая того, что учитывая во внимание специфику ее использования в данном алгоритме, можно свести число параметров к одному, а не двум.

Сортировка вставками

Второй метод называется метод вставок, т.к. на j-ом этапе мы «вставляем» j-ый элемент M[j] в нужную позицию среди элементов M[1], M[2],. . ., M[j-1], которые уже упорядочены. После этой вставки первые j элементов массива M станут упорядоченными.

Сказанное можно записать следующим образом:

Если воспользоваться барьером, а именно установить так называемый «фиктивный» элемент M[0], значение которого должно быть заведомо меньше значения любого из «реальных» элементов массива, то такой процесс перемещения элемента M[j] будет самым простым. И обозначим это значение через — оо.

---

Если барьер не применить, то перед вставкой M[j], в позицию i-1 надо выяснить, не будет ли i=1. В случае если нет, тогда сравнить M[j] (который в данный момент будет находиться в позиции i) с элементом M[i-1].

Описанный алгоритм имеет следующий вид:

Сортировка посредством выбора

Идея сортировки с помощью выбора не считается сложнее двух предыдущих. На j-ом этапе выбирается элемент минимальный среди M[j], M[j+1],. . ., M[N] и меняется местами с элементом M[j]. В результате после j-го этапа все элементы M[j], M[j+1],. . ., M[N]будут упорядочены.

Сказанное можно описать следующим образом:

Более точно:

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

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

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

1. Оценить адекватность модели.

2. Предложить решение, направленные на совершенствование этой структуры.

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

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

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

---

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

Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют O(log n) памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы (так как всё это потребляет O(1)). Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.

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

Глава 2. Особенности сортировки данных с учетом возможностей среды программирования.

2.1. Возможности среды Lazarus для реализации программы сортировки

Lazarus - это среда визуального программирования. В Lazarus есть возможность не только создавать программный код, но и, в особенности, наглядно (визуально) показывать в системе то, что мы хотели бы создать. [3]

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

---

Среда визуального программирования Lazarus облегчает и ускоряет создание программы, так как объединяет в себе компилятор, объектно-ориентированные средства визуального программирования и всевозможные технологии.

В среде Lazarus для ввода массивов не предусмотрены практически никакие особые компоненты, поэтому можно использовать компоненты или же любые другие, предназначенные для ввода данных. [9]

Элементы в окне можно вводить по одному. В обработчике событий при однократном нажатии кнопки ввода должны выполниться следующие операторы:

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

На рисунке 1 представлена форма для ввода элементов массива.

Рисунок 1. Форма программы для ввода и вывода массива

С кнопкой связан метод . Метод устанавливает фокус на строке ввода . [2]

На рисунке 2 представлен результат работы программы.

Рисунок 2. Результат работы программы ввода и вывода массива

Если разделить пробелами элементы массива в компоненте , то можно ввести сразу все элементы массива. Число пробелов-разделителей может быть любым.

Цикл для пропуска пробелов между словами:

Слова можно пропустить аналогичным циклом:

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

Текстовый редактор может содержать любое количество строк, это является отличием от строки ввода. Его свойство представляет собой строку, состоящую из находящихся в поле строк, разделенных последовательностью символов с кодами 13 и 10 (конец строки и переход на новую строку). При нажатии клавиши эти символы добавляются в поле . Для выделения подстроки, содержащей элемент массива, нужно отыскать символ с кодом 13 (#13), скопировать в новую подстроку, а затем удалить ее вместе с кодами 13 и 10 и продолжить поиск конца строки.

---