core/library/algorithms/shell_sort.h

   1 #ifndef SHELL_SORT_CLASS
   2 #define SHELL_SORT_CLASS
   3
   4 //////////////
   5 // Name   : shell_sort
   6 // Author : Chris Koeritz
   7 //////////////
   8 // Copyright (c) 1991-$now By Author.  This program is free software; you can
   9 // redistribute it and/or modify it under the terms of the GNU General Public
  10 // License as published by the Free Software Foundation:
  11 //     http://www.gnu.org/licenses/gpl.html
  12 // or under the terms of the GNU Library license:
  13 //     http://www.gnu.org/licenses/lgpl.html
  14 // at your preference.  Those licenses describe your legal rights to this
  15 // software, and no other rights or warranties apply.
  16 // Please send updates for this code to: fred@gruntose.com -- Thanks, fred.
  17 //////////////
  18
  19 namespace algorithms {
  20
  21 //! Orders an array in O(n log n) time.
  22 /*!
  23   This algorithm is based on Kernighan and Ritchie's "The C Programming Language".
  24 */
  25
  26 template <class type>
  27 void shell_sort(type v[], int n, bool reverse = false)
  28   //!< this function sorts a C array of the "type" with "n" elements.
  29   /*!< the "type" of object must support comparison operators.  if "reverse"
  30   is true, then the list is sorted highest to lowest. */
  31 {
  32   type temp;
  33   int gap, i, j;
  34   // the gap sizes decrease quadratically(?).  they partition the array of
  35   // items that need to be sorted into first two groups, then four, then
  36   // eight, ....
  37   // within each gap's worth of the array, the next loop takes effect...
  38   for (gap = n / 2; gap > 0; gap /= 2) {
  39     // the i indexed loop is the base for where the comparisons are made in
  40     // the j indexed loop.  it makes sure that each item past the edge of
  41     // the gap sized partition gets considered.
  42     for (i = gap; i < n; i++) {
  43       // the j indexed loop looks at the values in our current gap and ensures
  44       // that they are in sorted order.
  45       if (!reverse) {
  46         // normal ordering.
  47         for (j = i - gap; j >= 0 && v[j] > v[j + gap]; j = j - gap) {
  48           // swap the elements that are disordered.
  49           temp = v[j]; v[j] = v[j + gap]; v[j + gap] = temp;
  50         }
  51       } else {
  52         // reversed ordering.
  53         for (j = i - gap; j >= 0 && v[j] < v[j + gap]; j = j - gap) {
  54           // swap the elements that are disordered.
  55           temp = v[j]; v[j] = v[j + gap]; v[j + gap] = temp;
  56         }
  57       }
  58     }
  59   }
  60 }
  61
  62 } // namespace.
  63
  64 #endif // outer guard.
  65