fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <chrono>
  5. #include <random>
  6.  
  7. // =====================================================================
  8. // Custom Template Metaprogramming (Generic) Implementation of Sort
  9. // Uses a standard recursive Quicksort pattern
  10. // =====================================================================
  11. template<typename RandomIt>
  12. void custom_template_sort(RandomIt first, RandomIt last) {
  13.     // Base case: if the range is 1 or 0 elements, it is already sorted
  14.     if (first >= last - 1) return;
  15.  
  16.     // Choose a pivot (middle element)
  17.     auto pivot = *(first + (last - first) / 2);
  18.  
  19.     auto left = first;
  20.     auto right = last - 1;
  21.  
  22.     // Partitioning
  23.     while (left <= right) {
  24.         while (*left < pivot) left++;
  25.         while (*right > pivot) right--;
  26.  
  27.         if (left <= right) {
  28.             std::iter_swap(left, right);
  29.             left++;
  30.             right--;
  31.         }
  32.     }
  33.  
  34.     // Recursive calls
  35.     if (first < right + 1) {
  36.         custom_template_sort(first, right + 1);
  37.     }
  38.     if (left < last) {
  39.         custom_template_sort(left, last);
  40.     }
  41. }
  42.  
  43. // =====================================================================
  44. // Benchmark Engine
  45. // =====================================================================
  46. int main() {
  47.     const int SIZE = 100000;
  48.  
  49.     std::cout << "Generating " << SIZE << " random elements...\n";
  50.     std::vector<int> data_std(SIZE);
  51.  
  52.     // Generate random data
  53.     std::mt19937 rng(42); // Fixed seed for reproducible results
  54.     std::uniform_int_distribution<int> dist(1, 1000000);
  55.     for(int i = 0; i < SIZE; ++i) {
  56.         data_std[i] = dist(rng);
  57.     }
  58.  
  59.     // Create an identical copy for the custom sort
  60.     std::vector<int> data_custom = data_std; 
  61.  
  62.     // ---------------------------------------------------------
  63.     // Benchmark 1: std::sort
  64.     // ---------------------------------------------------------
  65.     auto start1 = std::chrono::high_resolution_clock::now();
  66.     std::sort(data_std.begin(), data_std.end());
  67.     auto end1 = std::chrono::high_resolution_clock::now();
  68.  
  69.     std::chrono::duration<double, std::milli> time_std = end1 - start1;
  70.  
  71.     // ---------------------------------------------------------
  72.     // Benchmark 2: Custom Template Sort
  73.     // ---------------------------------------------------------
  74.     auto start2 = std::chrono::high_resolution_clock::now();
  75.     custom_template_sort(data_custom.begin(), data_custom.end());
  76.     auto end2 = std::chrono::high_resolution_clock::now();
  77.  
  78.     std::chrono::duration<double, std::milli> time_custom = end2 - start2;
  79.  
  80.     // ---------------------------------------------------------
  81.     // Results
  82.     // ---------------------------------------------------------
  83.     std::cout << "\n--- Benchmark Results (" << SIZE << " elements) ---\n";
  84.     std::cout << "std::sort time:          " << time_std.count() << " ms\n";
  85.     std::cout << "custom_template_sort:    " << time_custom.count() << " ms\n";
  86.  
  87.     // Verify that the custom sort actually worked
  88.     bool correct = std::is_sorted(data_custom.begin(), data_custom.end());
  89.     std::cout << "\nCustom sort is correct:  " << (correct ? "True" : "False") << "\n";
  90.  
  91.     // Speed comparison
  92.     if (time_std.count() < time_custom.count()) {
  93.         std::cout << "Result: std::sort is " 
  94.                   << (time_custom.count() / time_std.count()) 
  95.                   << "x faster than the custom implementation.\n";
  96.     }
  97.  
  98.     return 0;
  99. }
Success #stdin #stdout 0.02s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Generating 100000 random elements...

--- Benchmark Results (100000 elements) ---
std::sort time:          4.84113 ms
custom_template_sort:    6.2489 ms

Custom sort is correct:  True
Result: std::sort is 1.29079x faster than the custom implementation.
https://ideone.com/jxJ00Y
language:
C++14 (gcc 8.3)
created:
6 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!