Question

Consider a new sorting algorithm similar to the bubble sort algorithm, called Rumble Sort. Given an array as input, Rumble Sort attempts to sort the array and produces a sorted array as output. Here' s the pseudocode for RumbleSort (L).

Rumblesort(L):
let sorted = false
while not sorted:
sorted = true
for i = 0; i < len (L) - 2; i + + ;
if L(i) > L [i + 2];
sorted = false
reverse the given list from L(i) to L [i + 2] (unclusive).

Consider running RumblesSort on the following inputs.
(i) [5 6 8 4 3]
(ii) [5 6 4 8 3]
(iii) [3 4 8 6 5]
(iv) [5 4 8 6 3 ]

For how many of the inputs, does RumbleSort produce the correct sorted array?

• A. 3
• B. 1
• C. 2
• D. 4

Answer 1

The correct option is A 3

(c)
RumbleSort algorithm fails to correctly sort the second input. Other inputs work fine.