§ 5.5. Адаптация процессов сортировки массивов

Известно, что существует большое количество методов сортировки массива [105, 124, 148]. Они отличаются различными алгоритмами, условиями целесообразного применения и техникой реализации массива (на магнитных дисках, лентах и т. д.). Формальные признаки массива позволяют несколько снизить разнообразие возможных методов сортировки, но не снимают проблему выбора. Если в распоряжении пользователя имеется несколько альтернативных программ сортировки, относительно выбора одной из которых у него нет априорных соображений, то ему следует воспользоваться методом альтернативной адаптации.

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

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

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

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

а при массив полностью упорядочен:

Рассмотрим для конкретности два алгоритма сортировки:

1. Алгоритм «min». В соответствии с этим алгоритмом на каждом этапе сортировки определяется минимальный элемент массива который переносится в новый список, а оставшийся массив перенумеровывается. Иначе говоря, массив укорачивается на единицу так, что первые элементов, сохраняются:

а последующие смещаются влево на единицу:

Легко видеть, что этот алгоритм быстрее сортирует массивы, близкие к обратноупорядоченным, чем к прямоупорядоченным (за счет уменьшения числа процедур смещения).

2. Алгоритм «пузырек». Этот алгоритм заключается в после довательном сравнении соседних элементов массива и их об мене при Критерием остановки является отсутствие обменов при просмотре всего массива. Алгоритм быстрее ботает на хорошо упорядоченных массивах.

На рис. 5.5.1 показаны временные характеристики обоих алгоритмов при сортировке массивов различной упорядоченности объемом на ЭВМ ЕС-1030. Из рисунка видно, что при следует использовать алгоритм «пузырек», а при

Используем для альтернативной адаптации сортировки алгоритм «двурукого бандита», описанный в подразделе 5.1.2.3. На рис. 5.5.2, а представлена динамика переключения с одного алгоритма, оптимального, на другой при скачкообразном изменении упорядоченности сортируемых массивов от до

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

Рис. 5.5.1. (см. скан) Временные характеристики сортировки при различной упорядоченности массива алгоритмами «min»-(а) и «пузырек» (б).

Рис. 5.5.2. (см. скан) Динамика работы алгоритма альтернативной адаптации процесса сортировки: а — при скачкообразном изменении коэффициента упорядоченности массивов, б - при линейном изменении.

Алгоритм начинает устойчиво выбирать оптимальный в данной ситуации алгоритм («min» при и «пузырек» — при ).

Динамика адаптации (рис. 5.5.2, б) при непрерывном измелении во времени упорядоченности сортируемых массивов:

где k — номер очередного массива, показывает, что алгоритм адаптации уверенно «включает» алгоритм, оптимальный в сложившейся ситуации с.

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

Описанные алгоритмы альтернативной адаптации применимы лишь в том случае, когда число конкурирующих альтернатив крайне мало (2—5). Если их число велико, то надо использовать алгоритмы эволюционной адаптации, описанные в следующей главе.