text:
Ballpoint pen

A ballpoint pen, also known as a biro (British English), ball pen (Hong Kong, Pakistani, Indian and Philippine English), or dot pen (Nepali English), is a pen that dispenses ink (usually in paste form) over a metal ball at its point, i.e., over a "ball point". The metals commonly used are steel, brass, or tungsten carbide. The design was conceived and developed as a cleaner and more reliable alternative to dip pens and fountain pens, and it is now the world's most-used writing instrument; millions are manufactured and sold daily. It has influenced art and graphic design and spawned an artwork genre.

Origins
The concept of using a "ball point" within a writing instrument to apply ink to paper has existed since the late 19th century. In these inventions, the ink was placed in a thin tube whose end was blocked by a tiny ball, held so that it could not slip into the tube or fall out of the pen.

The first patent for a ballpoint pen was issued on 30 October 1888 to John J. Loud, who was attempting to make a writing instrument that would be able to write "on rough surfaces—such as wood, coarse wrapping-paper, and other articles" which fountain pens could not. Loud's pen had a small rotating steel ball held in place by a socket. Although it could be used to mark rough surfaces such as leather, as Loud intended, it proved too coarse for letter-writing. With no commercial viability, its potential went unexploited, and the patent eventually lapsed.

The manufacture of economical, reliable ballpoint pens as are known today arose from experimentation, modern chemistry, and the precision manufacturing capabilities of the early 20th century. Patents filed worldwide during early development are testaments to failed attempts at making the pens commercially viable and widely available. Early ballpoints did not deliver the ink evenly; overflow and clogging were among the obstacles faced by early inventors. If the ball socket were too tight or the ink too thick, it would not reach the paper. If the socket were too loose or the ink too thin, the pen would leak, or the ink would smear. Ink reservoirs pressurized by a piston, spring, capillary action, and gravity would all serve as solutions to ink-delivery and flow problems.

László Bíró, a Hungarian newspaper editor (later a naturalized Argentine) frustrated by the amount of time that he wasted filling up fountain pens and cleaning up smudged pages, noticed that inks used in newspaper printing dried quickly, leaving the paper dry and smudge-free. He decided to create a pen using the same type of ink. Bíró enlisted the help of his brother György, a dentist with useful knowledge of chemistry, to develop viscous ink formulae for new ballpoint designs.

Bíró's innovation successfully coupled viscous ink with a ball-and-socket mechanism that allowed controlled flow while preventing ink from drying inside the reservoir. Bíró filed for a British patent on 15 June 1938.

In 1941, the Bíró brothers and a friend, Juan Jorge Meyne, fled Germany and moved to Argentina, where they formed "Bíró Pens of Argentina" and filed a new patent in 1943. Their pen was sold in Argentina as the "Birome", from the names Bíró and Meyne, which is how ballpoint pens are still known in that country. This new design was licensed by the British engineer Frederick George Miles and manufactured by his company Miles Aircraft, to be used by Royal Air Force aircrew as the "Biro". Ballpoint pens were found to be more versatile than fountain pens, especially in airplanes, where fountain pens were prone to leak.

Bíró's patent, and other early patents on ballpoint pens, often used the term "ball-point fountain pen".

Postwar proliferation

Following World War II, many companies vied to commercially produce their own ballpoint pen design. In pre-war Argentina, success of the Birome ballpoint was limited, but in mid-1945, the Eversharp Co., a maker of mechanical pencils, teamed up with Eberhard Faber Co. to license the rights from Birome for sales in the United States.

In 1946, a Spanish firm, Vila Sivill Hermanos, began to make a ballpoint, Regia Continua, and from 1953 to 1957 their factory also made Bic ballpoints, on contract with the French firm  Société Bic.

