Введение. Сортировка - это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >

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

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

· точность решения задачи

· затраты машинного времени

· затраты оперативной памяти

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

· минимально возможное число повторов элементарных операций в наилучшем случае

· среднее число повторов

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

Например, в задаче поиска в неупорядоченном массиве или списке из n элементов базовой операцией является сравнение заданного значения с ключом элемента массива. Тогда минимальное число сравнений равно 1 (совпадение произошло на первом элементе массива), максимальное равно n (просмотрен весь массив), а среднее - около n/2.

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

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

Для оценивания трудоемкости алгоритмов была введена специальная система обозначений – так называемая О-нотация. Эта нотация позволяет учитывать в функции f (n) лишь наиболее значимые элементы, отбрасывая второстепенные.

Например, в функции f (n) = 2n² + n – 5 при достаточно больших n компонента n² будет значительно превосходить остальные слагаемые, и поэтому характерное поведение этой функции определяется именно этой компонентой. Остальные компоненты можно отбросить и условно записать, что данная функция имеет оценку поведения (в смысле скорости роста ее значений) вида О(n² ).

Важность О-оценивания состоит в том, что оно позволяет описывать характер поведения функции f(n) с ростом n: насколько быстро или медленно растет эта функция.

Отсюда можно сделать несколько выводов:

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

2. Если заранее известно, что размерность решаемых задач невелика, но зато число их повторений очень большое, имеет смысл рассмотреть возможность использования алгоритмов не с самой лучшей оценкой, поскольку при малых n “лучшие” алгоритмы могут вести себя хуже, чем “плохие”;

3. Алгоритмы класса О(2ⁿ) и О(n!) следует использовать с большой осторожностью, учитывая катастрофический рост их трудоемкости уже при n> 100. Например, если число базовых операций определяется соотношением 2ⁿ, то при n=100 это число будет примерно равно 10³⁰, и если одна базовая операция выполняется за 1 микросекунду, то это потребует около 10²⁴ секунд, т.е. порядка 10¹⁶ лет. К сожалению, задачи с подобной трудоемкостью довольно часто встречаются на практике и их точное решение пока невозможно даже на сверхбыстрых суперкомпьютерах.

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

Для достижения поставленной цели, необходимо решить следующие задачи:

I. Рассмотреть классификацию методов сортировки;

¾ анализ метода обмена;

¾ анализ метода выбора;

¾ анализ метода вставок;

¾ анализ метода Шелла;

¾ анализ метода быстрой сортировки.

II. Проанализировать вышеперечисленные методы сортировки, путем их практической реализации.