Improvemet on bubble sort

Question

Which of the following can make for an improved version of bubble sort?
(A) Traverse the array left to right during odd passes and right to left during even passes, in bubble sort
(B) Divide the array into smaller arrays, apply quick sort on each of the small arrays and the apply bubble sort on the entire array
(C) Store the addresses to be swapped in a separate array and make all the swaps at one go
(D) None of these

Answer 1

Bubble sort can be improved by using inner loop while required (i.e. swapping element while required) , otherwise inner loop should skip
(A) Doing both way sort is not an efficient solution , As if we do left to right increasing order sorting , then right to left decreasing order.

(B) Though quick sort has time complexity O(n log n) in avg case which is better than bubble sort O(n²), but that is not  needed for getting better version of bubble sort. Actually here we  are using quick sort and then again bubble sort , which is not improving time or space complexity of bubble sort

(C)Swapping in separate array will increase space complexity of bubble sort

So, Answer will be (D)

Comments

yes, answer should be D. In B, even if we have sorted sub arrays, quick sort work as usual and gives $O(n^2)$ complexity. Option C cannot work as bubble sort requires the swapped elements to be compared in further steps. So, it is not possible to do all swaps in one go.

---

I understood stuff about option B and C. But I don't understand option A. In fact I am not able to imagine in what scenario option A approach will provide any kind of improvement. Is it even possible to sort the whole array by sorting left to right in odd passes and right to left in even passes? I am not able to imagine how do I implement this even if its not improvement over normal bubble sort. Or is it just option formed to confuse us?

---

We can apply  sorting from 2 end at the same time to get better running time

But here we are not doing these at same time , So what will be use of it?

I think it is useless