During the same period, American entrepreneur Milton Reynolds came across a Birome ballpoint pen during a business trip to Buenos Aires, Argentina. Recognizing commercial potential, he purchased several ballpoint samples, returned to the United States, and founded the Reynolds International Pen Company. Reynolds bypassed the Birome patent with sufficient design alterations to obtain an American patent, beating Eversharp and other competitors to introduce the pen to the US market. Debuting at Gimbels department store in New York City on 29 October 1945, for US$12.50 each (1945 US dollar value, about $ in dollars), "Reynolds Rocket" became the first commercially successful ballpoint pen. Reynolds went to great extremes to market the pen, with great success; Gimbel's sold many thousands of pens within one week. In Britain, the Miles-(Harry) Martin pen company was producing the first commercially successful ballpoint pens there by the end of 1945.

Neither Reynolds' nor Eversharp's ballpoint lived up to consumer expectations in America. Ballpoint pen sales peaked in 1946, and consumer interest subsequently plunged due to market saturation, going from luxury good to fungible commodity. By the early 1950s the ballpoint boom had subsided and Reynolds' company folded.

Paper Mate pens, among the emerging ballpoint brands of the 1950s, bought the rights to distribute their own ballpoint pens in Canada. Facing concerns about ink-reliability, Paper Mate pioneered new ink formulas and advertised them as "banker-approved". In 1954, Parker Pens released "The Jotter"—the company's first ballpoint—boasting additional features and technological advances which also included the use of tungsten-carbide textured ball-bearings in their pens. In less than a year, Parker sold several million pens at prices between three and nine dollars. In the 1960s, the failing Eversharp Co. sold its pen division to Parker and ultimately folded.

Marcel Bich also introduced a ballpoint pen to the American marketplace in the 1950s, licensed from Bíró and based on the Argentine designs. Bich shortened his name to Bic in 1953, forming the ballpoint brand Bic now recognized globally. Bic pens struggled until the company launched its "Writes First Time, Every Time!" advertising campaign in the 1960s. Competition during this era forced unit prices to drop considerably.

Inks
Ballpoint pen ink is normally a paste containing around 25 to 40 percent dye. The dyes are suspended in a mixture of solvents and fatty acids. The most common of the solvents are benzyl alcohol or phenoxyethanol, which mix with the dyes and oils to create a smooth paste that dries quickly. The fatty acids help to lubricate the ball tip while writing. Hybrid inks also contain added lubricants in the ink to provide a smoother writing experience. The drying time of the ink varies depending upon the viscosity of the ink and the diameter of the ball.

In general, the more viscous the ink, the faster it will dry, but more writing pressure needs to be applied to dispense ink. But although they are less viscous, hybrid inks have a faster drying time compared to normal ballpoint inks. Also, a larger ball dispenses more ink and thus increases drying time.

The dyes used in blue and black ballpoint pens are basic dyes based on triarylmethane and acid dyes derived from diazo compounds or phthalocyanine. Common dyes in blue (and black) ink are Prussian blue, Victoria blue, methyl violet, crystal violet, and phthalocyanine blue. The dye eosin is commonly used for red ink.

The inks are resistant to water after drying but can be defaced by certain solvents which include acetone and various alcohols.

Types of ballpoint pens
Ballpoint pens are produced in both disposable and refillable models. Refills allow for the entire internal ink reservoir, including a ballpoint and socket, to be replaced. Such characteristics are usually associated with designer-type pens or those constructed of finer materials. The simplest types of ballpoint pens are disposable and have a cap to cover the tip when the pen is not in use, or a mechanism for retracting the tip, which varies between manufacturers but is usually a spring- or screw-mechanism.

Rollerball pens employ the same ballpoint mechanics, but with the use of water-based inks instead of oil-based inks. Compared to oil-based ballpoints, rollerball pens are said to provide more fluid ink-flow, but the water-based inks will blot if held stationary against the writing surface. Water-based inks also remain wet longer when freshly applied and are thus prone to "smearing"—posing problems to left-handed people (or right handed people writing right-to-left script)—and "running", should the writing surface become wet.

