Jolt Physics
A multi core friendly Game Physics Engine
Loading...
Searching...
No Matches
InsertionSort.h
Go to the documentation of this file.
1// Jolt Physics Library (https://github.com/jrouwe/JoltPhysics)
2// SPDX-FileCopyrightText: 2022 Jorrit Rouwe
3// SPDX-License-Identifier: MIT
4
5#pragma once
6
8
10template <typename Iterator, typename Compare>
11inline void InsertionSort(Iterator inBegin, Iterator inEnd, Compare inCompare)
12{
13 // Empty arrays don't need to be sorted
14 if (inBegin != inEnd)
15 {
16 // Start at the second element
17 for (Iterator i = inBegin + 1; i != inEnd; ++i)
18 {
19 // Move this element to a temporary value
20 auto x = std::move(*i);
21
22 // Check if the element goes before inBegin (we can't decrement the iterator before inBegin so this needs to be a separate branch)
23 if (inCompare(x, *inBegin))
24 {
25 // Move all elements to the right to make space for x
26 Iterator prev;
27 for (Iterator j = i; j != inBegin; j = prev)
28 {
29 prev = j - 1;
30 *j = *prev;
31 }
32
33 // Move x to the first place
34 *inBegin = std::move(x);
35 }
36 else
37 {
38 // Move elements to the right as long as they are bigger than x
39 Iterator j = i;
40 for (Iterator prev = j - 1; inCompare(x, *prev); j = prev, --prev)
41 *j = std::move(*prev);
42
43 // Move x into place
44 *j = std::move(x);
45 }
46 }
47 }
48}
49
51template <typename Iterator>
52inline void InsertionSort(Iterator inBegin, Iterator inEnd)
53{
54 std::less<> compare;
55 InsertionSort(inBegin, inEnd, compare);
56}
57
#define JPH_NAMESPACE_END
Definition: Core.h:367
#define JPH_NAMESPACE_BEGIN
Definition: Core.h:361
JPH_NAMESPACE_BEGIN void InsertionSort(Iterator inBegin, Iterator inEnd, Compare inCompare)
Implementation of the insertion sort algorithm.
Definition: InsertionSort.h:11