Файл: Сортировка данных в массиве. Оценка эффективности метода.pdf

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

Для решения проблем связаных с различними поисками конкретной информации среди огромнного количества данныйх было предложено множество различных алгоритмов сортировки: например, слияние с вставкой, обменная поразрядная сортировка, каскадное слияние и метод Шелла, многофазное слияние и вставки в дерево, осциллирующая сортировка и быстрая сортировка Хоара, пирамидальная сортировка Уильямса и обменная сортировка со слиянием Бэтчера. В итоге и произошло интенсивное развитие теории сортировки.

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

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

Цель курсовой работы - разработка регламента выполнения процесса «Оценка эффективности метода».

В связи с поставленной целью решались седующие задачи курсовой работы:

Описать предметную область. Поставить задачи;

Моделирование сортировки данных в массиве;

Сравнение алгаритмов сортировки;

Оценка эфективности алгоритмов.

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

Предметом исследования явлется Сортировка данных в массиве, а так же Оценка эффективности метода.

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

Глава 1. Аналитическая часть

1.1 Описание предметной области. Постановка задачи

Для оценки метода будут использованы 3 алгоритма сортировки:

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

2. Сортировка выбором — ищет наименьшее или наибольшее значение элемента массива и помещяет его в начало или конец упорядоченного списка.

3. Сортировка слиянием — выстраивет первую и вторую половину списка по отдельности , а затем объединяет упорядоченные списки в отсортировоном виде, но требует много дополнительной памяти.

Сам же алгоритм сортировки — это алгоритм для упорядочивания элементов в списке. На данный момент существует множество видов алгаритмов сортировки, таких как: Слиянием, Вставками, Пузырьком, Гномья, Шелла, Пирамидальная, с помощью двоичного дерева, Выбором и т.д.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таким оброзом:

Алгоритмы устойчивой сортировки:

- Сортировка пузырьком

- Сортировка слиянием

Алгоритмы неустойчивой сортировки:

- Сортировка выбором

Формулировка задачи.

Допустим нужно упорядочить N элементов: R1, R2, ……., Rn. Каждый элемент представляет из себя запись Rj, содержащую какието данные и ключ Kj, управляющий процессом сортировки. На множестве ключей определено отношение порядка « < » так, чтобы для всех трёх значений ключей a, b, c выполнялись следующие условия:

-закон трихотомии: либо a < b, либо a > b, либо a = b;

-закон транзитивности: если a < b и b < c, то a < c.

Такие условия определяют математическое понятие линейного или совершенного упорядочения, а удовлетворяющие им множества поддаются сортировке многих методов.

Целью сортировки является нахождение перестановки записей p(1) p(2) … p(n) с индексами {1, 2, … ,N} , после которой ключи расположились бы в порядке неубывания:

Kp(1) ≤ Kp(2) ≤ … ≤ Kp(n)

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

p(i) < p(j) для любых Kp(i) = Kp(j) и i < j.

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

Этот вариант модели, подвергает рецензированию, обсуждению и последующему редактированию, после этого цикл повторяется .

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

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

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

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

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

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

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

Если в результате работы алгоритмом выполняется k сравнений. Ответом на сравнение этих элементов a и b может быть один из двух вариантов (a<b или a>b). Тоесть, всего возможно 2k варианта комбинаций ответа на k вопросов.

Количество изменений из n элементов равно n!. Чтобы можно было провести сюръекцию из множества ответов на сравнения на множество перестановок, количество сравнений должно больше, чем log2n!, это необходимо так как единственная разрешённая операция сравнение.

1.2. Моделирование сортировки данных в массиве.

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

1.Первый алгоритм «Сортировка пузырьком». Отличительной чертой этого алгоритма является в следующем: как только он пройдет первый внутрений цикл, то наибольший элемент массива всегда будет находится на Х-ой точке. На втором круге цикла, следующий по значению наибольший элемент встанет на Х-1 точку, и т.д. Тем самым, при каждом круге цикла, каждое последуйщее наибольший элемент будет уменьшается на 1 и небудет потребности «проходить» весь массив каждый раз по новой.

В результате, раз подмассиву из одного элемента не нужно проходить сортировку, то для сортировки нужно применять менее Х-1 итераций внешнего цикла. Изза этого иногда в реализациях внешний цикл выполняется ровно Х-1 и не отслеживается, выполнение обмена на каждой итерации.

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

Пример кода более улучшего алгоритма с уже проверкой выполненых перестановок во внутреннем цикле алгоритма массива.

На входе: массив A[N], состоящий из N элементов, с числами от A[1] до A[N]

Пример кода алгоритма сортировки 1. Цикл.

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

Случаи когда не улучшается:

Количество сравнений в теле цикла равно (N-1) N÷2.

Количество сравнений в заголовках циклов (N-1) N÷2.

Общее количество сравнений равно (N-1)N.

Количество присваиваний в заголовках циклов равно (N-1) N÷2..