SHARE
TWEET

Testing inversion sort

a guest Jan 18th, 2017 149 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top