Такие результаты тестов не случайны[3], но мы договорились, что не будем затрагивать тонкости реализации, оставив их для разработчиков языков. Просто сортировка такова и результаты тестов таковы.

Самым важным и интересным для нас в этих тестах является то, что количество необходимых для сортировки актов сравнения возрастает непропорционально количеству элементов в списке. То есть для сортировки случайной последовательности из 10 элементов необходимо (в среднем) 23 сравнения, а для сортировки подобного списка из 10 000 элементов необходимо не 23 000 сравнений, а в шесть(!) раз больше – 136 000. Обратите внимание, эта закономерность выполняется для любых списков, независимо от их начальной упорядоченности.

Здесь-то перед программистом и открывается кажущийся бескрайним простор для оптимизации кода. Давайте перейдём от сухой теории к практическим рецептам (пока тоже достаточно сухим).

Сортировка в Perl и её оптимизация

Для сортировки массивов и списков в Perl предусмотрена встроенная функция sort, которая в самой простой своей форме может использоваться так:

Листинг 1

# Элементарное применение функции sort

@sorted = sort @unsorted;

В результате выполнения этой команды элементы массива @unsorted сортируются по алфавиту и новый, сортированный, список помещается в массив @sorted[4].

Ценность функции sort для программиста была бы не велика, если бы это была единственная её форма, но, к счастью, функция sort допускает формулирование любого критерия сортировки. Вторая форма такова:

Листинг 2

# Функция sort с заданным критерием сортировки

@sorted = sort {...} @unsorted;

При каждом сравнении в блоке операторов {...} автоматически создаются две локальные[5] переменные $a и $b, которые являются синонимами сравниваемых элементов исходного списка @unsorted. Из-за этой синонимичности менять значение этих переменных весьма нежелательно, это приведёт к изменения соответствующих элементов списка @unsorted и может сбить sort с толку. Результат выполнения блока интерпретируется так же, как результат выполнения операторов <=> и cmp. То есть блок сообщает, какой из двух элементов следует считать меньшим.