Talk:Bubble sort.html

Watch code blocks

If you're watching this article, please also add the code block templates to your watchlist:

WikiProject Computing (Rated B-Class)
	This article is within the scope of Computing WikiProject, an attempt to build a comprehensive and detailed guide to computers and computing. If you would like to participate, you can edit the article attached to this page, or visit the project page, where you can join the project and/or contribute to the discussion.
B	This article has been rated as B-Class on the quality scale
???	This article has not yet received a rating on the importance scale.

WikiProject Computer science (Rated B-Class)

Computer science portal

This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.

This article has been rated as B-Class on the quality scale.

High

This article has been rated as High-importance on the importance scale.

sort

Is it just me or is the current pseudocode terribly wrong? At a glance it looks like it'll always perform n^2 operations which is clearly not right - the description states clearly that on an already sorted list it'll only require n operations. Normally there's a "hasswapped" boolean value and a do-while loop... Not nested for loops with no breaks. 203.59.50.44 05:39, 21 February 2007 (UTC)

The preceding comment was actually me. I replaced it with what I believe is actually "bubble sort", the previous example definitely had n^2 as best case performance time. I formatted the psuedocode slightly differently as well. Namely I removed the strange form of incrementing for loop control variables as part of the for do block (which was applied inconsistently anyway) - I did read up on wikicode but the top of the page says that it was elected not to be a policy, so didn't spend too much time on it. Let me know if you find anything.Themania 09:03, 21 February 2007 (UTC)

Is the Python implementation correct? Does the variable i run from 1 to length or from length to 1? --AxelBoldt

Python range(n) gives a list [0, 1, 2, ... n-1]. The Python for statement then iterates over these values. Python arrays are indexed from 0 upwards. -- The Anome

Perhaps that's a good reason not to use Python for pseudocode? Kragen Sitaker 02:20, 22 December 2005 (UTC)

"In the worst case, bubble sort will require O(n^2) swaps, while insertion sort will require at most O(n^2) swaps." Doesn't "require O(n^2)" and "at most O(n^2)" sound the same? Not sure if I'm missing some subtle point here. --cl 202.156.2.138 01:24, 22 Apr 2005 (UTC)

It appears that this was a poorly-worded attempt to note insertion's sort asymptotic advantage in the best case. Deco 03:21, 18 November 2005 (UTC)

XOR swapping

hey why isn't XOR swapping used in any of the examples? i replaced the C code but someone will have to do the rest cuz i'm not familiar with them.

It's clever, but it's also ugly. Even worse, it's an uncommon enough idiom that it's generally more confusing than anything. Flatline 03:52, 2005 Apr 6 (UTC)

According to xor swap algorithm, xor swapping is less efficient on modern processors than regular swapping using a temp variable. So, if it's uglier and slower than the normal way, why would you want to encourage its use? Flatline 17:56, 2005 Apr 7 (UTC)

I disagree that xor swap is ugly. It's ugly when applied to situations where an ordinary swap works just as well. xor swap is useful for the special problem of swapping a subset of bit positions between two binary processor registers; it elimates unnecessary masking steps in the use of the temporary register. When applied in this context, xor bit swap allows one to construct an efficient 8x8 bit transpose using a pair of 32 bit binary registers and plenty of bit rotations. It doesn't belong here by any means. The application of boolean valued xor swap to bubble sorting a binary valued sequence is too mirthful to contemplate.

I have removed all the implementations except one; wikipedia guidelines are quite clear that implementations are merely for helping the reader understand the concept better. More than one is definitely a no-no (and so are hacks for improving effiency). Wikicode implementations are preferred; I left the python impl in because I felt it is most similar to wikicode. Anyone who wants to replace it with wikicode is welcome. Arvindn 19:44, 3 Dec 2004 (UTC)

C++ Implementation

Update: Someone has reverted the code for me. Of course, I have no objection to this, so I went ahead and corrected the bug in it. I believe my implementation will be most handy for novices as it is even more straightforward than the Python implementation below. If you disagree, please note your objection here and we'll debate.

Wikicode used.

