what's bubble sort good at? [duplicate]_问答_开发者

This question already has answers here: Closed 12 years ago. 开发者_开发问答

Possible Duplicate:
What is a bubble sort good for?

I'am sure every algorithm has its advantage and disadvantage, so how about buble sort compared to other sorting algorithm? (ofcourse I hope the answer is other than "easy to learn")

It is easy to implement for linked lists, since you always swap adjacent nodes while traversing left to right repeatedly.
Bubble sort is a stable sort.

Performance-wise, Bubble Sort is not very good (O(n^2)). Here are some of it's advantages:

Bubble Sort is very easy to write correctly (if you're doing something quick and dirty then it might be easier just to use bubble sort).
Memory consumption is very low (because it is an in-place sort, unlike Merge Sort for arrays)

It's simple enough to play it out in school without it ending in a total mess: "If your left neighbor is taller than you, please switch places."

It's easier to program. Even seasoned programmers get quick sort, heap sort, and merge sort wrong. Also it does not consume an extra log(n) to O(n) in stack space. Although you can implement heap sort non recursively.

Basically the algorithms are this

O(n^2) worst case performance

Basically this is slower....

Insertion O(n^2) but performs O(n) on already sorted lists
Bubble sort: similar but not always programmed with the early exit to allow for this. Generally this one seems to be the more popular one to discuss and throw out in interviews
Selection Sort: there is generally no early exit so this always takes O(n^2)

O(n * lg(n))

Generally the fastest sorting algorithms for general sorting when you don't know anything about the input (this has actually been proven to be a lower bound on sorting without knowing anything about the input):

Quick Sort: It is usually the faster of the high speed algorithms, but mistakes in picking the pivot can make it degenerate to O(n^2), and then it is worse than say Bubble/Insertion/Selection because it also consumes stack space. It takes more advantage of cache locality so generally performs better than some of the other alternatives. It needs LG(n) space to O(n) space for calls depending upon how well it pivots.
Merge Sort: O(n*log(n)) performance, but requires O(n) extra space in. Generally not as fast as quick sort. Generally requires lg(n) extra space as well for calls...
Heap Sort: Requires no extra space, can be implemented non recursively, but sort of bounces around the array so it is not as good on the cache as the others. If implemented recursively requires lg(n) extra space for calls.

O(n) sorts
If you know something about your inputs you can often sort better than O(n*lg(n)). Basically look up Radix Sort, Bucket Sort, Counting Sort, etc.. There are many schemes. Generally if it is possible to sort using one of these you should....

**Other Sorts: ** There are many other sorts available. Things like shell sort, etc... the ones above are the more common.

But anyway in reality the faster algorithms are often harder to implement. If someone told me to sort these numbers in 20 minutes without a library, I'd probably write selection sort. The more complex ones are easier to get wrong. And often require additional space. You have to evaluate the complexity, space, and time tradeoffs. Many programming languages have built in sorting libraries.

Also one other thing to be careful of is whether a sort is stable or not. Basically if you have A, C, D, C, G, C will each C appear in order, or will the last C appear before one of the other C's. This is important if you are sorting on multiple fields. Ie if you sort by First Name and then last name (Alex Rodriguez, Jane Rodriguez, Betty Rodriguez)...first sort you'd get (Alex R, Betty R, Jane R). Second sort if it is stable you will get Alex R, Betty R, Jane R. If it is not stable, you could get any order. Generally Bubble and Insertion are easy to implement to be stable. Heap Sort and Quick Sort usually aren't stable. Merge sort is easy to implement as stable. This also factors into choices....

Also if you don't know O(n) notation, basically it is an upper bound on how many computations it takes. To give you an idea, to sort 20 items you are looking at around 400 operations with O(n^2) while with O(n * lg(n)) you are looking at 20 * approx 4.3 so around 86 operations. And for lg(n) you are looking at around 4.3. Anyway the larger the number gets the bigger this difference is. 10000 items is 133000 operations for n*lg(n) and 100000000 for n^2. For large lists using the slower sorts starts to become impractical. And of course O(n) is just 10,000. The number of operations is not exactly those numbers, but they speak to how fast it grows. Ie with just lg(n) you grow from 4.3 for 20 to 133000. With n you grow from 20 to 10000 with n * lgn you grow from 86 to 133000 and with n^2 you grow from 400 to 100000000. So basically as your lists get bigger the slower ones will reach a point where they can't do them but the faster ones can.

Anyway having put it all in context I see the following advantages to bubble sort:

Easy to implement and get right.
Doesn't consume extra space for array or procedure calls (assuming you don't implement it recursively)...so good for low memory environments
It reads the array sequentially so this is good for the memory cache
Someone else mentioned it is easy to use this to sort linked lists
It is easy to make this stable
Some interviewer will no doubt mention this at some point

Anyway in libraries Quick Sort and Stable Merge sort seem to be the most popular.

Bubble sort is the fastest way to sort a list of three items. With very few exceptions, all sorts degenerate into a form of bubble sort for lists of three.

BubbleSort is faster than QuickSort (and almost every other sort) on already sorted lists ;-)

QuickSort's best-case performance is O(N log N), BubbleSort's is O(N) !

Other than this exotic, I'd have to agree with Donald Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching:

In short, the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems

Realistically you would never use it for anything other than very small lists. For a sufficiently small list the low overhead can make it superior to the fancier sorts. I'd never use it for more than a dozen items.