Jolt Physics
A multi core friendly Game Physics Engine
Loading...
Searching...
No Matches
QuickSort.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
10
12template <typename Iterator, typename Compare>
13inline void QuickSortMedianOfThree(Iterator inFirst, Iterator inMiddle, Iterator inLast, Compare inCompare)
14{
15 // This should be guaranteed because we switch over to insertion sort when there's 32 or less elements
16 JPH_ASSERT(inFirst != inMiddle && inMiddle != inLast);
17
18 if (inCompare(*inMiddle, *inFirst))
19 swap(*inFirst, *inMiddle);
20
21 if (inCompare(*inLast, *inFirst))
22 swap(*inFirst, *inLast);
23
24 if (inCompare(*inLast, *inMiddle))
25 swap(*inMiddle, *inLast);
26}
27
29template <typename Iterator, typename Compare>
30inline void QuickSortNinther(Iterator inFirst, Iterator inMiddle, Iterator inLast, Compare inCompare)
31{
32 // Divide the range in 8 equal parts (this means there are 9 points)
33 auto diff = (inLast - inFirst) >> 3;
34 auto two_diff = diff << 1;
35
36 // Median of first 3 points
37 Iterator mid1 = inFirst + diff;
38 QuickSortMedianOfThree(inFirst, mid1, inFirst + two_diff, inCompare);
39
40 // Median of second 3 points
41 QuickSortMedianOfThree(inMiddle - diff, inMiddle, inMiddle + diff, inCompare);
42
43 // Median of third 3 points
44 Iterator mid3 = inLast - diff;
45 QuickSortMedianOfThree(inLast - two_diff, mid3, inLast, inCompare);
46
47 // Determine the median of the 3 medians
48 QuickSortMedianOfThree(mid1, inMiddle, mid3, inCompare);
49}
50
52template <typename Iterator, typename Compare>
53inline void QuickSort(Iterator inBegin, Iterator inEnd, Compare inCompare)
54{
55 // Implementation based on https://en.wikipedia.org/wiki/Quicksort using Hoare's partition scheme
56
57 // Loop so that we only need to do 1 recursive call instead of 2.
58 for (;;)
59 {
60 // If there's less than 2 elements we're done
61 auto num_elements = inEnd - inBegin;
62 if (num_elements < 2)
63 return;
64
65 // Fall back to insertion sort if there are too few elements
66 if (num_elements <= 32)
67 {
68 InsertionSort(inBegin, inEnd, inCompare);
69 return;
70 }
71
72 // Determine pivot
73 Iterator pivot_iterator = inBegin + ((num_elements - 1) >> 1);
74 QuickSortNinther(inBegin, pivot_iterator, inEnd - 1, inCompare);
75 auto pivot = *pivot_iterator;
76
77 // Left and right iterators
78 Iterator i = inBegin;
79 Iterator j = inEnd;
80
81 for (;;)
82 {
83 // Find the first element that is bigger than the pivot
84 while (inCompare(*i, pivot))
85 i++;
86
87 // Find the last element that is smaller than the pivot
88 do
89 --j;
90 while (inCompare(pivot, *j));
91
92 // If the two iterators crossed, we're done
93 if (i >= j)
94 break;
95
96 // Swap the elements
97 swap(*i, *j);
98
99 // Note that the first while loop in this function should
100 // have been do i++ while (...) but since we cannot decrement
101 // the iterator from inBegin we left that out, so we need to do
102 // it here.
103 ++i;
104 }
105
106 // Include the middle element on the left side
107 j++;
108
109 // Check which partition is smaller
110 if (j - inBegin < inEnd - j)
111 {
112 // Left side is smaller, recurse to left first
113 QuickSort(inBegin, j, inCompare);
114
115 // Loop again with the right side to avoid a call
116 inBegin = j;
117 }
118 else
119 {
120 // Right side is smaller, recurse to right first
121 QuickSort(j, inEnd, inCompare);
122
123 // Loop again with the left side to avoid a call
124 inEnd = j;
125 }
126 }
127}
128
130template <typename Iterator>
131inline void QuickSort(Iterator inBegin, Iterator inEnd)
132{
133 std::less<> compare;
134 QuickSort(inBegin, inEnd, compare);
135}
136
#define JPH_NAMESPACE_END
Definition Core.h:378
#define JPH_NAMESPACE_BEGIN
Definition Core.h:372
JPH_NAMESPACE_BEGIN void InsertionSort(Iterator inBegin, Iterator inEnd, Compare inCompare)
Implementation of the insertion sort algorithm.
Definition InsertionSort.h:11
#define JPH_ASSERT(...)
Definition IssueReporting.h:33
void QuickSort(Iterator inBegin, Iterator inEnd, Compare inCompare)
Implementation of the quick sort algorithm. The STL version implementation is not consistent across p...
Definition QuickSort.h:53
void QuickSortNinther(Iterator inFirst, Iterator inMiddle, Iterator inLast, Compare inCompare)
Helper function for QuickSort using the Ninther method, will move the pivot element to inMiddle.
Definition QuickSort.h:30
JPH_NAMESPACE_BEGIN void QuickSortMedianOfThree(Iterator inFirst, Iterator inMiddle, Iterator inLast, Compare inCompare)
Helper function for QuickSort, will move the pivot element to inMiddle.
Definition QuickSort.h:13