1.4Сортировка

Сортировка - процесс перегруппировки заданного множества (массива) объектов в некотором определенном порядке (например, по алфавиту). Цель сортировки - облегчить последующий поиск объектов в таком отсортированном множестве.

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

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

При выборе метода сортировки массива важнейшим фактором (как и во всех других случаях) является его экономичность, то есть время его работы. Мерой эффективности может быть C - число необходимых сравнений ключей и M - число необходимых перестановок элементов. Естественно, что эти величины функционально зависят от n - числа сортируемых элементов. Простые методы требуют порядка n² сравнений ключей, тогда как улучшенные методы (сложные) позволяют сократить это число до .

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

При n =1000, С =250250, M =252250.

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

1. Из массива выбирается элемент с наименьшим значением.

2. Он меняется местами с первым элементом.

3. Затем этот процесс повторяется с оставшимися элементами и так до тех пор, пока не останется один самый большой элемент.

Число сравнений не зависит от изначального порядка элементов: .

Среднее число перестановок:

где g = 0.577216 – константа Эйлера.

При n = 1000, С = 499500, M = 7485.

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

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

При этом, данный метод - самый неэффективный. Число сравнений не зависит от изначального порядка элементов: .

Среднее число перестановок: .

При n =1000, С =499500, M =749250.

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

Рассмотрим улучшенный метод "пузырьковой сортировки". Если учесть, что пузырьковая сортировка является самым неэффективным методом из трех алгоритмов прямой сортировки, то удивительно, что некоторое улучшение метода приводит к самому лучшему из известных в данный момент методу сортировки массивов. Его производительность столь впечатляюща, что его изобретатель Ч. Хоар даже назвал метод «быстрой сортировкой» (Quicksort).

Алгоритм быстрой сортировки сводится к следующим действиям:

1. Выберем наугад какой-либо элемент массива (лучше, если это будет медиана или среднее значение массива). Назовем его Х.

2. Будем просматривать массив слева до тех пор, пока не обнаружим элемент меньше Х (a_i<X). Затем будем просматривать массив справа, пока не встретим элемент больше Х (a_j>X).

3. Поменяем местами найденные элементы.

4. Продолжим процесс просмотра и обмена, пока оба просмотра не встретятся где-то в середине массива.

В результате массив окажется разбитым на две части: левую с элементами меньше (или равными) Х и правую - больше (или равными) Х.

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

Если в качестве границы все время выбирать медиану, то число сравнений равно , а число обменов - . При n =1000, С =6908, M =1151.

(При пузырьковой сортировке - С = 499500, M = 749250).

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