Понятие алгоритма и сортировки. Способы и алгоритмы сортировки массивов. Быстрая сортировка Хоара. Описание алгоритма "быстрой сортировки". Реализация на языке программирования. Анализ наихудшего разбиения. Вероятностные алгоритмы быстрой сортировки.
Краткое сожержание материала:

Размещено на

Размещено на

Министерство образования республики Беларусь

УО “Мозырский государственный университет имени И. П. Шамякина”

Кафедра информатики и методики преподавания информатики

Курсовая работа

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

Выполнила:

студентка 3 курса 1 группы

физико-математического

факультета

Савенко Елена Николаевна

Научный руководитель:

Доцент кафедры информатики и методики преподавания информатики, кандидат физико - математических наук

Сергиевич Николай Владимирович

Мозырь 2007

Содержание

• Введение
• Глава 1. Основные теоретические аспекты алгоритма и сортировки
• 1.1 Понятие алгоритма и сортировки
• 1.2 Основные способы и алгоритмы сортировки массивов
• 1.3 Быстрая сортировка Хоара
• 1.4 Основные правила, понятия и теоремы
• 1.5 Псевдокод
• Глава 2. Реализация алгоритма «быстрой сортировки»
• 2.1 Описание алгоритма «быстрой сортировки»
• 2.2 Реализация на языке программирования
• Глава 3. Анализ быстрой сортировки
• 3.1Анализ наихудшего разбиения
• 3.2 Наилучшее разбиение
• 3.3Промежуточный случай
• 3.4 Вероятностные алгоритмы быстрой сортировки
• 3.5 Нахождение и анализ среднего времени работы сортировки
• 3.5.1 Интуитивные соображения по нахождению среднего времени
• 3.5.2 Анализ среднего времени работы
• Введение
• В последние годы программирование для вычислительных машин стало не только средством, владение которым оказывается решающим для успешной работы во многих прикладных областях, а так же и предметом научного изучения. Стало ясно, что решение о структурировании данных нельзя принимать без знания алгоритмов. Так же с каждым годом жизнь становится все быстрее и быстрее, ускоряется и увеличивается поток информации. Для хранения всевозможной информации применяются так называемые базы данных. Но и с этими базами, особенно если они содержат миллионы пунктов, работать достаточно сложно, можно даже сказать невозможно. Разобраться в таком количестве данных без сортировки практически не возможно, они позволяют относительно быстро и качественно выделить необходимую информацию из предварительно упорядоченного набора. Следовательно, методы сортировки очень важны, особенно при обработке данных. В программировании уделяется огромное внимание сортировкам и их алгоритмам.
• В настоящее время существует огромное множество алгоритмов сортировки, которые имеют различный характер и скорость обработки информации. Однако многие из них обладают очень серьезным недостатком, а именно, время их выполнения пропорционально квадрату числа элементов. Для больших объемов данных эти сортировки будут медленными, а, начиная с некоторой величины, они будут слишком медленными, чтобы их можно было использовать на практике.
• В данной курсовой работе будем рассматривать одну из лучших сортировок. Которая носит название быстрая сортировка, алгоритм которой признан наилучшим.
• Целью курсовой работы является изучение современных технологий программирования и анализ алгоритма быстрой сортировки Хоара.
• Задачи курсовой работы:
• 1. изучить теоретическую основу алгоритмов сортировки;
• 2. рассмотреть алгоритм быстрой сортировки Хоара;
• 3. реализовать его на языке программирования;
• 4. произвести анализ работы сортировки.

Глава 1. Основные теоретические аспекты алгоритма и сортировки

1.1 Понятие алгоритма и сортировки

Алгоритм (algorithm) -- это любая корректно определенная вычислительная процедура, на вход (input), которой подается некоторая величина или набор величин, и результатом выполнения которой является выходная (output) величина или набор значений. Таким образом, алгоритм представляет собой последовательность вычислительных шагов, преобразующих входные величины в выходные.

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

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

Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убывания их значений. Например, список L из n элементов будет отсортирован в порядке возрастания значений элементов, если L1 <= L2 <= ... <= Ln.

Цель сортировки - облегчить поиск элементов в отсортированном множестве. В этом смысле элементы сортировки присутствуют почти во всех задачах. Упорядоченные объекты содержатся в телефонной книге, в оглавлениях, в библиотеках, в словарях, да почти всюду. Даже маленьких детей приучают привадить вещи «в порядок», и они сталкиваются с некоторым видом сортировки за долго до того, как узнают что-либо об арифметике.

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

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

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

1.2 Основные способы и алгоритмы сортировки массивов

В этой курсовой работе будет рассмотрена только сортировку массивов, которая имеет три основных способа:

· сортировка обменом;

· сортировка выбором;

· сортировка вставкой.

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

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

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

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

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

· с какой средней скоростью этот алгоритм сортирует информацию?;

· какова скорость для лучшего случая и для худшего случая?;

· поведение алгоритма является естественным или является не естественным?;

· выполняется ли перестановка элементов для одинаковых ключей?

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

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

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