1 #ifndef SHELL_SORT_CLASS
2 #define SHELL_SORT_CLASS
6 // Author : Chris Koeritz
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.
19 namespace algorithms {
21 //! Orders an array in O(n log n) time.
23 This algorithm is based on Kernighan and Ritchie's "The C Programming Language".
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. */
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
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.
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;
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;
64 #endif // outer guard.