Editorial for CPC '19 Contest 1 P4 - Sorting Practice
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Solution Sketch
Subtask 1
For the first subtask, we can use any sort that swaps adjacent elements, such as bubble sort or insertion sort. These sorts take comparisons and swaps.
Time Complexity:
Subtask 2
For the second subtask, we recall that insertion sort works best when the array is nearly sorted. We will consider a solution where for each from the largest where , down to , we will use insertion sort to sort all elements that are distance apart from each other, relative to one another. This can be thought of as arranging the array into approximately rows each with approximately elements, and sorting each row.
Well versed programmers will recognize this as shell sort with Hibbard's gap sequence. It can be shown that this takes comparisons and swaps in the worst case. Extra care should be taken to ensure that a correct insertion sort break condition is used.
Time Complexity:
Comments