AceSorting  0.1.0
Sorting algorithms for Arduino (Bubble Sort, Insertion Sort, Shell Sort, Comb Sort, Quick Sort)
shellSort.h
Go to the documentation of this file.
1 /*
2 MIT License
3 
4 Copyright (c) 2021 Brian T. Park
5 
6 Permission is hereby granted, free of charge, to any person obtaining a copy
7 of this software and associated documentation files (the "Software"), to deal
8 in the Software without restriction, including without limitation the rights
9 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 copies of the Software, and to permit persons to whom the Software is
11 furnished to do so, subject to the following conditions:
12 
13 The above copyright notice and this permission notice shall be included in all
14 copies or substantial portions of the Software.
15 
16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 SOFTWARE.
23 */
24 
31 #ifndef ACE_SORTING_SHELL_SORT_H
32 #define ACE_SORTING_SHELL_SORT_H
33 
34 #include "swap.h"
35 
36 namespace ace_sorting {
37 
45 template <typename T>
46 void shellSortClassic(T data[], uint16_t n) {
47  uint16_t gap = n;
48  while (gap > 1) {
49  gap = (gap + 1) / 2;
50 
51  // Do insertion sort of each sub-array separated by gap.
52  for (uint16_t i = gap; i < n; i++) {
53  T temp = data[i];
54 
55  // Shift one slot to the right.
56  uint16_t j;
57  for (j = i; j >= gap; j -= gap) {
58  if (data[j - gap] <= temp) break;
59  data[j] = data[j - gap];
60  }
61 
62  // Just like insertionSort(), this can assign 'temp' back into the
63  // original slot if no shifting was done. That's ok because T is assumed
64  // to be relatively cheap to copy, and checking for (i != j) is more
65  // expensive than just doing the extra assignment.
66  data[j] = temp;
67  }
68  }
69 }
70 
77 template <typename T>
78 void shellSortKnuth(T data[], uint16_t n) {
79  // Calculate the largest gap using Knuth's formula. If n is a compile-time
80  // constant and relatively "small" (observed to be true at least up to 100),
81  // the compiler will precalculate the loop below and replace it with a
82  // compile-time constant.
83  uint16_t gap = 1;
84  while (gap < n / 3) {
85  gap = gap * 3 + 1;
86  }
87 
88  while (gap > 0) {
89  // Do insertion sort of each sub-array separated by gap.
90  for (uint16_t i = gap; i < n; i++) {
91  T temp = data[i];
92 
93  // Shift one slot to the right.
94  uint16_t j;
95  for (j = i; j >= gap; j -= gap) {
96  if (data[j - gap] <= temp) break;
97  data[j] = data[j - gap];
98  }
99 
100  // Just like insertionSort(), this can assign 'temp' back into the
101  // original slot if no shifting was done. That's ok because T is assumed
102  // to be relatively cheap to copy, and checking for (i != j) is more
103  // expensive than just doing the extra assignment.
104  data[j] = temp;
105  }
106 
107  gap = (gap - 1) / 3;
108  }
109 }
110 
118 template<typename T>
119 void shellSortTokuda(T data[], const uint16_t n)
120 {
121  // Experimentally observed ideal gaps.
122  // https://en.wikipedia.org/wiki/Shellsort
123  // https://oeis.org/A108870
124  static const uint16_t sGaps[] = {
125  1, 4, 9, 20, 46, 103, 233, 525, 1182, 2660, 5985, 13467, 30301,
126  };
127  const uint16_t nGaps = sizeof(sGaps) / sizeof(uint16_t);
128 
129  // Find the starting gap.
130  uint16_t iGap;
131  for (iGap = 0; sGaps[iGap] < n && iGap < nGaps; iGap++) {}
132  if (iGap != 0) iGap--;
133 
134  while (true) {
135  uint16_t gap = sGaps[iGap];
136 
137  // Do insertion sort of each sub-array separated by gap.
138  for (uint16_t i = gap; i < n; i++) {
139  T temp = data[i];
140 
141  // Shift one slot to the right.
142  uint16_t j;
143  for (j = i; j >= gap; j -= gap) {
144  if (data[j - gap] <= temp) break;
145  data[j] = data[j - gap];
146  }
147 
148  // Just like insertionSort(), this can assign 'temp' back into the
149  // original slot if no shifting was done. That's ok because T is assumed
150  // to be relatively cheap to copy, and checking for (i != j) is more
151  // expensive than just doing the extra assignment.
152  data[j] = temp;
153  }
154 
155  if (iGap == 0) break;
156  iGap--;
157  }
158 }
159 
160 }
161 
162 #endif
swap.h
ace_sorting::shellSortTokuda
void shellSortTokuda(T data[], const uint16_t n)
Shell sort using gap sizes empirically determined by Tokuda.
Definition: shellSort.h:119
ace_sorting::shellSortKnuth
void shellSortKnuth(T data[], uint16_t n)
Shell sort using gap size from Knuth.
Definition: shellSort.h:78
ace_sorting::shellSortClassic
void shellSortClassic(T data[], uint16_t n)
Shell sort with gap size reduced by factor of 2 each iteration.
Definition: shellSort.h:46