3 {

4 unsigned long j, k;

5 Т v = data[right]; // запоминаем правый элемент

6 j = left - 1;

7 k = right;

8 do (

9 while( data[++j] < v);

10 while( data[—k] > v);

11 iff j >= k) break;

12 Swap(data[j], data[k]);

13 } whiled);

14 •Swap(data[j], data [right]).;

15 return j;

16 }

Функция RecursiveQuickSort вызывает функцию Partition, возвращающую серединный индекс, а затем рекурсивно вызывает себя для верхней и нижней частей.

1 // Быстрая сортировка

2 template <class T>

3 void RecursiveQuickSort( Т data[], unsigned long left, ^unsigned long right)

4 <

5 unsigned long j ;

6 if( right > left) 1 [

8 j = Partition(data, left, right);

9 RecursiveQuickSort(data, left, j-1);

10: RecursiveQuickSort(data, j+1, right);

11: } 12: )

Шаблон быстрой сортировки реализован на основе алгоритма, приведенного в книге Robert Sedgewick Algorithms in C++ (Addison- Wesley, 1992, pp.115—119). Некоторая модификация выразилась в использовании беззнакового индекса, выполняющего в строке 10 в функции partition роль ограничителя по нулевому значению.

Этот раздел показывает, как достаточно сложные алгоритмы могут быть реализованы в виде шаблонов. Не забудьте, что темой обсуждения настоящей главы являются не алгоритмы сами по себе, а шаблоны, как выразительное средство языка C++.

Обзор родовых классов

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