Some ballpoint pens use a hybrid ink formulation whose viscosity is lower than that of standard ballpoint ink, but greater than rollerball ink. The ink dries faster than a gel pen to prevent smearing when writing. These pens are better suited for left-handed persons. Examples are the Zebra Surari, Uni-ball Jetstream and Pilot Acroball ranges. These pens are also labelled "extra smooth", as they offer a smoother writing experience compared to normal ballpoint pens.

Ballpoint pens with erasable ink were pioneered by the Paper Mate pen company. The ink formulas of erasable ballpoints have properties similar to rubber cement, allowing the ink to be literally rubbed clean from the writing surface before drying and eventually becoming permanent. Erasable ink is much thicker than standard ballpoint inks, requiring pressurized cartridges to facilitate inkflow—meaning they can also write upside-down. Though these pens are equipped with erasers, any eraser will suffice.

The inexpensive, disposable Bic Cristal (also simply "Bic pen" or "Biro") is reportedly the most widely sold pen in the world. It was the Bic company's first product and is still synonymous with the company name. The Bic Cristal is part of the permanent collection at the Museum of Modern Art in New York City, acknowledged for its industrial design. Its hexagonal barrel mimics that of a wooden pencil and is transparent, showing the ink level in the reservoir. Originally a sealed streamlined cap, the modern pen cap has a small hole at the top to meet safety standards, helping to prevent suffocation if children suck it into the throat. Multi-pens are pens that feature multiple varying colored pen refills. Sometimes ballpoint refills are combined with another non-ballpoint refill, usually a mechanical pencil. Sometimes ballpoint pens combine a ballpoint tip on one end and touchscreen stylus on the other.

Ballpoint pens are sometimes provided free by businesses, such as hotels and banks, printed with a company's name and logo. Ballpoints have also been produced to commemorate events, such as a pen commemorating the 1963 assassination of President John F. Kennedy. These pens, known as "advertising pens," are the same as standard ballpoint pen models, but have become valued among collectors.

Sometimes ballpoint pens are also produced as design objects. With cases made of metal or wood, they become individually styled utility objects.

Use of ballpoint pens in space
It is generally believed that gravity is needed to coat the ball with ink. In fact most ballpoint pens on the Earth do not work when writing upside-down because the Earth's gravity pulls the ink inside the pen away from the tip of the pen. However, in the microgravity environment of space a regular ballpoint pen can still work, pointed in any direction, because the capillary forces in the ink are stronger than gravitational forces. The functionality of a regular ballpoint pen in space was confirmed by ESA astronaut Pedro Duque in 2003.

Technology developed by Fisher pens in the United States resulted in the production of what came to be known as the "Fisher Space Pen". Space Pens combine a more viscous ink with a pressurized ink reservoir that forces the ink toward the point. Unlike a standard ballpoint's ink container, the rear end of a Space Pen's pressurized reservoir is sealed, eliminating evaporation and leakage, thus allowing the pen to write upside-down, in zero-gravity environments, and allegedly underwater. Astronauts have made use of these pens in outer space.

As an art medium

The ballpoint pen has proven to be a versatile art medium for both professional artists and amateur doodlers. Low cost, availability, and portability are cited by practitioners as qualities which make this common writing tool a convenient art supply. Some artists use them within mixed-media works, while others use them solely as their medium-of-choice.

Effects not generally associated with ballpoint pens can be achieved. Traditional pen-and-ink techniques such as stippling and cross-hatching can be used to create half-tones or the illusion of form and volume. For artists whose interests necessitate precision line-work, ballpoints are an obvious attraction; ballpoint pens allow for sharp lines not as effectively executed using a brush. Finely applied, the resulting imagery has been mistaken for airbrushed artwork and photography, causing reactions of disbelief which ballpoint artist Lennie Mace refers to as the "Wow Factor".

