1// 
2// tSort.h 
3// 
4// Basic stable and unstable sort for arrays of objects. Both sorting functions require a compare function to be 
5// provided. If the type you are passing has a corresponding operator< (less) you can use that implicetly by not 
6// supplying a compare function. The default compare function will call '<' for you. If compare implements 
7// less-than, the array will be sorted in ascending order. Greater-than will reverse the order. 
8// 
9// Copyright (c) 2004-2006, 2015 Tristan Grimmer. 
10// Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby 
11// granted, provided that the above copyright notice and this permission notice appear in all copies. 
12// 
13// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL 
14// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, 
15// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN 
16// AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 
17// PERFORMANCE OF THIS SOFTWARE. 
18 
19#pragma once 
20#include <Foundation/tStandard.h> 
21 
22 
23namespace tSort 
24{ 
25 template<typename T> bool tCompLess(const T& a, const T& b) { return (a < b) ? true : false; } 
26 template<typename T> bool tCompGreater(const T& a, const T& b) { return (a > b) ? true : false; } 
27 
28 // Insertion sort. O(n^2) in worst case. Faster on already sorted data. This function is stable in that objects with 
29 // equal values will not be reordered. 
30 template<typename T> void tInsertion(T array[], int numItems, bool compare(const T& a, const T& b) = tCompLess<T>); 
31 
32 // Shellsort. Fast when number of items is small. Not stable. See https://en.wikipedia.org/wiki/Shellsort 
33 template<typename T> void tShell(T array[], int numItems, bool compare(const T& a, const T& b) = tCompLess<T>); 
34 
35 // Quicksort. O(n log n). Not stable but fast. Good with unordered data. Uses shellsort when numItems < 32. 
36 template<typename T> void tQuick(T array[], int numItems, bool compare(const T& a, const T& b) = tCompLess<T>); 
37 
38 // @todo Bubble sort, merge sort, or maybe selection sort instead of merge. 
39} 
40 
41 
42// Implementation below this line. 
43 
44 
45template<typename T> inline void tSort::tInsertion(T A[], int N, bool compare(const T& a, const T& b)) 
46{ 
47 for (int i = 1; i < N; i++) 
48 { 
49 const T value = A[i]; 
50 int j = i - 1; 
51 
52 for (; j >= 0 && compare(value, A[j]); j--) 
53 A[j+1] = A[j]; 
54 
55 A[j+1] = value; 
56 } 
57} 
58 
59 
60template<typename T> inline void tSort::tShell(T A[], int N, bool compare(const T& a, const T& b)) 
61{ 
62 // This code is a conversion of the pseudocode found on the Wikipedia page for shellsort: https://en.wikipedia.org/wiki/Shellsort 
63 // It uses Shell's original gap sequence. We start with the largest gap and work down to a gap of 1. 
64 for (int gap = N/2; gap; gap /= 2) 
65 { 
66 // Do a gapped insertion sort for this gap size. 
67 // The first gap elements A[0..gap-1] are already in gapped order. 
68 // Keep adding one more element until the entire array is gap sorted. 
69 for (int i = gap; i < N; i++) 
70 { 
71 // Add arr[i] to the elements that have been gap sorted. 
72 // Save arr[i] in temp and make a hole at position i. 
73 T temp = A[i]; 
74 
75 // Shift earlier gap-sorted elements up until the correct location for a[i] is found. 
76 // Since we wanted ascending order for a less-than compare, I reversed the order of the compare args vs the Wikipedia article. 
77 int j = i; 
78 for (; (j >= gap) && compare(temp, A[j - gap]); j -= gap) 
79 A[j] = A[j - gap]; 
80 
81 // Put temp (the original arr[i]) in its correct location. 
82 A[j] = temp; 
83 } 
84 } 
85} 
86 
87 
88namespace tSort 
89{ 
90 template<typename T> void tQuickRec(T* left, T* right, bool compare(const T& a, const T& b) = tCompLess<T>); 
91} 
92 
93 
94template<typename T> inline void tSort::tQuickRec(T* left, T* right, bool compare(const T& a, const T& b)) 
95{ 
96 int numItems = int(right - left) + 1; 
97 
98 // If there are only a few items in the list we use shellsort. 
99 const bool useShell = true; 
100 if (useShell) 
101 { 
102 const int shellItemThreshold = 32; 
103 if (numItems < shellItemThreshold) 
104 { 
105 tShell(left, numItems, compare); 
106 return; 
107 } 
108 } 
109 else 
110 { 
111 if (numItems <= 1) 
112 return; 
113 } 
114 
115 // Midpoint. 
116 T* mid = left + (right-left)/2; 
117 
118 if (compare(*mid, *left)) 
119 tStd::tSwap(*mid, *left); 
120 if (compare(*right, *mid)) 
121 tStd::tSwap(*right, *mid); 
122 if (compare(*mid, *left)) 
123 tStd::tSwap(*mid, *left); 
124 
125 // Pivot. 
126 const T pivot = *mid; 
127 T* i = left; 
128 T* j = right; 
129 
130 while (i <= j) 
131 { 
132 while (compare(*i, pivot) && i < right) 
133 i++; 
134 
135 while (compare(pivot, *j) && left < j) 
136 j--; 
137 
138 if (i <= j) 
139 { 
140 tStd::tSwap(*i, *j); 
141 i++, j--; 
142 } 
143 } 
144 
145 // Recurse. 
146 if (left < j) 
147 tQuickRec(left, j, compare); 
148 
149 if (i < right) 
150 tQuickRec(i, right, compare); 
151} 
152 
153 
154template<typename T> inline void tSort::tQuick(T A[], int N, bool compare(const T& a, const T& b)) 
155{ 
156 tQuickRec<T>(A, A + N - 1, compare); 
157} 
158