Timing

Questions 1 to 5 of 6

1. 1. Selection sort makes n times (n minus 1) divided by 2 comparisons on every input. Which growth class does this count belong to?

   n log n2 to the power of nn (linear)n squared
2. 2. On random input, bubble sort's full comparison count grows with the square of the list length. If the list grows from 100 values to 200 values, about how many times more comparisons does bubble sort make?

   About 2 timesAbout 8 timesAbout 4 timesAbout 200 times
3. 3. Which sorts do exactly one adjacent move for each inversion in the input? An inversion is a pair of values that are in the wrong order.

   Bubble sort and insertion sortSelection sort onlyInsertion sort onlysorted(), the built-in sort, which uses Timsort
4. 4. A student times bubble sort once on 5000 numbers and reports that single number. Which change makes the timing trustworthy?

   Print each sorted list inside the timed part so the output can be checkedCopy the input before each run, repeat the run several times, and report the medianSwitch from time.perf_counter_ns() to time.time() for a coarser clockSort the same list again and time the second sort
5. 5. True or false: selection sort makes fewer comparisons on an already sorted list of 100 values than on a random list of 100 values, because it stops early when the list is sorted.

   False, because selection sort always makes all 4,950 comparisons for 100 values, even when the input is already sortedTrue, because selection sort stops as soon as a pass finds no swap