Famous 20th-century artists including Andy Warhol, have utilized the ballpoint pen during their careers. Ballpoint pen artwork continues to attract interest in the 21st century, with many contemporary artists gaining recognition for their specific use of ballpoint pens as a medium. Korean-American artist Il Lee has been creating large-scale, abstract artwork since the late 1970s solely with ballpoint pens. Since the 1980s, Lennie Mace creates imaginative, ballpoint-only artwork of varying content and complexity, applied to unconventional surfaces including wood and denim. The artist coined terms such as "PENtings" and "Media Graffiti" to describe his varied output. British artist James Mylne has been creating photo-realistic artwork using mostly black ballpoints, sometimes with minimal mixed-media color.

The ballpoint pen has several limitations as an art medium. Color availability and sensitivity of ink to light are among concerns of ballpoint pen artists. As a tool that uses ink, marks made with a ballpoint pen can generally not be erased. Additionally, "blobbing" ink on the drawing surface and "skipping" ink-flow require consideration when drawing with a ballpoint pen. Although the mechanics of ballpoint pens remain relatively unchanged, ink composition has evolved to solve certain problems over the years, resulting in unpredictable sensitivity to light and some extent of fading.

Manufacturing
The common ballpoint pen is a product of mass production, with components produced separately on assembly lines. Basic steps in the manufacturing process include the production of ink formulas, molding of metal and plastic components, and assembly. Marcel Bich (leading to Société Bic) was involved in developing the production of inexpensive ballpoint pens.

Although designs and construction vary between brands, basic components of all ballpoint pens are universal. Standard components of a ballpoint tip include the freely rotating "ball" itself (distributing the ink on the writing surface), a "socket" holding the ball in place, small "ink channels" that provide ink to the ball through the socket, and a self-contained "ink reservoir" supplying ink to the ball. In modern disposable pens, narrow plastic tubes contain the ink, which is compelled downward to the ball by gravity. Brass, steel, or tungsten carbide are used to manufacture the ball bearing-like points, then housed in a brass socket.

The function of these components can be observed at a larger scale in the ball-applicator of roll-on antiperspirant. The ballpoint tip delivers the ink to the writing surface while acting as a "buffer" between the ink in the reservoir and the air outside, preventing the quick-drying ink from drying inside the reservoir. Modern ballpoints are said to have a two-year shelf life, on average.

A ballpoint tip that can write comfortably for a long period of time is not easy to produce, as it requires high-precision machinery and thin high-grade steel alloy plates. China, which produces about 80 percent of the world's ballpoint pens, relied on imported ballpoint tips and metal alloys before 2017.

Standards
The International Organization for Standardization has published standards for ball point and roller ball pens:

 * ISO 12756:1998: Drawing and writing instruments – Ball point pens – Vocabulary
 * ISO 12757-1:1998: Ball point pens and refills – Part 1: General use
 * ISO 12757-2:1998: Ball point pens and refills – Part 2: Documentary use (DOC)
 * ISO 14145-1:1998: Roller ball pens and refills – Part 1: General use
 * ISO 14145-2:1998: Roller ball pens and refills – Part 2: Documentary use (DOC)

Guinness World Records

 * The world's largest functioning ballpoint pen was made by Acharya Makunuri Srinivasa in India. The pen measures 5.4999 m long and weighs 37.23 kg.
 * The world's most popular pen is the Bic Cristal, with the 100 billonth model sold in September, 2006. The Bic Cristal was launched in December 1950 and roughly 57 are sold per second.

title: Ballpoint pen


text:
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.

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

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

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:

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)

 * 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

but this will not sort the entire list, as it exits the loop after the first iteration. the final condition ought to be 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  -- which is the same as  . Glrx (talk) 14:01, 9 May 2012 (UTC)

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 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:

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. 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  tracks the above paragraph. The outer loop is not a bounded   loop but un unbounded   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 Θ(n2) 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)

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Talk:Bubble sort


text:
Burroughs Corporation

