ГЛАВА 3. ЭЛЕМЕНТЫ ЧИСЛЕННЫХ МЕТОДОВ

ГЛАВА 3. ЭЛЕМЕНТЫ ЧИСЛЕННЫХ МЕТОДОВ.

3.1. “СТАНДАРТНЫЕ” АЛГОРИТМЫ СОРТИРОВКИ ОДНОМЕРНЫХ МАССИВОВ.

Основная цель сортировки - облег­чить последующий поиск элементов в таком упорядоченном массиве. Примерами упорядоченных объектов являются:

а) размещение книг в хранилищах библиотек;

б) расположение товаров на складах;

в) номера в телефонных справочниках и т.д.

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

i <= i <= ... <= i

в порядке возрастания элементов, если

i < i < ... < i

в порядке невозрастания элементов, если

i >= i >= ... >= i
в порядке убывания элементов, если

i > i > ... > i

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

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