// Purpose.  Template Method            // Discussion.  On the left, we're
                                         // starting with 2 sorts that are very
 #include <iostream.h>                   // similar.  If we could "customize" a
 #include <stdlib.h>                     // single sort implementation, we could
 #include <time.h>                       // enjoy reuse.  "Template Method de-
                                         // fines an algorithm in terms of ab-
 class SortUp {  ///// Shell sort /////  // stract operations that subclasses
 public:                                 // override to provide concrete beha-
    void doIt( int v[], int n ) {        // vior."  Here, doIt() is the algo-
       for (int g = n/2; g > 0; g /= 2)  // rithm, and needSwap() is the ab-
          for (int i = g; i < n; i++)    // stract operation.
             for (int j = i-g; j >= 0;
                               j -= g)   class Sort {  ////// Shell sort //////
                if (v[j] > v[j+g])       public:
                   doSwap(v[j],v[j+g]);     void doIt( int v[], int n ) {
    }                                          for (int g = n/2; g > 0; g /= 2)
 private:                                         for (int i = g; i < n; i++)
    void doSwap(int& a,int& b) {                     for (int j = i-g; j >= 0;
       int t = a; a = b; b = t; }                                      j -= g)
 };                                                     if (needSwap(v[j],
                                                                     v[j+g]))
 class SortDown {                                          doSwap(v[j],
 public:                                                          v[j+g]);
    void doIt( int v[], int n ) {           }
       for (int g = n/2; g > 0; g /= 2)  private:
          for (int i = g; i < n; i++)       virtual int needSwap(int,int) = 0;
             for (int j = i-g; j >= 0;      void doSwap(int& a,int& b) {
                               j -= g)         int t = a; a = b; b = t; }
                if (v[j] < v[j+g])       };
                   doSwap(v[j],v[j+g]);
    }                                    class SortUp : public Sort {
 private:                                   int needSwap(int a, int b) {
    void doSwap(int& a,int& b) {               return (a > b); }
       int t = a; a = b; b = t; }        };
 };                                      class SortDown : public Sort {
                                            int needSwap(int a, int b) {
 void main( void )                             return (a < b); }
 {                                       };
    const int NUM = 10;
    int       array[NUM];                void main( void )
    time_t    t;                         {
    srand((unsigned) time(&t));             const int NUM = 10;
    for (int i=0; i < NUM; i++) {           int       array[NUM];
       array[i] = rand() % 10 + 1;          time_t    t;
       cout << array[i] << ' '; }           srand((unsigned) time(&t));
    cout << endl;                           for (int i=0; i < NUM; i++) {
                                               array[i] = rand() % 10 + 1;
    SortUp  upObj;                             cout << array[i] << ' '; }
    upObj.doIt( array, NUM );               cout << endl;
    for (int u=0; u < NUM; u++)
       cout << array[u] << ' ';             SortUp  upObj;
    cout << endl;                           upObj.doIt( array, NUM );
                                            for (int u=0; u < NUM; u++)
    SortDown  downObj;                         cout << array[u] << ' ';
    downObj.doIt( array, NUM );             cout << endl;
    for (int d=0; d < NUM; d++)
       cout << array[d] << ' ';             SortDown  downObj;
    cout << endl;                           downObj.doIt( array, NUM );
 }                                          for (int d=0; d < NUM; d++)
                                               cout << array[d] << ' ';
 // 3 10 5 5 5 4 2 1 5 9                    cout << endl;
 // 1 2 3 4 5 5 5 5 9 10                 }
 // 10 9 5 5 5 5 4 3 2 1
                                         // 1 6 6 2 10 9 4 10 6 4
                                         // 1 2 4 4 6 6 6 9 10 10
                                         // 10 10 9 6 6 6 4 4 2 1