Unit 8 Assessment Question 3

CSA
1

I need help to understand why the statement in Option E in the Unit 8 Assessment lesson is true. The description in the following explanation seems to contradict itself: “In a reverse sorted array, each element will be compared and shifted to the right for almost every iteration. This means that fewer comparisons and shifts are required compared to other sorting algorithms, making insertion sort more efficient in this specific case.” Doesn’t “each element” and “fewer comparisons and shifts” contradict with each other?

Actually, I don’t understand the statement itself “Insertion sort is generally faster for a reverse sorted array.” Are we looking at a descending array and trying to sort it into an ascending array, for example? Isn’t this the worst case scenario that requires O(n^2) iterations? I can’t tell insertion sort is faster in this case.

On the other hand, if the statement in Option B is false, the statement in Option E should also be false, right?
B. Selection sort is generally slower than insertion sort on a randomized list.
E. Insertion sort is generally faster for a reverse sorted array.

Q3 explanation
Q3 explanation1112×889 93.4 KB

3

I’d like to follow up on this since I haven’t seen any responses. Can somebody respond to my question? My students have finished taking this assessment, and I had to decide to cancel this question since the answer was incorrect in my opinion. I’d appreciate your inputs!

4

Hi @zhu.xiaobo, I do apologize for the delay in response. I know that it was time sensitive since you were giving this as an assessment for your class. I wanted to formulate an articulate response and fully understand your question and the explanations the Code.org solution statements. I have to agree with you that the statement does tend to contradict itself. Using this link that compares insertion and selection sort, it states that in all cases selection sort has a runtime of O(n^2), and in the worst case scenario for insertion sort (when the array is in reverse order) the runtime is O(n^2) and the best case scenario (the array is already sorted) the runtime is O(n).

I will run this by the curriculum team and hopefully this resources will provide a little more light on the question.

Best,
-Sam

1 Like