Editorial for CPC '19 Contest 1 P4 - Sorting Practice


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: wleung_bvg

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 \mathcal{O}(N^2) comparisons and swaps.

Time Complexity: \mathcal{O}(N^2)

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 k from the largest k where 2^k \le N, down to 1, we will use insertion sort to sort all elements that are distance 2^k - 1 apart from each other, relative to one another. This can be thought of as arranging the array into approximately 2^k - 1 rows each with approximately \frac{N}{2^k - 1} 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 \mathcal{O}(N \cdot \sqrt{N}) 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: \mathcal{O}(N \cdot \sqrt{N})


Comments

There are no comments at the moment.