shell_sort.h

Go to the documentation of this file.

#ifndef SHELL_SORT_CLASS
#define SHELL_SORT_CLASS

/*****************************************************************************\
*                                                                             *
*  Name   : shell_sort                                                        *
*  Author : Chris Koeritz                                                     *
*                                                                             *
*******************************************************************************
* Copyright (c) 1991-$now By Author.  This program is free software; you can  *
* redistribute it and/or modify it under the terms of the GNU General Public  *
* License as published by the Free Software Foundation; either version 2 of   *
* the License or (at your option) any later version.  This is online at:      *
*     http://www.fsf.org/copyleft/gpl.html                                    *
* Please send any updates to: fred@gruntose.com                               *
\*****************************************************************************/

#include "definitions.h"


template <class type>
void shell_sort(type v[], int n, bool reverse = false)

{
  type temp;
  int gap, i, j;
  // the gap sizes decrease quadratically(?).  they partition the array of
  // items that need to be sorted into first two groups, then four, then
  // eight, ....
  // within each gap's worth of the array, the next loop takes effect...
  for (gap = n / 2; gap > 0; gap /= 2) {
    // the i indexed loop is the base for where the comparisons are made in
    // the j indexed loop.  it makes sure that each item past the edge of
    // the gap sized partition gets considered.
    for (i = gap; i < n; i++) {
      // the j indexed loop looks at the values in our current gap and ensures
      // that they are in sorted order.
      if (!reverse) {
        // normal ordering.
        for (j = i - gap; j >= 0 && v[j] > v[j + gap]; j = j - gap) {
          // swap the elements that are disordered.
          temp = v[j];
          v[j] = v[j + gap];
          v[j + gap] = temp;
        }
      } else {
        // reversed ordering.
        for (j = i - gap; j >= 0 && v[j] < v[j + gap]; j = j - gap) {
          // swap the elements that are disordered.
          temp = v[j];
          v[j] = v[j + gap];
          v[j + gap] = temp;
        }
      }
    }
  }
}

#endif // outer guard.

---