| 206 | |
| 207 | protected: |
| 208 | void Run(CppBenchmark::Context& context) override |
| 209 | { |
| 210 | // Generate items to sort |
| 211 | std::generate(items.begin(), items.end(), rand); |
| 212 | |
| 213 | // Calculate initial distance |
| 214 | size_t d = 1; |
| 215 | while (d < items.size()) |
| 216 | d = 3 * d + 1; |
| 217 | |
| 218 | // While distance is valid |
| 219 | while (d > 0) |
| 220 | { |
| 221 | // Perform insert sort with the given distance |
| 222 | ShellSortInternal(items, d); |
| 223 | |
| 224 | // Decrease distance |
| 225 | d /= 3; |
| 226 | } |
| 227 | context.metrics().AddItems(items.size()); |
| 228 | } |
| 229 | |
| 230 | private: |
| 231 | void ShellSortInternal(std::vector<int>& subitems, size_t d) const |