Talk:Bubble sort

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)

A bubble sort is very quick & easy to code in most high-level native system interfaces. Bubble sort is also be very fast and convenient in system management scripts. The same can be said about the occasional bubble sort when coding in “C”; the resulting mnemonic code is very fast and efficient for casual use on relatively smaller data sets/arrays. Fssymington (talk) 13:16, 19 March 2022 (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.

The author's description of "clever" undergraduates and "mentally challenged", possibly puts them in the camp that seems to assume all competent programmers were born that way and were turning out merge-sorts during primary education. Some students have barely started learning to code, or learning what algorithms are, when they first come across the bubble sort. To that end, it serves as a good introduction to sorting algorithms, algorithmic thinking in general, analyzing complexity etc as long as the appropriate caveats and signposts are added ("this is not a good sort in the real world"). I have never seen bubble sort appear in even the most elementary materials without these warnings. It's not like "hello world" is particularly useful either, but students must walk before they can run. Let's be honest, most software engineers will never need to actually write any sort algorithm in production, rather than use a library, anyway.

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)

Another note is that bubble sort lends itself very well to parallelization, especially on SIMD architectures. Each processor can handle comparing and swapping pairs of elements, then each iteration the pair boundaries shift, resulting in (with N/2 processors) a running time of O(N). —Preceding unsigned comment added by 204.111.162.215 (talk) 19:18, 31 October 2009 (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)

I agree. Perhaps we could replace it with something along the lines of what's seen on [this page here]. He makes a lot of good points about the deficiencies of the current animation on the page, some of which Wvheerden has already pointed out. 216.16.60.102 (talk) 20:39, 15 April 2009 (UTC)

I agree as well, I have also taken the liberty of changing it accordingly. crashmatrix (talk | contribs) 23:27, 8 September 2009 (UTC)

Thanks for taking the initiative on this. The new image is much better. --Two Bananas (talk) 18:58, 9 September 2009 (UTC)

I don't know what the old gif looked like but I found the current gif to be very useful. WikiAlto (talk) 21:01, 31 October 2012 (UTC)

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).

The first sentence of the article says bubble sort is the same as sinking sort and the last section says it is not. John P. McCaskey (talk) 18:15, 28 January 2012 (UTC)

Does anybody have a reference on this? I'm not convinced it's correct to say that NIST is "wrong" and Knuth is "right." They're just names. As far as I can tell, the "misnomer" section is original research based on an unsourced conversation and someone's conjecture about how bubbles behave (which is totally irrelevant to whether that's a nickname for a search). There's no such thing as a "misnomer," because there are no actual bubbles involved: the question is whether people actually call it a "sinking" sort. If NIST does, that's a resounding affirmative. Gerweck (talk) 11:16, 4 November 2013 (UTC)

AFAIK, "bubble sort" and "sinking sort" are two related, but different algorithms. This is "sinking sort":

for i ← 1 to length(A) - 1
    for j ← i+1 to length(A):
        if A[i] > A[j]:
            swap A[j] and A[i]
    end for
end for

This is more primitive than bubble sort: "sinking sort" is not restricted to comparison of adjacent values. This makes it unstable! (Bubble sort is stable.) Sinking sort shouldn't redirect here. RBKreckel (talk) 07:12, 2 December 2015 (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)

There seems to be different opinions about this on the net. This university source states that bubble sort always runs for its n/2 iterations:

http://www.cs.auckland.ac.nz/~jmor159/PLDS210/sorting.html

These two describes the termination check as an optimization:

http://www.cs.duke.edu/~ola/bubble/bubble.pdf

http://ee.hawaii.edu/~tep/EE160/Book/chap10/subsection2.1.2.2.html

Does anyone have Art of comp prog on the shelf? We need Knuth to settle this issue once and for all.

It probably should be mentioned in the article that there are different opinions.

Liiiii (talk) 13:05, 11 February 2012 (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)

Error in pseudocode?

I think the pseudocode section contains an error. Examining this code block:

    for each i in 0 to n - 1  inclusive do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )

If the array A is zero-indexed, then when i == n-1 the code references A[ i + 1 ] == A[n] which is outside the bounds of the array. Clearly if A is one-indexed, then there is no entry A[0].

Hgilde (talk) 14:11, 25 September 2009 (UTC)

Seems like the pseudocode needs a correction, this one will not sort the entire list it is only the first iteration, I think the nested loop method in the Optimization section must replace this one. --Mmgokce (talk) 10:14, 22 July 2011 (UTC)

  do
   swapped = false
   for each i in 1 to length(A) - 1 inclusive do:
     if A[i-1] > A[i] then
       swap( A[i-1], A[i] )
       swapped = true
     end if
   end for
 while swapped

It is not clear what you are talking about. All three versions appear to work (and have inside and outside loops). The NLM method has a null inside iteration on the last value of the outside loop, but that doesn't stop it from working. Glrx (talk) 15:22, 22 July 2011 (UTC)

i still think that the pseudo-code in the article is incorrect.

current state is

   do{
       swapped = false;
       for(int i = 1; i<=size-1; i++) {
           if(values[i-1] > values[i]) {
               temp = values[i-1];
               values[i-1] = values[i];
               values[i] = temp;
               swapped = true;
           }
       }
   } while(!swapped);

but this will not sort the entire list, as it exits the loop after the first iteration. the final condition ought to be

   } while(swapped);

If someone is available for discussion please post your comments here. thanks. --boomSlang 08:54, 8 May 2012 (UTC) — Preceding unsigned comment added by Ksheer (talk • contribs)

That is not the code in the article. The article's loop exit condition is until not swappped -- which is the same as while swapped. Glrx (talk) 14:01, 9 May 2012 (UTC)

External links

Two recent changes ([1], [2]) to the article were made by Mahanthi1 (talk), in which an existing link was replaced by a link to a website listing C examples (including Bubble sort). The same user made a similar change to Heapsort. Per Wikipedia's guidelines for external links, I reverted the changes. I also invited the user to discuss the changes here, per WP:BRD.--4wajzkd02 (talk)

Implementations

Someone removed my Java implementation of bubble sort, but I noticed that the page on Fisher-Yates shuffle has implementations in several languages. Is there a rule about when code can be included on a page? Ztothefifth (talk) 23:59, 20 December 2010 (UTC)

The question is what does an implementation in language X do for the article? I don't see the merit in a specific language. Bubble sort is not a complex algorithm. Psuedo code is clear enough, and it also avoids the problem of some editors wanting an implementation in their favorite language. If there's a Java, then there should be a C++. If you look back on the article history, you will see efforts to install multiple language versions. Furthermore, Wikipedia is not a how to guide. It is not a code depository.

That some other article includes multiple implementations of an algorithm is not justification to include multiple implementations here.

What does your Java implementation illustrate about bubble sort that is not expressed in the psuedo code versions? This is not an article about programming in Java. Readers should not be expected to know Java.

Glrx (talk) 03:07, 21 December 2010 (UTC)

Okay, that makes sense. Ztothefifth (talk) 03:14, 21 December 2010 (UTC)

Misnomer

The sinking sort name issue is still with us. See also #Sinking sort above. Sinking sort still redirects here. Sinking isn't mentioned at insertion sort.

I have some trouble with the claim that bubble sort is incorrectly termed "sinking sort". There is a NIST reference that says sinking sort is bubble sort. Knuth says insertion sort is sometimes called sinking sort. We need a reliable source that says bubble sort is not sinking sort. It may be that sinking sort lacks precision and refers to both bubble and insertion methods. In that case, the refs are not inconsistent.

The unsourced arguments are unconvincing. In a bubble sort, the smaller values take their time bubbling up to the surface, but the largest values are rabbits that quickly sink to the bottom. Sinking and bubbling seem equally apt.

Unless there are are reliable sources that says it's wrong to refer to bubble sort as sinking sort, then WP should not make the claim. Hearsay that Knuth said it isn't right isn't verifiable, and NIST has had 4 years to update the page.

Does somebody have an RS that says sinking sort is not bubble sort?

Glrx (talk) 20:48, 21 April 2012 (UTC)

Contradiction in article

The first and the last paragraph of the article are in direct contradiction about where bubble sort gets its name. — Preceding unsigned comment added by 213.138.152.225 (talk) 09:31, 27 September 2012 (UTC)

Pseudocode Correct?

I'm not sure about this but i don't think the part which says "until not swapped" is correct. The loop should only end when it reaches the end of the list not when there is no swap. A section of the list could be coincidentally in order and this may stop the loop prematurely. E.g. 127935. 1 and 2 would produce no swaps at all and end the 'repeat...until' loop prematurely. 60.51.124.251 (talk) 10:37, 14 March 2013 (UTC)

The end condition for the repeat...until is only tested after the for loop has examined the entire list. Glrx (talk) 04:26, 15 March 2013 (UTC)

a possible useful 1 -> k, k practically any value 1..n data extrapolation

sometimes i think its possible to swap two equal size blocks as some generalization of bubblesort. Using Euclid arrange/rearrange there could b possible that those two blocks have different sizes.... Florin Matei, Romania 93.118.212.93 (talk) 03:58, 22 June 2013 (UTC)

No External Links to Implement Bubble Sort in Basic C language

This is the basic sort for programmers and the external links contain all languages Except C.So I posted an additional link for a C implementation of Bubble sort [www.loverusham.blogspot.in/2014/03/bubble-sort-selection-sort-insertion.html Bubble Sort in Basic C] in Basic C but it has been reverted by some Spambot.I am new here and I dont understand how it works. — Preceding unsigned comment added by LoverushAM (talk • contribs) 06:59, 14 March 2014 (UTC)

The clue is in the URL. "blogspot" is a blog which is not regarded as a reliable source for Wikipedia purposes. I have no doubt that the C algorithm is correct, but sourcing it from a blog is not regarded as acceptable. DieSwartzPunkt (talk) 14:59, 21 March 2014 (UTC)

Ah, I have just spotted what the real problem is. The blog in question was published by yourself, so it is regarded as a self published source which is not acceptable. The bot spotted that your account name is also in the URL of the blog. DieSwartzPunkt (talk) 15:06, 21 March 2014 (UTC)

Exchange sort redirects here

Why does the Exchange sort redirect to this article? It has no relationship to the bubble sort being a completely different algorithm. When compared to the other mainstream sorting algorithms, it comes out as the second fastest for randomised data, taking (very) roughly 50% longer than the Quick sort. DieSwartzPunkt (talk) 14:56, 21 March 2014 (UTC)

Step-by-step example

This example is misleading. There are 10 comparisons to be made in a list of 5 items: n(n-1)/2. Moreover, if a list to be sorted is in reverse order then the last pass will incur one swap and no further passes will be needed.

Chrysippo (talk) 19:59, 11 November 2015 (UTC)

Yes, the step-by-step is wrong. Not enough iterations, too many comparisons in each iteration. It should be four total iterations not three with successivley fewer comparisons in each iteration (4, 3, 2, 1) for a total of 10 comparisons. 66.225.134.125 (talk) 21:53, 16 November 2015 (UTC)

another optimization? (lower array bound)

i came across another optimization in _Numerical Methods, Algorithms and Tools in C#_ by Waldemar Dos Passos, starting on Page 304:

https://books.google.com/books?id=oLOB2rvNegUC&pg=PT304&lpg=PT304&dq=%22bubble+sort%22+%22the+last+swap%22&source=bl&ots=P3xGPwUJnq&sig=p37w7-ew-fk_QELw48UrQEpExM8&hl=en&sa=X&ved=0ahUKEwjbnoOugrPJAhXGRSYKHV_FCsI4ChDoAQgiMAQ

it involves moving the lower array bound up when there are no changes to the early part of the list on a pass through. note that unlike with the upper array bound, this isn't a persistent cap; the lower limit can decrease once a "turtle" drifts down.

somebody smarter than me will have to verify whether this change works, and decide whether the situational speed gain outweighs the added overhead to merit inclusion in the Wiki. also, because the loop in the book compares (x[i] > x[i+1]) rather than the (x[i-1] > x[i]) in this article, one or more lines of code might need to be adjusted by 1.

(edit: okay, was on a website since 2003: http://www.fredosaurus.com/notes-cpp/algorithms/sorting/bubblesort2.html) — Preceding unsigned comment added by 73.44.213.60 (talk) 11:20, 8 December 2015 (UTC)

73.44.213.60 (talk) 04:25, 29 November 2015 (UTC) assassin17

Removing the last external link added

I will be removing the last external link added - to a university lecture with one slide that explains the visualization in the infobox. We try to avoid links to lectures. However, the article had no explanation for that visualization and the addition was an attempt to correct that. I've added the original source as a reference in the image caption. In 2007 the author of this style of visualization, disliking sorting animations, ran into "a particularly heinous example of the genre. I found the following specimen on the Wikipedia page for Bubblesort:". So he created his own style of visualization in response to this very page. It was fun finding that out. StarryGrandma (talk) 02:44, 17 March 2017 (UTC)

Repeated passes are unnecessary

I am confused by this algorithm.

It uses repeated passes, but this is not necessary. All that is necessary is to move back one step whenever a swap is done.

Here is JavaScript code that does this:

function sort(list)
{
	for (p = 0; p < list.length - 1; )
		if (list[p + 1] < list[p])
		{
			i = list[p];
			list[p] = list[p + 1];
			list[p + 1] = i;

			if (p == 0)
				p++;
			else
				p--;
		}
		else
			p++;
}

The article claims that the algorithm is very inefficient, but it is highly efficient if it is done the above way.

What is the point of this? Angel Cupid (talk) 04:09, 18 May 2019 (UTC)

This is a fun algorithm. What you have given here is not bubble sort, but a version of cocktail sort, which is a bit faster than bubble sort. While your algorithm makes only one upward pass, it will make many downward passes as it moves lower values down. StarryGrandma (talk) 22:40, 18 May 2019 (UTC)

Actually this is Gnome sort. StarryGrandma (talk) 22:33, 19 May 2019 (UTC)

Basic version of Bubble sort, which has quadratic best-case complexity, is not documented here.

Hello all,

I have edited this article two times to document the existence of a version of Bubble sort that does not use the swap variable and, therefore, has quadratic time complexity even in the best case. This Bubble sort version can be found, for example, in the book Introduction to Algorithms, which "has been widely used as the textbook for algorithms courses at many universities", as the own Wikipedia states. But, unfortunately, the edits were reverted.

The fact that such version exist in some books is worth to be mentioned here, because it means that several students learn this version of the algorithm, hence, learning that the best-case time complexity of Bubble sort is $O(n^{2})$, but then, when they search for Bubble sort in Wikipedia, they find a (slightly) different algorithm with different best-case complexities.

I believe that we have a quite simple issue to solve here, namely, we can simply include in Bubble sort's article some information about that version presented in the book Introduction to Algorithms, and that is what I did with my two edits.

If you disagree with me, please, could you come here and explain your reasons?

Thank you very much.

--Lp.vitor (talk) 07:55, 4 September 2019 (UTC)

There are some small changes that can be made to the basic bubblesort that, for certain input conditions, give a faster result. It isn't so obvious which of those should be included here. Gah4 (talk) 12:40, 4 September 2019 (UTC)

But I am not saying that we must include one in spite of the other. I am just saying that we should say somewhere in the article that both versions exist, because many people only know one of the two versions. That is what I did with my edits (as it can checked in the history of this page...). --Lp.vitor (talk) 13:37, 4 September 2019 (UTC)

You added the unsourced statement, "Some authors call Bubble sort the version with the swap test (that has linear time best-case complexity), while for others, Bubble sort is the most simple version whose time complexity is always quadratic." That statement is opinion. It downplays the number of authors who use the swap version (some rather than most), it emphasizes the authors who do not include the swap, it suggests that the version without the swap is simplest (what about the a version that uses an outer while), and it suggests that the version with the swap test may not be "bubble sort" to some authors (if bubble sort is the version without the swap, then what is the version with the swap called?).

• Astrachan (a buble-sort antagonist) states, "Nearly every description of bubble sort describes how to terminate the sort early if the vector becomes sorted. This optimization requires checking if any swaps are made and terminating if no swaps are made after j iterations of the inner loop."
• NIST Dictionary of Algorithms states bubble sort is, "Sort by comparing each adjacent pair of items in a list in turn, swapping the items if necessary, and repeating the pass through the list until no swaps are done."

Consequently, the common versions of bubble sort with have the swap test.

If "several students learn this version of the algorithm" and are surprised by the swap test version, then they were poorly taught or didn't pay attention to the subsequent optimizations.

From an exposition standpoint, the Knuth exchange sort and CLRS bubble sort already have the last-items-are-sorted optimization, so it obviates the section Bubble sort#Optimizing bubble sort. The code confuses the exposition.

Looking at just the code, the Knuth exchange sort and CLRS bubble sort look more like a selection sort; instead of keeping track of the max item's index, the max item keeps sinking. It looks like the goal from the beginning is to put the largest item in the last slot (just like selection sort but with many more swaps that keep the sort stable) and any swaps along the way were accidental. I do not have either book handy, so I do not know what they actually say.

I expect a description that is conceptually different and more like a relaxation or hill climbing algorithm. The array is disordered; making a single swap pass will make it more ordered. Continually doing such passes will result in an ordered array. A swap test is added to determine when the array is sorted and terminate the outer loop (i.e., the swap test is a center piece of the algorithm). Strictly local improvements (swaps) give a global result (a sorted array). The description also highlights that more than just the last item is being sorted. Then analysis shows the inner loop puts at least one more item in its proper place, so after at most n passes, the array is sorted; the outer loop can be μ-minimized and the inner loop can be optimized to skip the already ordered elements.

The article's version of bubbleSort tracks the above paragraph. The outer loop is not a bounded for loop but un unbounded while and the inner loops is not yet optimized.

Astrachan says Iverson 1962 is the first to use the term "bubble sort". Iverson's description starts at the end of the array and works backward, so the notion of lighter items "bubbling up" to the top of the array makes sense. Iverson (p. 217) says,

The result is to bubble each item upward in the sequence until it encounters an item with a smaller (or equal) key and then to leave it and continue bubbling the new smaller item. In particular, the smallest item is bubbled to the top. Successive stages repeat the process, but since the jth stage brings the jth smallest item to the jth position, the (j + 1)th stage need not treat the first j positions. It is clear that ν(x) - 1 stages suffice, but it is advantageous to allow termination at the end of the first stage during which no transpositions occur.

(Iverson describes the goal as a selection sort; he goes on to describe bubble sorts that reverse direction for each pass.)

Leaving out the swap test also contradicts earlier article text that states, "The only significant advantage that bubble sort has over most other algorithms, even quicksort, but not insertion sort, is that the ability to detect that the list is sorted efficiently [sic] is built into the algorithm." Without the swap test, there is no sorted list detection.

I do not see an advantage in providing an even more pathetic Θ(n²) version of bubble sort. Especially if it does not mesh with the rest of the article's text.

Glrx (talk) 20:53, 4 September 2019 (UTC)

Hello, Glrx. First of all, thank you for coming here and participating on the discussion. I mostly agree with you about the statement that "Some authors call Bubble sort the version with the swap test[...]". It was unsourced because the sources were basically the same as before (e.g., the CLRS). So, in order to solve this specific issue, it is sufficient to write it in the other way around, i.e., "Some authors call Bubble sort the version without the swap test[...]", as it would highlight that the majority of the authors consider the version with swap test.

On your assertion about students that learn this "simpler" version: they are not necessarily poorly taught, it may happen that the professor chose to teach only this version because Bubble sort is not important enough to extend discussions about it, mainly if a professor is using CLRS book, which is very likely to happen. On the other extreme, you could also say that students that do not know that a version of Bubble sort without swap test exist are also poorly taught (which I would also not agree, but, is a statement that follows the same logic).

One observation, even the Duke University's page that you linked present the code without the swap test variable, despite the comment written below the code.

About your comment that a version without the swap test contradicts the earlier article text, that is also easily solvable by adding two or three words to that part of the article that appears earlier.

Finally, about your last paragraph: all this is not about advantage. My whole point is that we are constructing an encyclopedia, not a book, so, we can't choose to show only the "less pathetic" version of the algorithm, we must tell the readers that for some important authors, like Donald Knuth and Thomas H. Cormen, Bubble sort is a slightly different algorithm that has quadratic time complexity even in the best case.

--Lp.vitor (talk) 09:17, 5 September 2019 (UTC)

bubble sort is adaptive

I'm quite sure bubble sort is adaptive, but I can't find anything that would confirm this. If someone can manage to find this, the section on performance should be rewritten. Binarycat64 (talk) 15:33, 17 June 2022 (UTC)

From what i can tell, the definition of an adaptive sorting algorithm is broad enough to include the property of exiting early on a sorted list, so I'm gonna go ahead with the rewrite. Binarycat64 (talk) 15:42, 17 June 2022 (UTC)

Obama's bubble sort answer is staged?

The Obama section, gives the impression that Obama answered a genuine CS question, whilst the actual video suggests that its staged and for comedic effect. Could/should we reword the sentence to reflect this tone?

I can see some reasons against editing/adding clarification. Firstly, further detail might place too much focus on Obama, who isn't the focus of the article. Secondly, it might damage Obama character a little. Thirdly, it might be a little awkward to word. PlasticStylus (talk) 19:01, 17 October 2022 (UTC)

Parallel bubble sort

This discusses parallel bubble sorting but it doesn't give time complexity. It seems to me that it can speed it up by a factor of at most the number of tasks that can be run in parallel. I don't think it could be O(n²) unless you could run O(n²) tasks in parallel. That also discusses it. Bubba73 ^{You talkin' to me?} 03:10, 25 September 2024 (UTC)