CODEWITHSUNDEEP
algorithmsorting
quantumrose
quantumrose

Reputation: 165

About bubble sort vs merge sort

This is an interview question that I recently found on Internet:

If you are going to implement a function which takes an integer array as input and returns the maximum, would you use bubble sort or merge sort to implement this function? What if the array size is less than 1000? What if it is greater than 1000?

This is how I think about it:

First, it is really weird to use sorting to implement the above function. You can just go through the array once and find the max one. Second, if have to make a choice between the two, then bubble sort is better - you don't have to implement the whole bubble sort procedure but only need to do the first pass. It is better than merge sort both in time and space.

Are there any mistakes in my answer? Did I miss anything?

Upvotes: 9

Views: 26970

Answers (6)

Hani Khan
Hani Khan

Reputation: 11

Merge sort is easy for a computer to sort the elements and it takes less time to sort than bubble sort. Best case with merge sort is n*log2n and worst case is n*log2n. With bubble sort best case is O(n) and worst case is O(n2).

Upvotes: 1

YakuZa
YakuZa

Reputation: 526

only one pass is needed , for worst case , to find maximum u just have to traverse the whole array , so bubble would be better ..

Upvotes: 1

dfb
dfb

Reputation: 13289

Barring the maximum part, bubble sort is slower asymptotically, but it has a big advantage for small n in that it doesn't require the merging/creation of new arrays. In some implementations, this might make it faster in real time.

Upvotes: 1

rici
rici

Reputation: 241911

It's a trick question. If you just want the maximum, (or indeed, the kth value for any k, which includes finding the median), there's a perfectly good O(n) algorithm. Sorting is a waste of time. That's what they want to hear.

As you say, the algorithm for maximum is really trivial. To ace a question like this, you should have the quick-select algorithm ready, and also be able to suggest a heap datastructure in case you need to be able to mutate the list of values and always be able to produce the maximum rapidly.

Upvotes: 17

Four_lo
Four_lo

Reputation: 1150

I just googled the algorithms. The bubble sort wins in both situations because of the largest benefit of only having to run through it once. Merge sort can not cut any short cuts for only having to calculate the largest number. Merge takes the length of the list, finds the middle, and then all the numbers below the middle compare to the left and all above compare to the right; in oppose to creating unique pairs to compare. Meaning for every number left in the array an equal number of comparisons need to be made. In addition to that each number is compared twice so the lowest numbers of the array will most likely get eliminated in both of their comparisons. Meaning only one less number in the array after doing two comparisons in many situations. Bubble would dominate

Upvotes: 5

Zac
Zac

Reputation: 2211

Firstly I agree with everything you have said, but perhaps it is asking about knowing time complexity's of the algorithms and how the input size is a big factor in which will be fastest.

Bubble sort is O(n2) and Merge Sort is O(nlogn). So, on a small set it wont be that different but on a lot of data Bubble sort will be much slower.

Upvotes: 2

Related Questions