The Burroughs Corporation was a major American manufacturer of business equipment. The company was founded in 1886 as the American Arithmometer Company by William Seward Burroughs. In 1986, it merged with Sperry UNIVAC to form Unisys. The company's history paralleled many of the major developments in computing. At its start, it produced mechanical adding machines, and later moved into programmable ledgers and then computers. It was one of the largest producers of mainframe computers in the world, also producing related equipment including typewriters and printers.

Early history

In 1886, the American Arithmometer Company was established in St. Louis, Missouri, to produce and sell an adding machine invented by William Seward Burroughs (grandfather of Beat Generation author William S. Burroughs). In 1904, six years after Burroughs' death, the company moved to Detroit and changed its name to the Burroughs Adding Machine Company. It was soon the biggest adding machine company in America.

Evolving product lines
The adding machine range began with the basic, hand-cranked Class 1 which was only capable of adding. The design included some revolutionary features, foremost of which was the dashpot which governed the speed at which the operating lever could be pulled so allowing the mechanism to operate consistently correctly. The machine also had a full-keyboard with a separate column of keys 1 to 9 for each decade where the keys latch when pressed, with interlocking which prevented more than one key in any decade from being latched. The latching allowed the operator to quickly check that the correct number had been entered before pulling the operating lever. The numbers entered and the final total were printed on a roll of paper at the rear, so there was no danger of the operator writing down the wrong answer and there was a copy of the calculation which could be checked later if necessary.

The Class 2 machine, called the "duplex" and built in the same basic style, provided a means of keeping two separate totals. The Class 6 machine was built for bookkeeping work and provided the ability for direct subtraction.

Burroughs released the Class 3 and Class 4 adding machines which were built after the purchase of the Pike Adding Machine Company around 1910. These machines provided a significant improvement over the older models because operators could view the printing on the paper tape. The machines were called "the visible" for this improvement.

In 1925 Burroughs released a much smaller machine called "the portable". Two models were released, the Class 8 (without subtraction) and the Class 9 with subtraction capability. Later models continued to be released with the P600 and top-of-the-range P612 offered some limited programmability based upon the position of the movable carriage. The range was further extended by the inclusion of the Series J ten-key machines which provided a single finger calculation facility, and the Class 5 (later called Series C) key-driven calculators in both manual and electrical assisted comptometers.

In the late 1960s, the Burroughs sponsored "nixi-tube" provided an electronic display calculator. Burroughs developed a range of adding machines with different capabilities, gradually increasing in their capabilities. A revolutionary adding machine was the Sensimatic, which was able to perform many business functions semi-automatically. It had a moving programmable carriage to maintain ledgers. It could store 9, 18 or 27 balances during the ledger posting operations and worked with a mechanical adder named a Crossfooter. The Sensimatic developed into the Sensitronic which could store balances on a magnetic stripe which was part of the ledger card. This balance was read into the accumulator when the card was inserted into the carriage. The Sensitronic was followed by the E1000, E2000, E3000, E4000, E6000 and the E8000, which were computer systems supporting card reader/punches and a line printer.

Later, Burroughs was selling more than adding machines, including typewriters.

Move into computers
The biggest shift in company history came in 1953: the Burroughs Adding Machine Company was renamed the Burroughs Corporation and began moving into digital computer products, initially for banking institutions. This move began with Burroughs' purchase in June 1956, of the ElectroData Corporation in Pasadena, California, a spinoff of the Consolidated Engineering Corporation which had designed test instruments and had a cooperative relationship with Caltech in Pasadena. ElectroData had built the Datatron 205 and was working on the Datatron 220. The first major computer product that came from this marriage was the B205 tube computer. In 1968 the L and TC series range was produced (e.g. the TC500—Terminal Computer 500) which had a golf ball printer and in the beginning a 1K (64 bit) disk memory. These were popular as branch terminals to the B5500/6500/6700 systems, and sold well in the banking sector, where they were often connected to non-Burroughs mainframes. In conjunction with these products, Burroughs also manufactured an extensive range of cheque processing equipment, normally attached as terminals to a medium systems such as B200/B300 and larger systems such as a B2700 or B1700.

