Consider a new sorting algorithm similar to the bubble sort algorithm, called Rumble Sort.
Given an array as input, RumbleSort 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] (inclusive)
With regards to the above Rumble Sort algorithm, consider the following statements.
S1:Rumble Sort work's correctly for all inputs.
S2:The time complexity of detemining if the RumbleSort algorithm will work correctly for a given input is O(n2)
Which of the above statements is/are true?
Consider a new sorting algorithm similar to the bubble sort algorithm, called Rumble Sort.
Given an array as input, RumbleSort 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] (inclusive)
With regards to the above Rumble Sort algorithm, consider the following statements.
S1:Rumble Sort work's correctly for all inputs.
S2:The time complexity of detemining if the RumbleSort algorithm will work correctly for a given input is O(n2)
Which of the above statements is/are true?
The correct option is A None of these
Both are false statements.
Justification:
RumbleSort is actually Bubble Sort being applied separately to odd and even positions. We can see the way the element comparisons are done as follows.
Element 0 Element 2
Element 1 Element 3
Element 2 Element 4
Element 3 Element 5
Element 4 Element 6
And so on and it can be see that (even.odd) and (odd, even ) positions are never compared. Hence we can conclude that RumbleSort gives two sorted sublists, such that one sublist which contains elements at even positions is sorted as well the other sublists containing elements at odd positions is also sorted.
Hence
S1is clearly false.
Now since we know how the algorithm works, the algorithm actually sorts the odd and even sublists separately. Hence we can mimic the action of this algorithm by using the best sorting technique which takes O(n logn ) time to sort the odd and even positions separately first. And to check if the given array is sorted takes O(n). Hence overall time complexity to check if the algorithm will work correctly for a given input is O(n logn) thus
S2 is also false.
Both are false statements.
Justification:
RumbleSort is actually Bubble Sort being applied separately to odd and even positions. We can see the way the element comparisons are done as follows.
Element 0 Element 2
Element 1 Element 3
Element 2 Element 4
Element 3 Element 5
Element 4 Element 6
And so on and it can be see that (even.odd) and (odd, even ) positions are never compared. Hence we can conclude that RumbleSort gives two sorted sublists, such that one sublist which contains elements at even positions is sorted as well the other sublists containing elements at odd positions is also sorted.
Hence
S1is clearly false.
Now since we know how the algorithm works, the algorithm actually sorts the odd and even sublists separately. Hence we can mimic the action of this algorithm by using the best sorting technique which takes O(n logn ) time to sort the odd and even positions separately first. And to check if the given array is sorted takes O(n). Hence overall time complexity to check if the algorithm will work correctly for a given input is O(n logn) thus
S2 is also false.
