AceSorting  0.2
Sorting algorithms for Arduino (Bubble Sort, Insertion Sort, Shell Sort, Comb Sort, Quick Sort)
combSort.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_COMB_SORT_H
32 #define ACE_SORTING_COMB_SORT_H
33 
34 #include "swap.h"
35 
36 namespace ace_sorting {
37 
49 template <typename T>
50 void combSort13(T data[], uint16_t n) {
51  bool swapped = true;
52 
53  uint16_t gap = n;
54  while (swapped || gap > 1) {
55  gap = gap * 10 / 13;
56  if (gap == 0) gap = 1;
57  swapped = false;
58 
59  uint16_t i;
60  uint16_t j;
61  for (i = 0, j = gap; j < n; i++, j++) {
62  if (data[i] > data[j]) {
63  swap(data[i], data[j]);
64  swapped = true;
65  }
66  }
67  }
68 }
69 
82 template <typename T>
83 void combSort13m(T data[], uint16_t n) {
84  bool swapped = true;
85 
86  uint16_t gap = n;
87  while (swapped || gap > 1) {
88  gap = gap * 10 / 13;
89  if (gap == 9 || gap == 10) {
90  gap = 11;
91  } else if (gap == 0) {
92  gap = 1;
93  }
94  swapped = false;
95 
96  uint16_t i;
97  uint16_t j;
98  for (i = 0, j = gap; j < n; i++, j++) {
99  if (data[i] > data[j]) {
100  swap(data[i], data[j]);
101  swapped = true;
102  }
103  }
104  }
105 }
106 
129 template <typename T>
130 void combSort133(T data[], uint16_t n) {
131  bool swapped = true;
132 
133  uint16_t gap = n;
134  while (swapped || gap > 1) {
135  gap = gap * 3 / 4;
136  if (gap == 0) gap = 1;
137  swapped = false;
138 
139  uint16_t i;
140  uint16_t j;
141  for (i = 0, j = gap; j < n; i++, j++) {
142  if (data[i] > data[j]) {
143  swap(data[i], data[j]);
144  swapped = true;
145  }
146  }
147  }
148 }
149 
161 template <typename T>
162 void combSort133m(T data[], uint16_t n) {
163  bool swapped = true;
164 
165  uint16_t gap = n;
166  while (swapped || gap > 1) {
167  gap = gap * 3 / 4;
168  if (gap == 9 || gap == 10) {
169  gap = 11;
170  } else if (gap == 0) {
171  gap = 1;
172  }
173  swapped = false;
174 
175  uint16_t i;
176  uint16_t j;
177  for (i = 0, j = gap; j < n; i++, j++) {
178  if (data[i] > data[j]) {
179  swap(data[i], data[j]);
180  swapped = true;
181  }
182  }
183  }
184 }
185 
186 }
187 
188 #endif
swap.h
ace_sorting::swap
void swap(T &a, T &b)
Swap the parameters.
Definition: swap.h:41
ace_sorting::combSort133
void combSort133(T data[], uint16_t n)
Comb sort using a gap factor of 4/3=1.33 (successive gap is multiplied by 3 / 4).
Definition: combSort.h:130
ace_sorting::combSort13
void combSort13(T data[], uint16_t n)
Comb sort using a gap factor of 1.3 (successive gap is multiplied by 10 / 13).
Definition: combSort.h:50
ace_sorting::combSort133m
void combSort133m(T data[], uint16_t n)
Same as combSort133() but modified so that a gap of 9 or 10 becomes gap=11 so that the final sequence...
Definition: combSort.h:162
ace_sorting::combSort13m
void combSort13m(T data[], uint16_t n)
Same as combSort13() with the modification that if the gap is 9 or 10, it is set to 11,...
Definition: combSort.h:83