1] Will bubble sort () work properly if the inner loop for (int j = n-1; j > i;

Question

1] Will bubble sort () work properly if the inner loop

for (int j = n-1; j > i; --j) is replaced by

for (int j = n-1; j > 0; --j)

What is the complexity of the new version?

2] Many operations can be performed faster on sorted than on unsorted data. For which of the following operations is this the case?

a. checking whether one word is an anagram of another word, e.g., plum and lump

b. finding an item with a minimum value

c. computing an average of values

d. finding the middle value (the median)

e. finding the value that appears most frequently in the data

Explanation / Answer

(1) First one is yes because in bubble sort there will be two for loops hope you know that.

for(i = 0;i<n;i++){

       for (int j = n-1; j > i; --j){      }

}.

Here the inner loop runs n-1, times, n-2 times, n-3 times so on up to 1 time since i value is increasing.

But when yuo replace it with for (int j = n-1; j > 0; --j) it always runs n-1 times naming it exactly O(n^2). Just does some extra computation nothing more than that.

Times will remain O(n^2) itself.

So bubble sort () work properly even if the inner loop

for (int j = n-1; j > i; --j) is replaced by

for (int j = n-1; j > 0; --j).

(2) D. Finding the middle value since it is just the floor[(n-1)/2] element of the array starting from 0. For finding the median in un sorted array it would take more computation like ordering and then finding the median of them.

So D is the answer.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.