ezEngine  Milestone 7
Sorting_inl.h
1 
2 template <typename Container, typename Comparer>
3 void ezSorting::QuickSort(Container& container, const Comparer& comparer)
4 {
5  QuickSort(container, 0, container.GetCount() - 1, comparer);
6 }
7 
8 template <typename T, typename Comparer>
9 void ezSorting::QuickSort(ezArrayPtr<T>& arrayPtr, const Comparer& comparer)
10 {
11  QuickSort(arrayPtr, 0, arrayPtr.GetCount() - 1, comparer);
12 }
13 
14 template <typename Container, typename Comparer>
15 void ezSorting::InsertionSort(Container& container, const Comparer& comparer)
16 {
17  InsertionSort(container, 0, container.GetCount() - 1, comparer);
18 }
19 
20 template <typename T, typename Comparer>
21 void ezSorting::InsertionSort(ezArrayPtr<T>& arrayPtr, const Comparer& comparer)
22 {
23  InsertionSort(arrayPtr, 0, arrayPtr.GetCount() - 1, comparer);
24 }
25 
26 
27 template <typename Container, typename Comparer>
28 void ezSorting::QuickSort(Container& container, ezUInt32 uiStartIndex, ezUInt32 uiEndIndex, const Comparer& comparer)
29 {
30  if (uiStartIndex < uiEndIndex)
31  {
32  if (uiEndIndex - uiStartIndex <= INSERTION_THRESHOLD)
33  {
34  InsertionSort(container, uiStartIndex, uiEndIndex, comparer);
35  }
36  else
37  {
38  ezUInt32 uiPivotIndex = Partition(container, uiStartIndex, uiEndIndex, comparer);
39 
40  if (uiStartIndex < uiPivotIndex)
41  QuickSort(container, uiStartIndex, uiPivotIndex - 1, comparer);
42 
43  QuickSort(container, uiPivotIndex + 1, uiEndIndex, comparer);
44  }
45  }
46 }
47 
48 template <typename Container, typename Comparer>
49 ezUInt32 ezSorting::Partition(Container& container, ezUInt32 uiLeft, ezUInt32 uiRight, const Comparer& comparer)
50 {
51  const ezUInt32 uiPivotIndex = (uiLeft + uiRight) / 2;
52 
53  ezMath::Swap(container[uiPivotIndex], container[uiRight]); // move pivot to right
54 
55  ezUInt32 uiIndex = uiLeft;
56  for (ezUInt32 i = uiLeft; i < uiRight; ++i)
57  {
58  if (comparer.Less(container[i], container[uiRight]))
59  {
60  ezMath::Swap(container[i], container[uiIndex]);
61  ++uiIndex;
62  }
63  }
64 
65  ezMath::Swap(container[uiIndex], container[uiRight]); // move pivot back in place
66 
67  return uiIndex;
68 }
69 
70 
71 template <typename T, typename Comparer>
72 void ezSorting::QuickSort(ezArrayPtr<T>& arrayPtr, ezUInt32 uiStartIndex, ezUInt32 uiEndIndex, const Comparer& comparer)
73 {
74  if (uiStartIndex < uiEndIndex)
75  {
76  if (uiEndIndex - uiStartIndex <= INSERTION_THRESHOLD)
77  {
78  InsertionSort(arrayPtr, uiStartIndex, uiEndIndex, comparer);
79  }
80  else
81  {
82  ezUInt32 uiPivotIndex = Partition(arrayPtr, uiStartIndex, uiEndIndex, comparer);
83 
84  if (uiStartIndex < uiPivotIndex)
85  QuickSort(arrayPtr, uiStartIndex, uiPivotIndex - 1, comparer);
86 
87  QuickSort(arrayPtr, uiPivotIndex + 1, uiEndIndex, comparer);
88  }
89  }
90 }
91 
92 template <typename T, typename Comparer>
93 ezUInt32 ezSorting::Partition(ezArrayPtr<T>& arrayPtr, ezUInt32 uiLeft, ezUInt32 uiRight, const Comparer& comparer)
94 {
95  const ezUInt32 uiPivotIndex = (uiLeft + uiRight) / 2;
96 
97  ezMath::Swap(arrayPtr[uiPivotIndex], arrayPtr[uiRight]); // move pivot to right
98 
99  ezUInt32 uiIndex = uiLeft;
100  for (ezUInt32 i = uiLeft; i < uiRight; ++i)
101  {
102  if (comparer.Less(arrayPtr[i], arrayPtr[uiRight]))
103  {
104  ezMath::Swap(arrayPtr[i], arrayPtr[uiIndex]);
105  ++uiIndex;
106  }
107  }
108 
109  ezMath::Swap(arrayPtr[uiIndex], arrayPtr[uiRight]); // move pivot back in place
110 
111  return uiIndex;
112 }
113 
114 
115 template <typename Container, typename Comparer>
116 void ezSorting::InsertionSort(Container& container, ezUInt32 uiStartIndex, ezUInt32 uiEndIndex, const Comparer& comparer)
117 {
118  for (ezUInt32 i = uiStartIndex + 1; i <= uiEndIndex; ++i)
119  {
120  ezUInt32 uiHoleIndex = i;
121  while (uiHoleIndex > uiStartIndex && comparer.Less(container[uiHoleIndex], container[uiHoleIndex - 1]))
122  {
123  ezMath::Swap(container[uiHoleIndex], container[uiHoleIndex - 1]);
124  --uiHoleIndex;
125  }
126  }
127 }
128 
129 template <typename T, typename Comparer>
130 void ezSorting::InsertionSort(ezArrayPtr<T>& arrayPtr, ezUInt32 uiStartIndex, ezUInt32 uiEndIndex, const Comparer& comparer)
131 {
132  T* ptr = arrayPtr.GetPtr();
133 
134  for (ezUInt32 i = uiStartIndex + 1; i <= uiEndIndex; ++i)
135  {
136  ezUInt32 uiHoleIndex = i;
137  T valueToInsert = std::move(ptr[uiHoleIndex]);
138 
139  while (uiHoleIndex > uiStartIndex && comparer.Less(valueToInsert, ptr[uiHoleIndex - 1]))
140  {
141  --uiHoleIndex;
142  }
143 
144  const ezUInt32 uiMoveCount = i - uiHoleIndex;
145  if (uiMoveCount > 0)
146  {
147  ezMemoryUtils::RelocateOverlapped(ptr + uiHoleIndex + 1, ptr + uiHoleIndex, uiMoveCount);
148  ezMemoryUtils::MoveConstruct(ptr + uiHoleIndex, std::move(valueToInsert));
149  }
150  else
151  {
152  ptr[uiHoleIndex] = std::move(valueToInsert);
153  }
154  }
155 }
156