1 //////////////////////////////////////////////////////////////////////////////
4 // ADLib, Prop and their related set of tools and documentation are in the
5 // public domain. The author(s) of this software reserve no copyrights on
6 // the source code and any code generated using the tools. You are encouraged
7 // to use ADLib and Prop to develop software, in both academic and commercial
8 // settings, and are free to incorporate any part of ADLib and Prop into
11 // Although you are under no obligation to do so, we strongly recommend that
12 // you give away all software developed using our tools.
14 // We also ask that credit be given to us when ADLib and/or Prop are used in
15 // your programs, and that this notice be preserved intact in all the source
18 // This software is still under development and we welcome any suggestions
19 // and help from the users.
23 //////////////////////////////////////////////////////////////////////////////
28 #include <AD/sort/sorting.h>
30 // Shell sort\cite{algo-hand-book}
32 // e.g: shellSort(char *, names, 100, strcmp(key,names[i]) < 0);
35 /////////////////////////////////////////////////////////////////////////////
37 /////////////////////////////////////////////////////////////////////////////
38 #define shellSort(TYPE,A,N,predicate) \
40 for ( register int gap = (N); gap > 1; ) { \
41 if (gap < 5) gap = 1; \
42 else gap = (5 * gap - 1) / 11; \
43 for (register int j = (N) - gap; j >= 0; j--) { \
44 register TYPE key = (A)[j]; \
45 for (register int i = j + gap; i < (N) && !(predicate); i += gap) \
46 (A)[i-gap] = (A)[i]; \
52 /////////////////////////////////////////////////////////////////////////////
54 /////////////////////////////////////////////////////////////////////////////
55 template <class T
, class Ord
>
56 class ShellSort
: public Sorting
<T
,Ord
> {
61 template <class T
, class Ord
>
62 void ShellSort
<T
,Ord
>::sort(int N
, T array
[])
63 { shellSort(T
, array
, N
, Ord::less(key
, array
[i
])); }