Timing

Questions 1 to 5 of 6

1. 1. The lesson counts the comparisons insertion sort makes on reversed input of 20000 values. How many comparisons is that?

   Type a number.

2. 2. Insertion sort runs on a list of 1000 values that is already sorted. How many comparisons and swaps does it make?

   999 comparisons and 0 swaps499500 comparisons and 0 swaps999 comparisons and 999 swaps1000 comparisons and 0 swaps
3. 3. Which clock does the timing program use, and why?

   std::chrono::system_clock, because it is the clock that never jumpsstd::time(), because it returns the seconds since the program startedstd::chrono::steady_clock, because it can be set from the networkstd::chrono::steady_clock, because it always moves forward at a fixed rate
4. 4. A teammate builds the timing program with plain g++ and no optimisation flag, so the build is -O0. Selection sort is now slower than insertion sort. What is the right conclusion?

   Selection sort is always slower than insertion sort, so the lesson's -O2 result was a mistakeThe -O0 build is the correct one, so the -O2 numbers should be ignoredThe -O0 numbers describe unoptimised code, so they do not show how the sorts compare; time every sort with -O2Timing is only valid with the default flags, so -O0 is the right choice for the test
5. 5. True or False: on a list of 1000 random values, selection sort makes the same number of comparisons as it does on a list of 1000 values that is already sorted.

   False, because sorted input lets selection sort stop early, so it makes fewer comparisonsTrue, because selection sort always scans the rest of the list, so the input order does not change the count