The implementation has been written in Wikicode. We only need to see it once. All you VB programmers and whatnot can grab your implementations from the page history and contribute them to the linked Wikisource page, which can grow to your heart's delight. There's no reason to have that many implementations when we're just looking to explain the algorithm, not write a treatise on the proper reinvention of the wheel in STL. grendel|khan 21:13, 2005 Mar 18 (UTC)

If that implementation is correct Wikicode then Wikicode is quite an unorthodox thing... As I see it, the swap line should be something like

  swap(A,j,j+1)

The code right now really doesn't look like the function Swap() would swap the contents of the two adjacent indexes in the array. It looks like a confusion between values and references.

Let me be clear about this:

Function bubblesort is given a list[1..n] of type ElementType. What function Swap should get is the list plus two positions in the list - those positions that need to be swapped. Swap would be:

  function swap(A : list[1..n] of ElementType, i:index, j:index) {
     var temp : ElementType;
     temp:=A[i];
     A[i]:=A[j];
     A[j]:=temp;
  }

What about the current function? How does

  swap(i:ElementType, j:ElementType)

look like?

--Matti 13:33, 30 June 2006 (UTC)

Well, I think it's confusing to you primarily because you assign conventional value-passing semantics to it. It's easy to write for example a macro in C or a function in C++ taking reference parameters that would correctly execute this code. In some languages, all parameters are passed by reference by default. Considering that the intent is clear, I don't see a problem. Deco 13:38, 30 June 2006 (UTC)

Humm, I got to this page because of curiousity about "Wikicode". I was looking for examples of wikicode, and found that piece of code to look a bit odd, perhaps because the wikicode syntax resembles Pascal/C and wikicode is argued to be an imperative language (hence my hasty interpretation of value-passing semantics). Wikicode specs are, of course, merely suggestive, and since wikicode is pseudocode, it doesn't really matter how it's being written as long as the intent is clear. Although I'd write it differently, I see your point. There's no need to continue debate. --Matti 14:53, 30 June 2006 (UTC)

Bubble Sort is also rather slower than Insertion Sort, on average

Re: the bit in the article "Bubble sort is asymptotically equivalent in running time to insertion sort, but the two algorithms differ greatly in the number of swaps necessary. In the worst case, bubble sort will require O(n2) swaps, while insertion sort will require at most O(n) swaps."... No.

Bubble sort and insertion sort are not "asymptotically equivalent". On average...

 Bubble sort does a little less than N^2/2 swaps.  Insertion sort does a little over N^2/4 moves (NOT swaps).
 (swaps may take anything from 1x to 3x as long as moves, depending on the CPU architecture).

 Bubble sort does just under N^2/2 comparisons.  Insertion sort does a little over N^2/4.

 If the CPU has a cache, and N is sufficiently large, Bubble Sort requires approximately twice as many cache flushes.

 On pipelined architectures, Bubble Sort results in O(N*log(N)) branch mispredictions
 (that is, the total count of left-to-right minima found during the sort).
 Insertion sort: O(N).

...and so bubble sort's asymptotic running time is - typically - twice that of insertion sort. When N is small, on a pipelined architecture, it is worse even than that.

--James Barbetti, 10-July-2005

You are correct, bubble sort is considerably slower in practice for a variety of reasons, but a constant multiple performance difference is still "asymptotically equivalent", by definition. Some of these stats would be great to add to the article in the new performance section. Deco 03:09, 18 November 2005 (UTC)

Best Case Analysis?

Shouldn't the best case be only O(n) as it makes one pass over the elements? The page quotes O(n^2) as the best case running time, this has to be a mistake.

128.175.166.74 21:16, 17 October 2005 (UTC)

The pseudocode for the bubble sort algorithm needes n(n-1)/2 comparisons. Always. Thus best/wors/average time complexity of the pseudcode algorithm is O(n^2). However, version of bubble sort described in the first paragraph has best case O(n) complexity since it can detect that input list is already sorted.

Recent disparaging changes

