Geek asks and answers

About Bubble Sort and Merge Sort

This is a question from an interview I recently found on the Internet:

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

Here's how I think about it:

Firstly, it is very strange to use sorting to implement the above function. You can just go through the array once and find the maximum. Secondly, if you need to make a choice between them, it is better to choose a bubble - you do not need to perform the entire procedure for sorting the bubbles, but only need to complete the first pass. This is better than merging sorting in both time and space.

Are there any errors in my answer? Did I miss something?

+5
source share
6 answers

This is a trick. If you just need a maximum (or, indeed, the value of k th for any k, which includes a median search), there is a perfectly good algorithm O(n). Sorting is a waste of time. This is what they want to hear.

As you say, the algorithm for maximum is really trivial. To solve such a problem, you should have a ready-made quick selection algorithm, and also be able to offer a heap data structure in case you need to change the list of values ​​and always be able to quickly produce maximum speed.

+9
source

. - , . , . Merge , , , ; . , , . , , , . .

+4

-, , , , , , , .

O(n2), Merge Sort - O(nlogn). , , Bubble .

+2

, , n , / . .

+1

, , u, , .

+1

Merge sorting is easy for a computer to sort items, and sorting takes less time than sorting bubbles. The best case with merge sort is n*log2n, and the worst is n*log2n. The best case for sorting bubbles is O(n), and the worst case is O(n2).

+1
source

More articles:


All Articles