| 207 | |
| 208 | template<typename T, typename U> |
| 209 | static void SortArray(T* data, int32 count, bool (*compare)(const T& a, const T& b, U* userData), U* userData) |
| 210 | { |
| 211 | if (count < 2) |
| 212 | return; |
| 213 | auto& stack = SortingStack::Get(); |
| 214 | |
| 215 | // Push left and right |
| 216 | stack.Push(0); |
| 217 | stack.Push(count - 1); |
| 218 | |
| 219 | // Keep sorting from stack while is not empty |
| 220 | while (stack.Count != 0) |
| 221 | { |
| 222 | // Pop right and left |
| 223 | int32 right = stack.Pop(); |
| 224 | const int32 left = stack.Pop(); |
| 225 | |
| 226 | // Partition |
| 227 | T* x = &data[right]; |
| 228 | int32 i = left - 1; |
| 229 | for (int32 j = left; j <= right - 1; j++) |
| 230 | { |
| 231 | if (compare(data[j], *x, userData)) |
| 232 | { |
| 233 | i++; |
| 234 | Swap(data[i], data[j]); |
| 235 | } |
| 236 | } |
| 237 | Swap(data[i + 1], data[right]); |
| 238 | const int32 pivot = i + 1; |
| 239 | |
| 240 | // If there are elements on left side of pivot, then push left side to stack |
| 241 | if (pivot - 1 > left) |
| 242 | { |
| 243 | stack.Push(left); |
| 244 | stack.Push(pivot - 1); |
| 245 | } |
| 246 | |
| 247 | // If there are elements on right side of pivot, then push right side to stack |
| 248 | if (pivot + 1 < right) |
| 249 | { |
| 250 | stack.Push(pivot + 1); |
| 251 | stack.Push(right); |
| 252 | } |
| 253 | } |
| 254 | } |
| 255 | |
| 256 | /// <summary> |
| 257 | /// Sorts the linear data array using Quick Sort algorithm (non recursive version, uses temporary stack collection). Uses reference to values for sorting. Useful for sorting collection of pointers to objects that implement comparision operator. |