I've added a variety of things to the article that may be considered disparaging of bubble sort. I just wanted to clarify that I have nothing personally against bubble sort and I'm really just trying to add more information to the article. I do not agree with Astrachan's assertion that bubble sort should no longer be taught; I think every sort algorithm has something to add. Deco 03:21, 18 November 2005 (UTC)

Disparagement in Context

Any clever undergraduate quickly comes to the view of bubblesort as, uh, mentally challenged. It's so worthless (in most cases) you wonder why it was first invented, much less taught to the unsuspecting.

Well, I once did hear that explained, but I've never dug up an athoritative reference for this. The notion was that bubble sort was invented (and taken seriously) because it is the *optimal* algorithm for sorting on a Turing machine. In that context no disparagement is warranted. I would speculate that once bubble sort is "in the literature" and obviously easy to teach, it takes on a life of its own from there, for reasons that were soon lost in the mist. Bear in mind that this teaching tradition likely originated at a point in time where a beginning computer science student might have little or no access to computing facilities.

If the course covers "why some algorithms suck more than others" then there is good reason to teach bubble sort; if the course covers "generally approved methods to get from point A to point B" my view is that it does more harm than good to teach this algorithm.

I would even go further. Just as one would not write an article about "new math" explaining it only in terms of its substance while neglecting entirely its political biography within the K12 establishment, I think neither should bubble sort be afforded this treatment. To my mind bubble sort is more of a cultural artifact of the undergraduate CS experience than an object of intellectual merit in its own right.

Bubble sort does have exceedingly rare uses

In all my years of coding and applications and simulations I've written, I have come across one instance where bubble sort was the best option. It was in an application that kept the order of simulated traffic moving from one side to another in a torroid shape where an entity would occasionally wrap around the edge to the other side. Each entity could only pass at maximum one other entity per turn, but the list order could not be modified until all turns were taken by each entity. Using bubble sort on this resulted in one pass across the list over 99% of the time (and the < 1% was always less than 2 passes). Note that this was also a realtime application. Granted, very few programmers will ever run into a situation remotely like this, but it was one case where bubble sort was the best option. (Note that I am using the generic words traffic and entity to not give away things covered by an NDA.)

That is interesting. I see how a few elements wrapping around like that could favour bubble sort, especially the variation with the extra flags. I'm sure an application-specific algorithm could do better, but at least bubble sort is already well-researched. I'm afraid it's obscure enough though that I'd opt to keep it here on the talk page. Deco 00:26, 6 December 2005 (UTC)

Rare Uses in Physical Embodiment

If you have a linear train track (no sidings) with a circular wheel house that rotates 180 degrees and reverses a segment of track of N cars in length, then for N==2, bubble sort allows one to order the cars in the train; plus some obvious generalizations to ordering through application of subsequence reversals.

Of course one does not encounter this in the real world, because bubble sort is what it is (horribly tedious). In most other physical contexts, there is no physical requirement that the elements swapped be adjacent in sequence.

Ascending/Descending

I suggest changing the explanation of it's name to: "The algorithm gets its name from the way smaller or larger elements "bubble" to the top (i.e. head) of the list via the swaps. The bubble sort can be implemented to sort in ascending or descending order."

My thinking is that people are used to counting from smallest number to biggest number and also it is a small sentence that clarifies this sort can be done both ways. If someone is starting out in programming they might not realize this. I say for accuracy and understandability the change is implemented and left alone. (anon post)

I understand why you consider this a useful addition, but I respectfully disagree. Simply changing the comparison from "<" to ">=" in any comparison sort will reverse the sorting order; therefore this statement is not at all specific to bubble sort and better discussed in the more general comparison sort article, as it is. The placement here suggests that this is a special property or advantage of bubble sort. Deco 03:59, 14 December 2005 (UTC)

what is bubble sort?

