Файл: Курсовая работа Алгоритм быстрой сортировки студентка 3 курса 1 группы физикоматематического факультета.rtf

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

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

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

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

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

Выполнила:

студентка 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 Основные способы и алгоритмы сортировки массивов

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

---

• 
  сортировка обменом;
  
• 
  сортировка выбором;
  
• 
  сортировка вставкой.
  

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

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

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

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

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

• 
  с какой средней скоростью этот алгоритм сортирует информацию?;
  
• 
  какова скорость для лучшего случая и для худшего случая?;
  
• 
  поведение алгоритма является естественным или является не естественным?;
  
• 
  
  выполняется ли перестановка элементов для одинаковых ключей?
  

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

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

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

---

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

Наиболее известной (и наиболее "бесславной") является сортировка пузырьковым методом. Ее популярность объясняется запоминающимся названием и простотой алгоритма. Однако эта сортировка является одной из самых худших среди всех когда-либо придуманных сортировок. Сортировка пузырьковым методом использует метод обменной сортировки. Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов.

При сортировке выбором выбирается элемент с наименьшим значением и делается его обмен с первым элементом массива. Затем находится элемент с наименьшим значением из оставшихся n-1 элементов и делается его обмен со вторым элементом и т.д. до обмена двух последних элементов.

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

1.3 Быстрая сортировка Хоара

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

Если сортировка выполняется слишком долго, то причиной этого может быть используемый алгоритм. Однако первая реакция на такое поведение сортировки выражается словами: "Давай напишем программу на ассемблере". Хотя использование ассемблера почти всегда позволяет повысить быстродействие программы в некоторое число раз с постоянным коэффициентом, но если выбранный алгоритм не является достаточно хорошим, то сортировка вне зависимости от оптимальности кода по-прежнему будет выполняться долго. Следует помнить, что при квадратичной зависимости времени выполнения программы от числа элементов массива повышение оптимальности кода или повышение быстродействия ЭВМ приведет лишь к незначительному улучшению, поскольку время выполнения программы будет увеличиваться по экспоненте. Следует помнить, что если какая-либо программа, написанная на языке Паскаль, выполняется недостаточно быстро, то она не станет выполняться достаточно быстро, если ее написать на ассемблере. Решение лежит в использовании лучшего алгоритма сортировки.

---