Here is a test generation program.

int main() { freopen("e.in", "w", stdout); cout << 1000000 << '\n'; for (int i = 0; i < 1000000; i++) cout << rand() << ' '; return 0; }

Here is a quick sort of array

 #include <cstdio> #include <iostream> #include <algorithm> using namespace std; int a[1000100], n; int main() { freopen("e.in", "r", stdin); freopen("e.out", "w", stdout); cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; sort(a, a + n); return 0; }

Evaluation of this algorithm is 10 ^ 6 * log (10 ^ 6) <10 ^ 8, how can it work so long ???? 7

  • Now turn this trick on the Spectrum, for a week it will sort out ... maybe ... - Vladimir Klykov
  • what ? ???? - Eugene536
  • 10 ^ 8 is what? - KaZaca
  • one
    1. How did you measure the lead time? 2. The calculation of the theoretical execution time in cycles has ceased to be relevant since the time 8086 left home computers, in which there was still a naive consistent execution of everything and everything. - Pavlus
  • one
    @ Eugene536, what did you want from the crosses? Generalized programming does not fit well with the speed of execution. Use I / O from C (<stdio.h>, in your case apparently fscanf ()). - avp

1 answer 1

Sorting is not slow, but data reading. At the beginning of the program add:

 ios_base::sync_with_stdio(false);