I was under the impression that bubble sort would repeatedly go through the entire list until no swaps were required. The first paragraph of this article describes it this way. Then, when describing it "in more detail", it uses a slightly different algorithm, where each pass through the list is slightly shorter, and the loop keeps going regardless of whether swaps are required. It would be nice if this could be clarified. I checked out Sedgewick (Algorithms, 2nd ed) and he does the same thing; he first describes it as repeatedly passing through the whole file until no swaps are required, and then gives sample code which is equivalent to the sample code from this article. Strange. (I don't have Knuth so I can't check to see how he defines it.) Pfalstad 00:14, 9 January 2006 (UTC)

Revamp

Rewrote most of the top half.

Pfalstad: It's been clarified, hopefully. See "Alternative implementations".

Jafet 16:16, 12 August 2006 (UTC)

Greatest to least or least to greatest?

The article is a little inconsistent about the goal of the sort. Throughout most (maybe all) of the text under headings, we are talking about sorting an array from greatest to least. But the psuedocode seems to sort an array from least to greatest. I understand that the bubble sort can be designed to do either, but to avoid confusing the reader, we should pick one and stick with it. --Nave251 21:51, 13 November 2006 (UTC)

Sure confused me!

THE ANNOYING GIF!!!

Out of curiosity, could somebody please get rid of the stupid gif! It gets on my nerves everytime I go to this page for a project I'm working on! The gif is absolutely pointless (unless it's there to bug the heck out of me)! I would appreciate it greatly if somebody got rid of it. Thank you.
~Lily —The preceding unsigned comment was added by 71.111.135.70 (talk) 16:17, 8 April 2007 (UTC).

A problem with the gif is that it appears to operate in Θ(n) time, instead of something between Ω(n) and О(n²). This is naturally due to it being a gif composed of the n-1 iterations, but misleading nonetheless. 82.203.161.17

In my opinion, the GIF is (in any case) not a particularly accurate depiction of the algorithm's operation. I lecture computer science, and the correlation between the randomly scattered points being arranged into a line (what the animation is showing), and a sequential list being sorted into a new order (what the algorithm is actually doing), is not at all obvious. I would suggest either removing the GIF as it currently stands, coming up with a better animation (that shows the operation of the sort on a sequential array of values), or put the animation in the body of the article, with a proper explanation of what it is actually trying to show. Wvheerden (talk)

ambiguous comparison to QuickSort

Comb sort compares elements large gaps apart and can move turtles extremely quickly, before proceeding to smaller and smaller gaps to smoothen out the list. Its average speed is comparable to faster algorithms like Quicksort.

Superficially, it is not immediately apparent that it is Comb sort which is comparable to QuickSort, and not BubbleSort (which the article is about). I suggest either removing the comparison or putting it in the preceding sentence to make this clearer.

BubbleSort itself, of course, has worst and average complexity of O(n^2).

--- Arancaytar - avá artanhé (reply) 20:59, 29 April 2007 (UTC)

Sample implementations

A "sample implementations" section has recently been added to the article, with a Java example. I'm not a sure this is a good idea, for two reasons:

We already have a perfectly-clear pseudo-code rendition, which should be understandable no matter what real-world language the reader is used to. If the reader isn't capable of translating that into language X, then they really should spend more time learning the basics of language X.

In the long run, this kind of section just leads to everyone adding an implementation in their favourite language, which unnecessarily bloats the article.

In short, I'm don't think real-world implementations add anything to the article, and have the tendency to make the article worse. See also Wikipedia:Articles for deletion/Insertion sort implementations. Oli Filth^(talk) 08:29, 28 November 2007 (UTC)

Is the second pseudo-code example really necessary? 217.171.129.72 (talk) 17:38, 5 January 2008 (UTC)

I'm not sure the pseudocode is exactly readable. It's very optimised for performance, and new programmers like me can struggle to follow it. Perhaps a commented version? The loops in it driving me crazy :P --Gigitrix (talk) 13:26, 19 January 2008 (UTC)

Rearranging the contents

I have noticed that this page has 3 versions of this algorithm. One with the most basic type (which always have complexity O(n^2)), one with a revised code that can terminate earlier (which the example is written for), and one with one more improvement (which is filed under "alternative implementations"). Adding the (lowest to greatest)-(greatest to lowest) variability, I think this does nothing but confuse the reader.
Besides, I think that this flow of contents is not "natural". I mean one needs to have some info to be able to understand what a piece of code is about, and an example after seeing the code to understand better.
My suggestion is to reorder the whole article as:

