524____________________Часть III. Современное программирование на С++

В стенде имеется упрощенный класс TIMER. Класс наследуется как открытый из структуры time (глава 20), что позволяет классу TIMER прекрасно работать с библиотечными функциями, например gettime, использующими ту же структуру time. Класс TIMER запоминает системное время при создании объекта. У этого класса есть собственная функция форматированного вывода, являющаяся перегруженной функцией operator« (см. главы 13 и 16).

Строки 42—59 — это функция main, она же испытательный стенд наших шаблонов. Здесь демонстрируются примеры использования различных сортировок.

Предмет обсуждения данного раздела — сортировка методом выбора, определена в строках 11—24. Несложно заметить, что она похожа на пузырьковую сортировку (GumSort), за исключением того, что текущая позиция перестановки (swapAt) постоянно обновляется и используется при сравнении. Перестановка откладывается до строки 22, когда внутренний цикл for уже проверил все варианты.

Рекурсивный шаблон быстрой сортировки

Быстрая сортировка — чемпион скорости для больших случайных выборок. Порядок производительности оценивается для нее как 0(log2n)m, что означает, что скорость падает медленно даже при больших п (число элементов). Есть, однако, у этой сортировки и маленький недостаток. Если выборка частично упорядочена, то время сортировки возрастает до 0(п2).

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

Замечание

Эта книга — не справочник по алгоритмам. Есть много хороших книг по обработке и хранению данных. В них описано много больше алгоритмов сортировки и областей их применения, и куда более подробно. Если у вас возникли затруднения, то обратитесь к книге Numerical Recipes in С (Cambridge University Press, 1992).

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

1: template <class T> . 2: unsigned long Partition( Т data[], unsigned long left, ^unsigned long right)