Advertisement
Guest User

Testing inversion sort

a guest
Jan 18th, 2017
263
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.83 KB | None | 0 0
  1. #include <cmath>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. long long sort_test(const int n) {
  6.   std::vector<int> A(n);
  7.   for (int ii = 0; ii < n; ++ii) {
  8.     A[ii] = n-ii;
  9.   }
  10.   long long operations_performed = 0;  // We do not count initialization.
  11.   for (int ii = 1; ii < n; ++ii) {
  12.     operations_performed += 5;  // Loop operations and inequality evaluation.
  13.     if (A[ii-1] > A[ii]) {
  14.       operations_performed += 4;  // Swap and restart.
  15.       const int tmp = A[ii-1];
  16.       A[ii-1] = A[ii];
  17.       A[ii] = tmp;
  18.       ii = 0;
  19.     }
  20.   }
  21.   return operations_performed;
  22. }
  23.  
  24. int main() {
  25.   for (int ii = 20; ii < 1000; ++ii) {
  26.     long long operations_performed = sort_test(ii);
  27.     std::cout << ii << ' ' << operations_performed << ' '
  28.               << log(ii) << ' ' << log(operations_performed) << '\n';
  29.   }
  30.   return 0;
  31. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement