ME Mock 4

Question

Consider a new sorting algorithm similar to the BubbleSort algorithm, called RumbleSort. Given an array as input, RumbleSort attempts to sort the array and produces a sorted array as output. Here’s the pseudo-code for RumbleSort.

 

With regards to the above RumbleSort algorithm, consider the following statements.

S1:  RumbleSort works correctly for all inputs.

S2:  The time complexity of determining if the RumbleSort algorithm will work correctly for a given input is $\mathcal Ο(n^2)$

 

Which of the above statements is/are true?

Answer 1

S1 is False, S2 is True

Notice that:

• A. Any element initially at an even index, will always remain at an even index. Similarly, any element initally at an odd index will remain at an odd index.
• B. An even indexed element is not compared with any element at an odd numbered index in one iteration of rumblesort.
• C. Using A and B we have a stronger claim that any element initially at an even index can "never" be compared to an element initially at any odd index.

 

S1: C is sufficient to tells us that Rumble sort is incorrect, that is, it doesn't work correctly for all inputs.

example input where Rumblesort fails: [2, 1, 3]

 

S2: To verify whether Rumblesort will work correctly for a given input I, we can sort all even indexed elements of I and all odd elements of I separately. Let these sorted lists be $\rm{EVEN}$ and $\rm{ODD}$. Then, Rumblesort fails if $\exists i: \exists j < i: \rm{ODD}[j] > \rm{EVEN}[i]$, or if $\exists j: \exists i < j: \rm{EVEN}[i] > \rm{ODD}[j]$

This verification takes $\Theta (n \log n)$ time for the two sorts, and $\mathcal O(n^2)$ time for each of those checks, totaling $\mathcal O (n^2)$ time.

Note: The checks can be done in $\mathcal O(n \log n)$ by using binary search, so the most efficient checking algorithm can do it in $\Theta (n \log n)$ time.