Firstly, a not-so-detailed explanation, with a consensus on the order of final array (increasing sort or decreasing sort)
Secondly, pseudocode of the most basic form (I actually don't think this is even needed, but since it is here, maybe we should keep it)
Thirdly, a not-so-detailed explanation of improvements that can be made
Then, a pseudocode with all those improvements, not a pseudocode for each improvement as it is the case now (I guess we can make just these two improvements, but who knows?)
Then, a step-by-step example
Then, the analysis part with all details that are skipped before
Then, "In practice", "Variations", "References", etc.

If we all agree on this flow, we should edit the other algorithms as well... What do you say? --Vdaghan (talk) 17:45, 15 January 2008 (UTC)

That makes sense. By the way, the current 1st and 2nd pseudocode address the array differently (0 vs 1 origin). The 3rd pseudocode is broken. Other improvements - Knuth mentions anything above the last element exchanged on the previous pass is in it's final position. OoS (talk) 21:20, 31 January 2008 (UTC)

Lie: Selection sort beats bubble sort

See Talk:Selection sort#Lie: Selection sort outperforms bubble sort

Barack Obama on bubble sort

http://www.youtube.com/watch?v=k4RRi_ntQc8 or buried within whole interview http://www.youtube.com/watch?v=1nnj7r1wCD4 —Preceding unsigned comment added by 99.230.244.220 (talk) 01:24, 3 August 2008 (UTC)

Sinking sort

Why does "sinking sort" redirect here? I am aware that NIST says it's the same thing, but go throught "The Art Of Computer Programming" and you will see it's not. I've asked Donald Knuth, the author, about it and he said that he is sure that NIST is wrong and they are currently working on updating their pages with more accurate information and will probably update that as well.

And it's pretty obvious that it's not bubble sort that's named like that, as bubbles don't sink! It sais there what algorithm it actually is. Love4Boobies —Preceding undated comment was added at 12:15, 25 September 2008 (UTC).

bubble sort-complexity

1.time complexity

         the time comlexity is calculated interms of number of comparisons f(n);here two loops(outer loop and inner loop)itrates(or repeated)the comparisons.the number of times the outer loop itrates is determined by the number of elements in the list(say n).the inner loop iterated one less than the number of elements in the list(ie,(n-1)) and it is reiterated upon every iteration of the outer loop.
 ie, the first iteration through n-1 elements
     the second iteration through n-2 elements
     the third iteration through n-3 elements  and so on...
  
     ie, the no. of compares/swaps=(n-1)+(n-2)+(n-3)+......+2+1
                                  =n(n-1)=n^2-n
                          here the highest power of n is 2.this indicates that the time complexity is o(n2).

 best case:
           the best case hapens when the swap procedure is never called.in the best case outer loop will terminate after one iteration.ie,it involves performing one pass,which requires (n-1) comparisons
            f(n)=o(n)

The traditional formulation of bubblesort never terminates the outer loop early. This article has been modified to introduce early termination, and this decision needs to be revisited. Dcoetzee 22:31, 29 October 2008 (UTC)

Wrong. Bubble Sort always terminates after a pass where no swaps were done. This is the fundamental characteristic of Bubble Sort. The version without this end condition is not Bubble Sort, but an inefficient implementation of Selection Sort. The description is correct. The pseudocode was wrong, I fixed it now. --PauliKL (talk) 08:38, 11 December 2008 (UTC)

Code block templates

Hi all. A while ago I began an experiment with a new method for discouraging incorrect good-faith changes to code and pseudocode called "code block templates" on the articles quicksort and binary search algorithm. So far there haven't been any incorrect new changes to those code block templates, but very few changes have been made, so I'd like to expand the scope of this experiment to see how effective it is. This is one of the articles I'm targeting for this second phase. Please let me know on my talk page if you have any questions or concerns. Thanks! Dcoetzee 21:37, 7 December 2008 (UTC)