1 //
2 // Copyright (c) 2008-2017 the Urho3D project.
3 //
4 // Permission is hereby granted, free of charge, to any person obtaining a copy
5 // of this software and associated documentation files (the "Software"), to deal
6 // in the Software without restriction, including without limitation the rights
7 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 // copies of the Software, and to permit persons to whom the Software is
9 // furnished to do so, subject to the following conditions:
10 //
11 // The above copyright notice and this permission notice shall be included in
12 // all copies or substantial portions of the Software.
13 //
14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20 // THE SOFTWARE.
21 //
22
23 #pragma once
24
25 #include "../Container/Swap.h"
26 #include "../Container/VectorBase.h"
27
28 namespace Urho3D
29 {
30
31 static const int QUICKSORT_THRESHOLD = 16;
32
33 // Based on Comparison of several sorting algorithms by Juha Nieminen
34 // http://warp.povusers.org/SortComparison/
35
36 /// Perform insertion sort on an array.
InsertionSort(RandomAccessIterator<T> begin,RandomAccessIterator<T> end)37 template <class T> void InsertionSort(RandomAccessIterator<T> begin, RandomAccessIterator<T> end)
38 {
39 for (RandomAccessIterator<T> i = begin + 1; i < end; ++i)
40 {
41 T temp = *i;
42 RandomAccessIterator<T> j = i;
43 while (j > begin && temp < *(j - 1))
44 {
45 *j = *(j - 1);
46 --j;
47 }
48 *j = temp;
49 }
50 }
51
52 /// Perform insertion sort on an array using a compare function.
InsertionSort(RandomAccessIterator<T> begin,RandomAccessIterator<T> end,U compare)53 template <class T, class U> void InsertionSort(RandomAccessIterator<T> begin, RandomAccessIterator<T> end, U compare)
54 {
55 for (RandomAccessIterator<T> i = begin + 1; i < end; ++i)
56 {
57 T temp = *i;
58 RandomAccessIterator<T> j = i;
59 while (j > begin && compare(temp, *(j - 1)))
60 {
61 *j = *(j - 1);
62 --j;
63 }
64 *j = temp;
65 }
66 }
67
68 /// Perform quick sort initial pass on an array. Does not sort fully.
InitialQuickSort(RandomAccessIterator<T> begin,RandomAccessIterator<T> end)69 template <class T> void InitialQuickSort(RandomAccessIterator<T> begin, RandomAccessIterator<T> end)
70 {
71 while (end - begin > QUICKSORT_THRESHOLD)
72 {
73 // Choose the pivot by median
74 RandomAccessIterator<T> pivot = begin + ((end - begin) / 2);
75 if (*begin < *pivot && *(end - 1) < *begin)
76 pivot = begin;
77 else if (*(end - 1) < *pivot && *begin < *(end - 1))
78 pivot = end - 1;
79
80 // Partition and sort recursively
81 RandomAccessIterator<T> i = begin - 1;
82 RandomAccessIterator<T> j = end;
83 T pivotValue = *pivot;
84 for (;;)
85 {
86 while (pivotValue < *(--j));
87 while (*(++i) < pivotValue);
88 if (i < j)
89 Swap(*i, *j);
90 else
91 break;
92 }
93
94 InitialQuickSort(begin, j + 1);
95 begin = j + 1;
96 }
97 }
98
99 /// Perform quick sort initial pass on an array using a compare function. Does not sort fully.
InitialQuickSort(RandomAccessIterator<T> begin,RandomAccessIterator<T> end,U compare)100 template <class T, class U> void InitialQuickSort(RandomAccessIterator<T> begin, RandomAccessIterator<T> end, U compare)
101 {
102 while (end - begin > QUICKSORT_THRESHOLD)
103 {
104 // Choose the pivot by median
105 RandomAccessIterator<T> pivot = begin + ((end - begin) / 2);
106 if (compare(*begin, *pivot) && compare(*(end - 1), *begin))
107 pivot = begin;
108 else if (compare(*(end - 1), *pivot) && compare(*begin, *(end - 1)))
109 pivot = end - 1;
110
111 // Partition and sort recursively
112 RandomAccessIterator<T> i = begin - 1;
113 RandomAccessIterator<T> j = end;
114 T pivotValue = *pivot;
115 for (;;)
116 {
117 while (compare(pivotValue, *(--j)));
118 while (compare(*(++i), pivotValue));
119 if (i < j)
120 Swap(*i, *j);
121 else
122 break;
123 }
124
125 InitialQuickSort(begin, j + 1, compare);
126 begin = j + 1;
127 }
128 }
129
130 /// Sort in ascending order using quicksort for initial passes, then an insertion sort to finalize.
Sort(RandomAccessIterator<T> begin,RandomAccessIterator<T> end)131 template <class T> void Sort(RandomAccessIterator<T> begin, RandomAccessIterator<T> end)
132 {
133 InitialQuickSort(begin, end);
134 InsertionSort(begin, end);
135 }
136
137 /// Sort in ascending order using quicksort for initial passes, then an insertion sort to finalize, using a compare function.
Sort(RandomAccessIterator<T> begin,RandomAccessIterator<T> end,U compare)138 template <class T, class U> void Sort(RandomAccessIterator<T> begin, RandomAccessIterator<T> end, U compare)
139 {
140 InitialQuickSort(begin, end, compare);
141 InsertionSort(begin, end, compare);
142 }
143
144 }
145