tetl 0.1.0
Embedded Template Library
Loading...
Searching...
No Matches
insertion_sort.hpp
Go to the documentation of this file.
1// SPDX-License-Identifier: BSL-1.0
2// SPDX-FileCopyrightText: Copyright (C) 2023 Tobias Hienzsch
3
4#ifndef TETL_ALGORITHM_INSERTION_SORT_HPP
5#define TETL_ALGORITHM_INSERTION_SORT_HPP
6
7#include <etl/_algorithm/iter_swap.hpp>
8#include <etl/_functional/less.hpp>
9
10namespace etl {
11
12/// \brief Sorts the elements in the range `[first, last)` in non-descending
13/// order. The order of equal elements is guaranteed to be preserved.
14///
15/// https://en.wikipedia.org/wiki/Insertion_sort
16///
17/// \note Non-standard extension
18/// \ingroup algorithm
19template <typename RandomIt, typename Compare>
20constexpr auto insertion_sort(RandomIt first, RandomIt last, Compare comp) -> void
21{
22 for (auto i = first; i != last; ++i) {
23 auto key = *i;
24 auto j = i;
25 while (j != first and comp(key, *(j - 1))) {
26 *j = *(j - 1);
27 --j;
28 }
29 *j = key;
30 }
31}
32
33/// \note Non-standard extension
34/// \ingroup algorithm
35template <typename RandomIt>
36constexpr auto insertion_sort(RandomIt first, RandomIt last) -> void
37{
38 etl::insertion_sort(first, last, etl::less());
39}
40
41} // namespace etl
42
43#endif // TETL_ALGORITHM_INSERTION_SORT_HPP
constexpr auto insertion_sort(RandomIt first, RandomIt last, Compare comp) -> void
Sorts the elements in the range [first, last) in non-descending order. The order of equal elements is...
Definition insertion_sort.hpp:20
constexpr auto insertion_sort(RandomIt first, RandomIt last) -> void
Definition insertion_sort.hpp:36
Definition adjacent_find.hpp:9
Function object for performing comparisons. Unless specialised, invokes operator< on type T....
Definition less.hpp:15