-
Notifications
You must be signed in to change notification settings - Fork 2.1k
/
Copy pathSortUtils.h
63 lines (56 loc) · 1.56 KB
/
SortUtils.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
*
* Copyright (c) 2020-2021 Project CHIP Authors
* Copyright (c) 2013-2017 Nest Labs, Inc.
* All rights reserved.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#pragma once
#include <algorithm>
#include <stdint.h>
#include <stdlib.h>
namespace chip {
namespace Sorting {
/**
*
* Impements the insertion sort algorithm to sort an array
* of items of size 'n'.
*
* The provided comparison function SHALL have the following signature:
*
* bool Compare(const T& a, const T& b);
*
* If a is deemed less than (i.e is ordered before) b, return true.
* Else, return false.
*
* This is a stable sort.
*
*/
template <typename T, typename CompareFunc>
void InsertionSort(T * items, size_t n, CompareFunc f)
{
for (size_t i = 1; i < n; i++)
{
const T key = items[i];
int j = static_cast<int>(i) - 1;
while (j >= 0 && f(key, items[j]))
{
items[j + 1] = items[j];
j--;
}
items[j + 1] = key;
}
}
} // namespace Sorting
} // namespace chip