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

Связь между бесконечно малыми и бесконечно большими величинами.

♦ Теорема 12.3.1) Если функция – бесконечно малая при , то функция является бесконечно большой при .

2) Если функция – бесконечно большая при , то функция является бесконечно малой при .

Доказательство.1) Пусть при – бесконечно малая, то есть . Таким образом, , отсюда , где , . Получаем, что функция – бесконечно большая.

2) Доказательство проводится аналогичным образом. ■

J Пример 12.7.1) при – бесконечно малая, а – бесконечно большая величина. При функция – бесконечно большая, а – бесконечно малая.

2) при – бесконечно малая, а – бесконечно большая.

3) при – бесконечно большая, а – бесконечно малая. J

Цель лекции: изучить основные алгоритмы внутренних сортировок и научиться решать задачи сортировок массивов различными методами (бинарная пирамидальная сортировка, метод Шелла, быстрая сортировка Хоара, сортировка слиянием).

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

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

Алгоритмом сортировки называется алгоритм для упорядочения некоторого множества элементов. Обычно под алгоритмом сортировки подразумевают алгоритм упорядочивания множества элементов по возрастанию или убыванию.

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

В алгоритмах сортировки лишь часть данных используется в качестве ключа сортировки. Ключом сортировки называется атрибут (или несколько атрибутов), по значению которого определяется порядок элементов. Таким образом, при написании алгоритмов сортировок массивов следует учесть, что ключ полностью или частично совпадает с данными.

Практически каждый алгоритм сортировки можно разбить на 3 части:

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

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

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

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