Федеральное агентство по образованию

Государственное образовательное учреждение

Высшего профессионального образования

Донской государственный технический университет

Реферат

По дисциплине: «Теория алгоритмов»

На тему: «Алгоритмы сортировки»

Выполнила:

Ст. группы ВПМ-31

Бурлуцкая О.С

Проверил:

Баранов И.В

г. Ростов–на-Дону

2012 г.

Содержание

Введение

1. Методы сортировки

   1. Метод пузырька

   2. Сортировка выбором

   3. Сортировка вставкой

   4. Метод Шелла

   5. Быстрая сортировка (метод Хоара)

   6. Сортировка бинарным деревом

   7. Сортировка массивом (хероширование)

   8. Обменная поразрядная сортировка

Заключение

Список использованных источников

Введение

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

1. Методы сортировки

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

• Сравнение, определяющее упорядоченность пары элементов;

• Перестановка, меняющая местами пару элементов;

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

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

1.1.Метод пузырька

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

Если теперь повторить такой просмотр еще N – 1 раз, то, очевидно, что вся заданная последовательность окажется от сортированной. Этот алгоритм можно несколько оптимизировать двумя добовлениями:

1. Просматривая на k-м проходе не весь массив, а только элементы с первого до (N-k+1)-го;

2. Повторяя просмотр не N раз, а лишь до тех пор, пока при очередном просмотре не произойдет ни одной перестановки.