AceSorting
0.2
Sorting algorithms for Arduino (Bubble Sort, Insertion Sort, Shell Sort, Comb Sort, Quick Sort)
src
ace_sorting
selectionSort.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_SELECTION_SORT_H
32
#define ACE_SORTING_SELECTION_SORT_H
33
34
#include "
swap.h
"
35
36
namespace
ace_sorting {
37
44
template
<
typename
T>
45
void
selectionSort
(T data[], uint16_t n) {
46
for
(uint16_t i = 0; i < n; i++) {
47
48
// Loop to find the smallest element.
49
uint16_t iSmallest = i;
50
T smallest = data[i];
51
52
// Starting the loop with 'j = i + 1' increases flash usage on AVR by 12
53
// bytes. But it does not reduce the execution time signficantly, because
54
// the (i + 1) will be done anyway by the j++ in the loop. So the only thing
55
// we save is a single redundant 'smallest < smallest' comparison.
56
for
(uint16_t j = i; j < n; j++) {
57
if
(data[j] < smallest) {
58
iSmallest = j;
59
smallest = data[j];
60
}
61
}
62
63
// This extra check (i != iSmallest) is not really necessary, because if the
64
// first element was already the smallest, it would swap the value back into
65
// itself. However, the one situation where Selection Sort *might* be used
66
// over Insertion Sort is when the write operation is far more expensive
67
// than a read operation. So this test preserves that advantage of the
68
// Selection Sort, by avoiding doing an unnecessary swap.
69
if
(i != iSmallest) {
70
swap
(data[i], data[iSmallest]);
71
}
72
}
73
}
74
75
}
76
77
#endif
swap.h
ace_sorting::swap
void swap(T &a, T &b)
Swap the parameters.
Definition:
swap.h:41
ace_sorting::selectionSort
void selectionSort(T data[], uint16_t n)
Selection sort.
Definition:
selectionSort.h:45
Generated by
1.8.17