In the 1950s, Burroughs worked with the Federal Reserve Bank on the development and computer processing of magnetic ink character recognition (MICR) especially for the processing of bank cheques. Burroughs made special MICR/OCR sorter/readers which attached to their medium systems line of computers (2700/3700/4700) and B200/B300 systems and this entrenched the company in the computer side of the banking industry.

A force in the computing industry
Burroughs was one of the nine major United States computer companies in the 1960s, with IBM the largest, Honeywell, NCR Corporation, Control Data Corporation (CDC), General Electric (GE), Digital Equipment Corporation (DEC), RCA and Sperry Rand (UNIVAC line). In terms of sales, Burroughs was always a distant second to IBM. In fact, IBM's market share was so much larger than all of the others that this group was often referred to as "IBM and the Seven Dwarves." By 1972 when GE and RCA were no longer in the mainframe business, the remaining five companies behind IBM became known as the BUNCH, an acronym based on their initials.

At the same time, Burroughs was very much a competitor. Like IBM, Burroughs tried to supply a complete line of products for its customers, including Burroughs-designed printers, disk drives, tape drives, computer printing paper and typewriter ribbons.

Developments and innovations
The Burroughs Corporation developed three highly innovative architectures, based on the design philosophy of "language-directed design". Their machine instruction sets favored one or many high level programming languages, such as ALGOL, COBOL or FORTRAN. All three architectures were considered mainframe class machines:
 * The Burroughs Large Systems machines started with the B5000 in 1961. The B5500 came a few years later when large rotating disks replaced drums as the main external memory media. These B5000 Series systems used the world's first virtual memory multi-programming operating system.  They were followed by the B6500/B6700 in the later 1960s, the B7700 in the mid 1970s, and the A series in the 1980s. The underlying architecture of these machines is similar and continues today as the Unisys ClearPath MCP line of computers: stack machines designed to be programmed in an extended Algol 60. Their operating systems, called MCP (Master Control Program—the name later borrowed by the screenwriters for Tron), were programmed in ESPOL (Executive Systems Programming Oriented Language, a minor extension of ALGOL) and DCALGOL (Data Communications ALGOL) and later in NEWP (with further extensions to ALGOL) almost a decade before Unix. The command interface developed into a compiled structured language with declarations, statements and procedures called WFL (Work Flow Language).

Many computer scientists consider these series of computers to be technologically groundbreaking. Stack oriented processors, with 48 bit word length where each word was defined as data or program contributed significantly to a secure operating environment, long before spyware and viruses affected computing. The modularity of these large systems was unique: multiple CPUs, multiple memory modules and multiple I/O and Data Comm processors permitted incremental and cost effective growth of system performance and reliability.

In industries like banking, where continuous operations was mandatory, Burroughs Large Systems penetrated nearly every large bank, including the Federal Reserve Bank. Burroughs built the backbone switching systems for Society for Worldwide Interbank Financial Telecommunication (SWIFT) which sent its first message in 1977. Unisys is still the provider to SWIFT today.

 * Burroughs produced the B2500 or "medium systems" computers aimed primarily at the business world. The machines were designed to execute COBOL efficiently. This included a BCD (Binary Coded Decimal) based arithmetic unit, storing and addressing the main memory using base 10 numbering instead of binary. The designation for these systems was Burroughs B2500 through B49xx, followed by Unisys V-Series V340 through V560.
 * Burroughs produced the B1700 or "small systems" computers that were designed to be microprogrammed, with each process potentially getting its own virtual machine designed to be the best match to the programming language chosen for the program being run.
 * The smallest general-purpose computers were the B700 "microprocessors" which were used both as stand-alone systems and as special-purpose data-communications or disk-subsystem controllers.
 * Burroughs manufactured an extensive range of accounting machines including stand-alone systems such as the Sensimatic, L500 and B80 and dedicated terminals including the TC500 and specialised check processing equipment.
 * In 1982, Burroughs began producing personal computers, the B20 and B25 lines with the Intel 8086/8088 family of 16-bit chips as the processor. These ran the BTOS operating system, which Burroughs licensed from Convergent Technologies. These machines implemented an early local area network to share a hard disk between workgroup users. These microcomputers were later manufactured in Kunming, China for use in China under agreement with Burroughs.
 * Burroughs collaborated with University of Illinois on a multiprocessor architecture developing the ILLIAC IV computer in the early 1960s. The ILLIAC had up to 128 parallel processors while the B6700 & B7700 only accommodated a total of 7 CPUs and/or I/O units (the 8th unit was the memory tester).
 * Burroughs made military computers, such as the D825 (the "D" prefix signifying it was for defense industrial use), in its Great Valley Laboratory in Paoli, Pennsylvania. The D825 was, according to some scholars, the first true multiprocessor computer. Paoli was also home to the Defense and Space Group Marketing Division.
 * In 1964 Burroughs had completed the D830 which was another variation of the D825 designed specifically for real-time applications, such as airline reservations. Burroughs designated the B8300 after Trans World Airlines (TWA) ordered one in September 1965. A system with three instruction processors was installed at TWA's reservations center in Rockleigh, New Jersey in 1968. The system, which was called George, with an application programmed in JOVIAL, was intended to support some 4000 terminals, but the system experienced repeated crashes due to a filing system disk allocation error when operating under a large load. A fourth processor was added but did nothing to resolve the problem. The problem was resolved in late 1970 and the system became stable. The decision to cancel the project was being made at the very time that the problem was resolved. TWA cancelled the project and acquired one IBM System/360 Model 75, two IBM System/360 model 65s, and IBM's PARS software for its reservations system. TWA sued Burroughs for non-fulfillment of the contract, but Burroughs counter-sued, stating that the basic system did work and that the problems were in TWA's applications software. The two companies reached an out-of-court settlement.
 * Burroughs developed a half-size version of the D825 called the D82, cutting the word size from 48 to 24 bits and simplifying the computer's instruction set. The D82 could have up to 32,768 words of core memory and continued the use of separate instruction and I/O processors. Burroughs sold a D82 to Air Canada to handle reservations for trips originating in Montreal and Quebec. This design was further refined and made much more compact as the D84 machine which was completed in 1965. A D84 processor/memory unit with 4096 words of memory occupied just 1.4 cuft. This system was used successfully in two military projects: field test systems used to check the electronics of the Air Force General Dynamics F-111 Aardvark fighter plane and systems used to control the countdown and launch of the Army's Pershing 1 and 1a missile systems.

Merger with Sperry
In September 1986, Burroughs Corporation merged with Sperry Corporation to form Unisys. For a time, the combined company retained the Burroughs processors as the A- and V-systems lines. As the market for large systems shifted from proprietary architectures to common servers, the company eventually dropped the V-Series line, although customers continued to use V-series systems. Unisys continues to develop and market the A-Series, now known as ClearPath.

Burroughs Payment Systems
In 2010, Unisys sold off its Payment Systems Division to Marlin Equity Partners, a California-based private investment firm, which incorporated it as Burroughs Payment Systems, Inc. (later just Burroughs, Inc.), based in Plymouth, Michigan.

References in popular culture
Burroughs B205 hardware has appeared as props in many Hollywood television and film productions from the late 1950s. For example, a B205 console was often shown in the television series Batman as the Bat Computer; also as the flight computer in Lost in Space. B205 tape drives were often seen in series such as The Time Tunnel and Voyage to the Bottom of the Sea. Burroughs equipment was also featured in the movie The Angry Red Planet.

title: Burroughs Corporation