May the source be with you, but remember the KISS principle ;-)
Home Switchboard Unix Administration Red Hat TCP/IP Networks Neoliberalism Toxic Managers
(slightly skeptical) Educational society promoting "Back to basics" movement against IT overcomplexity and  bastardization of classic Unix



Sorting algorithms Recommended Books Recommended Links Shaker sort Insertion sort
Animations Testing Sorting Algorithms Donald Knuth The Art of Computer Programming Humor Etc

This horrible bubblesort algorithm tortured generations of students who take programming classes ;-).

In reality, bubblesort is an extremely simple algorithm the most distinctive feature of which is that this is most often incorrectly implemented sorting algorithms in existence. Looks like few writes of bubblesort even open Knuth.

It is not only incorrectly implemented in popular web pages, it is also  often implemented incorrectly in textbooks and animations :-). Again, bubblesort is probably the champion of incorrect implementations among simple sorting algorithms

Bubblesort is probably the champion of incorrect implementations among simple sorting algorithms  

The idea is to swap adjacent elements, if the elements are out of order, moving up or down the data set. Usually multiple passes are necessary.  Each subsequent pass is shorter as elements after the last swap are already sorted (it is this element that is often missed in "naive" implementations that dominate the web). It terminated as soon as no swaps were performed during the pass.  See animation to get better idea of the details

On any set of data it is less efficient then Insertion sort so it has purely theoretical value as it has some interesting properties. Like insertion sort it is a stable sorting algorithm. 

See Reversed Initial Order - Sorting Algorithm Animations for nice animation

An interesting and often overlooked feature of the algorithm is that the last swap signify the boundary of the already sorted part of the array.  In this sense bubblesort is similar to selection sort as on each pass the maximum or minimum element in the unsorted part is found and subsequent sort can be done on a subset that is smaller then initial by one or more elements (the place of last swap is the boundary). 

Speed with which largest element "sinks" is high -- he occupies its proper place in one pass, but the speed with which small element "floats up" is slow:  only one exchange is done on each path. That's why sometimes largest elements in bubble sort are called "rabbits" and smallest "tortoises".

But it's details of the implementation that are presented are often incorrect. For example Robert Sedgewick's implementation Algorithms in Java, Third Edition, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching is definitely wrong (too primitive to be exact) and does not corresponds to Donald Knuth's version:

static void bubble(ITEM[] a, int l, int r) 
  { for (int i = l; i < r; i++) 
      for (int j = r; j > i; j--) 
        compExch(a, j-1, j); 

As most implementations of bubblesort presented on the web and some implementations in the textbooks are incorrect it is important to understand two properties of the correct implementation of bubblesort:

  1. If there are no exchanges then the sorting is complete (the simplistic implementation above does not have even this feature; it should generally be avoided).
  2. Each next pass ends at the last swap of the previous pass.  It does not make any sense to continue comparing elements below this point.
Two properties of the correct implementation of bubblesort:
  1. If there are no exchanges, then the sorting is complete .
  2. Each next pass ends at the last swap of the previous pass.

Here is the reimplementation of the algorithm as it was discussed by Knuth: 

void bubbleSort(int a[], int n)
/* Sorts in increasing order the array A of the size N */
  int k;
  int bound = n-1;
  int t;
  int last_swap;
  while (bound) {
    last_swap = 0;
    for ( k=0; k<bound; k++ )
       t = a[k]; /* t is a maximum of A[0]..A[k] */
       if ( t > a[k+1] ) {
         a[k] = a[k+1]; a[k+1] = t; /*swap*/
         last_swap = k; /* mark the last swap position */
    bound=last_swap; /*elements after bound are already sorted */       
} // bubbleSort


There the valuable bound determines when the sorting is finished and it is assigned the position of the last swap. The part of the code that "drags" maximum element to the bottom is sometimes called "bubblemax" and can be coded as subroutines but that does not make much sense.  You can also double this part of algorithm adding "bubblemin" pass on the opposite direction to compensate for the slowness with which minimum elements are "bubbling up" while max element is "sinking" in a single pass. This enhancement to bidirectional bubblesort is known also as shaker sort. But the question is whether this enhancement worth the additional complexity as there are more efficient algorithms of comparable complexity which achieve the same goals (first of all Mergesort).

If you were to watch a graphical representation of the sorting occurring, you would see that each path the smallest element gets "bubbled" up to the top, while the largest element is sinking to the bottom.   

One of the few advantages of Bubblesort is that like insertion sort it is a natural algorithm to be used on lists.  It is also works very well on already sorted lists, or lists with just few permutations. If there is just one permutation the algorithm requires just one pass to sort. 

It is possible to increase the speed of Bubblesort, but only at the cost of increased complexity of the code. One trivial enhancement is to make it symmetrical alternating passes in each direction. This variant is often called cocktail sort (implementations at Wikipedia are incorrect) or shaker short. It works much better is only works much better when some small and large items are swapped in the data set and concentrated on the "wrong end".

The other possibility is shorten the size of the pass based on observation that the element before the first swap can be used for the beginning of next pass: previous elements cannot change their places as they are in partial order. This adds to total number of comparison as check for the first swaps will be performed for each swap.   See C++ Notes Algorithms More Bubble Sorts for the implementation of this idea.

Top Visited
Past week
Past month


Old News ;-)

[Dec 27, 2018] Comb sort - Wikipedia

Dec 27, 2018 |

Comb sort is a relatively simple sorting algorithm originally designed by Włodzimierz Dobosiewicz in 1980. [1] [2] Later it was rediscovered by Stephen Lacey and Richard Box in 1991. [3] Comb sort improves on bubble sort . Contents

Algorithm [ edit ]

The basic idea is to eliminate turtles , or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously. Rabbits , large values around the beginning of the list, do not pose a problem in bubble sort.

In bubble sort , when any two elements are compared, they always have a gap (distance from each other) of 1. The basic idea of comb sort is that the gap can be much more than 1. The inner loop of bubble sort, which does the actual swap , is modified such that gap between swapped elements goes down (for each iteration of outer loop) in steps of a "shrink factor" k : [ n / k , n / k 2 , n / k 3 , ..., 1 ].

The gap starts out as the length of the list n being sorted divided by the shrink factor k (generally 1.3; see below) and one pass of the aforementioned modified bubble sort is applied with that gap. Then the gap is divided by the shrink factor again, the list is sorted with this new gap, and the process repeats until the gap is 1. At this point, comb sort continues using a gap of 1 until the list is fully sorted. The final stage of the sort is thus equivalent to a bubble sort, but by this time most turtles have been dealt with, so a bubble sort will be efficient.

The shrink factor has a great effect on the efficiency of comb sort. k = 1.3 has been suggested as an ideal shrink factor by the authors of the original article after empirical testing on over 200,000 random lists. A value too small slows the algorithm down by making unnecessarily many comparisons, whereas a value too large fails to effectively deal with turtles, making it require many passes with 1 gap size.

The pattern of repeated sorting passes with decreasing gaps is similar to Shellsort , but in Shellsort the array is sorted completely each pass before going on to the next-smallest gap. Comb sort's passes do not completely sort the elements. This is the reason that Shellsort gap sequences have a larger optimal shrink factor of about 2.2.


 function combsort(array input)

    gap := input.size // Initialize gap size
    shrink := 1.3 // Set the gap shrink factor
    sorted := false

    loop while sorted = false
        // Update the gap value for a next comb
        gap := floor(gap / shrink)
        if gap ≤ 1
            gap := 1
            sorted := true // If there are no swaps this pass, we are done
        end if

        // A single "comb" over the input list
        i := 0
        loop while i + gap < input.size // See Shell sort for a similar idea
            if input[i] > input[i+gap]
                swap(input[i], input[i+gap])
                sorted := false
                // If this assignment never happens within the loop,
                // then there have been no swaps and the list is sorted.
             end if

             i := i + 1
         end loop

     end loop
 end function


Incorrect implementation, but good animation including random, nearly sorted, reverses and few unique data samples. It's visible how inefficient bubblesort is on reversely sorted data array.

Bubble Sort

Several implementation in Perl, Python and C++ using swap subroutine. Does not too correct to me.

Bubble sort misconceptions

Bubble Sort is Never the Answer

It is not too often in the real world that you have to implement your own sort. Generally, whatever language you are using has a library with this functionality built in. If the occasion does arise, however, it is important to understand which algorithms are applicable in which situations. As with most choices, there is no absolute correct answer; there are many trade offs to consider. When choosing an algorithm there are three things you should consider: performance, overhead, and ease of implementation.

You should give equal consideration to each of these factors, disregarding any one of them can lead to poor choices. It is common, for instance, for people to ignore the ease of implementation and focus on the performance of the algorithm. The problem with this is that not every operation is critical. No one is going to die if they songs on their play list do not get sorted quickly enough. Programmer time is more expensive than run time as a professor of mine often said. In addition to this, some high performance algorithms can slower than simpler algorithms due to overhead. If you are sorting 100 items, you can probably insertion sort them just as fast or faster than you can heap sort them. The same would not be true with one million items; heap sort would be faster.

Once we consider all of the factors, you should find that no one algorithm is ideal in every case. There are some algorithms, however, that are not ideal in any case. Unfortunately one of these algorithms is among the most popular: bubble sort. Bubble sort is a very simple algorithm to implement and it has little overhead. The problem lies in its performance. You might think that this conflicts with my earlier point that even simple, low performance algorithms can be faster than others in the right situation. You also might think that bubble sort, being easy to implement, makes up for its performance short comings. This would be true, if it were not the case that there are algorithms that are equally simple to implement, require just as little overhead, and perform better in practice.

Insertion sort is one such algorithm. Like bubble sort it is an in place sort, and is just as easy to implement. Both algorithms have the same time complexity (O notation), but in practice insertion sort performs better in most cases. This being the case you may wonder why bubble sort is even around. Certainly if it is obsolete pages regarding its implementation should be torn out of books and mentioning it should be punishable by a swift slap with a keyboard. Maybe not. When I learned bubble sort it was as an example of how not to sort. In my non-expert opinion, it is equally important to understand how NOT to do things as it is important to understand how TO do them. My point? Learn bubble sort, but never use it.

[Oct 09, 2010] C++ Notes Algorithms More Bubble Sorts

Here are some additional variations on bubble sort.

Bubble Sort -- stop when no exchanges

This version of bubble sort continues making passes over the array as long as there were any exchanges. If the array is already sorted, this sort will stop after only one pass.
 void bubbleSort2(int x[], int n) {
    bool exchanges;
    do {
       exchanges = false;  // assume no exchanges
       for (int i=0; i<n-1; i++) {
          if (x[i] > x[i+1]) {
             int temp = x[i]; x[i] = x[i+1]; x[i+1] = temp;
             exchanges = true;  // after exchange, must look again
    } while (exchanges);
Disadvantage: This algorithm doesn't shorten the range each time by 1 as it could. See below.

Bubble Sort -- stop when no exchanges, shorter range each time

This version of bubble sort combines ideas from the previous versions. It stops when there are no more exchanges, and it also sorts a smaller range each time.
void bubbleSort3(int x[], int n) {
  bool exchanges;
  do {
    n--;               // make loop smaller each time.
    exchanges = false; // assume this is last pass over array
    for (int i=0; i<n; i++) {
      if (x[i] > x[i+1]) {
        int temp = x[i];  x[i] = x[i+1];  x[i+1] = temp;
        exchanges = true;  // after an exchange, must look again 
  } while (exchanges);
Disadvantage: After the first pass it may not be necessary to examine the entire range of the array -- only from where the lowest exchange occurred to where the highest exchange occurred. The parts above and below must already be sorted. See below.

Bubble Sort -- Sort only necessary range

Here's a version of bubble sort that, on each pass, looks only at the region of array where more exchanges might be necessary.
//========================================================= bubbleSortRange
// After a pass in bubble sort, it's only necessary to sort from just 
// below the first exchange (small values may move lower)
// to just before the last exchange (largest values won't move higher). 
// Everything that wasn't exchanged must be in the correct order. 
// After each pass, the upper and lower bounds for the next pass are
// set from the positions of the first and last exchanges on prev pass.

void bubbleSortRange(int x[], int n) {
    int lowerBound = 0;    // First position to compare.
    int upperBound = n;    // First position NOT to compare.
    //--- Continue making passes while there is a potential exchange.
    while (lowerBound <= upperBound) {
        int firstExchange = n;  // assume impossibly high index for low end.
        int lastExchange  = -1; // assume impossibly low index for high end.
        //--- Make a pass over the appropriate range.
        for (int i=lowerBound; i<upperBound; i++) {
            if (x[i] > x[i+1]) {
                //--- exchange elements
                int temp = x[i];  x[i] = x[i+1];  x[i+1] = temp;
                //--- Remember first and last exchange indexes.
                if (i<firstExchange) { // true only for first exchange.
                    firstExchange = i;
                lastExchange = i;
        //--- Prepare limits for next pass.
        lowerBound = firstExchange-1;
        if (lowerBound < 0) {
            lowerBound = 0;
        upperBound = lastExchange;
}//end bubbleSortRange
The text from the above example can be selected, copied, and pasted into an editor.
Disadvantage: Notice that the largest unsorted element will always be moved all the way to its correct position in the array, but small elements are shifted down by only one place on each pass.

Other bubble sorts

Note that in all these sorts the part that is sorted grows at only one end of the array. The ability to quit early is not symmetrical. The extreme values move all the way to the end in one direction, but only one place in the other direction. The algorithm can be improved by alternately "bubbling" in opposite directions.

[Oct 09, 2010] Simple Sorting in Java Bubble Sort

Java class pornography or how not to program bubblesort ;-)

LISTING 3.1 The Program

// demonstrates bubble sort
// to run this program: C>java BubbleSortApp
class ArrayBub
  private long[] a;         // ref to array a
  private int nElems;        // number of data items
  public ArrayBub(int max)     // constructor
   a = new long[max];         // create the array
   nElems = 0;            // no items yet
  public void insert(long value)  // put element into array
   a[nElems] = value;       // insert it
   nElems++;           // increment size
  public void display()       // displays array contents
   for(int j=0; j<nElems; j++)    // for each element,
     System.out.print(a[j] + " "); // display it
  public void bubbleSort()
   int out, in;

   for(out=nElems-1; out>1; out--)  // outer loop (backward)
     for(in=0; in<out; in++)    // inner loop (forward)
      if( a[in] > a[in+1] )    // out of order?
        swap(in, in+1);     // swap them
   } // end bubbleSort()
  private void swap(int one, int two)
   long temp = a[one];
   a[one] = a[two];
   a[two] = temp;
  } // end class ArrayBub
class BubbleSortApp
  public static void main(String[] args)
   int maxSize = 100;      // array size
   ArrayBub arr;         // reference to array
   arr = new ArrayBub(maxSize); // create the array

   arr.insert(77);        // insert 10 items

   arr.display();        // display items

   arr.bubbleSort();       // bubble sort them

   arr.display();        // display them again
   } // end main()
  } // end class BubbleSortApp

The constructor and the insert() and display() methods of this class are similar to those we've seen before. However, there's a new method: bubbleSort(). When this method is invoked from main(), the contents of the array are rearranged into sorted order.

The main() routine inserts 10 items into the array in random order, displays the array, calls bubbleSort() to sort it, and then displays it again. Here's the output:

77 99 44 55 22 88 11 0 66 33
0 11 22 33 44 55 66 77 88 99

The bubbleSort() method is only four lines long. Here it is, extracted from the listing:

public void bubbleSort()
  int out, in;

  for(out=nElems-1; out>1; out--)  // outer loop (backward)
   for(in=0; in<out; in++)    // inner loop (forward)
     if( a[in] > a[in+1] )    // out of order?
      swap(in, in+1);     // swap them
  } // end bubbleSort()

[Apr 10, 2009] Bubble Sort - C++, Java, Algorithm and Data Structure Tutorials by Denis Kulagin

Contains Java and C++ implementation with "swap check".
  1. Bubble Sort Animation (with source code line by line visualization)
  2. Bubble Sort in Java Applets Centre
  3. Animated Sorting Algorithms: Bubble Sort

Recommended Links

Google matched content

Softpanorama Recommended

Top articles


Shaker sort
(bidirectional bubblesort)

Bubble sort (double direction)

bidirectional bubble sort

Definition: A variant of bubble sort which compares each adjacent pairs of items in a list in turn, swapping them if necessary, and alternately passes through the list from the beginning to the end then from the end to the beginning until no swaps are done.

Also known as cocktail shaker sort, shaker sort, double-direction bubble sort.

See also sort.

Note: Complexity is O(n2) for arbitrary data, but approaches O(n) if the list is nearly in order at the beginning. Bidirectional bubble sort usually does better than bubble sort since at least one item is moved forward or backward to its place in the list with each pass. Bubble sort moves items forward into place, but can only move items backward one location each pass.

Authors: PEB,BB

Bidirectional Bubble Sort Algorithm Demo



Groupthink : Two Party System as Polyarchy : Corruption of Regulators : Bureaucracies : Understanding Micromanagers and Control Freaks : Toxic Managers :   Harvard Mafia : Diplomatic Communication : Surviving a Bad Performance Review : Insufficient Retirement Funds as Immanent Problem of Neoliberal Regime : PseudoScience : Who Rules America : Neoliberalism  : The Iron Law of Oligarchy : Libertarian Philosophy


War and Peace : Skeptical Finance : John Kenneth Galbraith :Talleyrand : Oscar Wilde : Otto Von Bismarck : Keynes : George Carlin : Skeptics : Propaganda  : SE quotes : Language Design and Programming Quotes : Random IT-related quotesSomerset Maugham : Marcus Aurelius : Kurt Vonnegut : Eric Hoffer : Winston Churchill : Napoleon Bonaparte : Ambrose BierceBernard Shaw : Mark Twain Quotes


Vol 25, No.12 (December, 2013) Rational Fools vs. Efficient Crooks The efficient markets hypothesis : Political Skeptic Bulletin, 2013 : Unemployment Bulletin, 2010 :  Vol 23, No.10 (October, 2011) An observation about corporate security departments : Slightly Skeptical Euromaydan Chronicles, June 2014 : Greenspan legacy bulletin, 2008 : Vol 25, No.10 (October, 2013) Cryptolocker Trojan (Win32/Crilock.A) : Vol 25, No.08 (August, 2013) Cloud providers as intelligence collection hubs : Financial Humor Bulletin, 2010 : Inequality Bulletin, 2009 : Financial Humor Bulletin, 2008 : Copyleft Problems Bulletin, 2004 : Financial Humor Bulletin, 2011 : Energy Bulletin, 2010 : Malware Protection Bulletin, 2010 : Vol 26, No.1 (January, 2013) Object-Oriented Cult : Political Skeptic Bulletin, 2011 : Vol 23, No.11 (November, 2011) Softpanorama classification of sysadmin horror stories : Vol 25, No.05 (May, 2013) Corporate bullshit as a communication method  : Vol 25, No.06 (June, 2013) A Note on the Relationship of Brooks Law and Conway Law


Fifty glorious years (1950-2000): the triumph of the US computer engineering : Donald Knuth : TAoCP and its Influence of Computer Science : Richard Stallman : Linus Torvalds  : Larry Wall  : John K. Ousterhout : CTSS : Multix OS Unix History : Unix shell history : VI editor : History of pipes concept : Solaris : MS DOSProgramming Languages History : PL/1 : Simula 67 : C : History of GCC developmentScripting Languages : Perl history   : OS History : Mail : DNS : SSH : CPU Instruction Sets : SPARC systems 1987-2006 : Norton Commander : Norton Utilities : Norton Ghost : Frontpage history : Malware Defense History : GNU Screen : OSS early history

Classic books:

The Peter Principle : Parkinson Law : 1984 : The Mythical Man-MonthHow to Solve It by George Polya : The Art of Computer Programming : The Elements of Programming Style : The Unix Haterís Handbook : The Jargon file : The True Believer : Programming Pearls : The Good Soldier Svejk : The Power Elite

Most popular humor pages:

Manifest of the Softpanorama IT Slacker Society : Ten Commandments of the IT Slackers Society : Computer Humor Collection : BSD Logo Story : The Cuckoo's Egg : IT Slang : C++ Humor : ARE YOU A BBS ADDICT? : The Perl Purity Test : Object oriented programmers of all nations : Financial Humor : Financial Humor Bulletin, 2008 : Financial Humor Bulletin, 2010 : The Most Comprehensive Collection of Editor-related Humor : Programming Language Humor : Goldman Sachs related humor : Greenspan humor : C Humor : Scripting Humor : Real Programmers Humor : Web Humor : GPL-related Humor : OFM Humor : Politically Incorrect Humor : IDS Humor : "Linux Sucks" Humor : Russian Musical Humor : Best Russian Programmer Humor : Microsoft plans to buy Catholic Church : Richard Stallman Related Humor : Admin Humor : Perl-related Humor : Linus Torvalds Related humor : PseudoScience Related Humor : Networking Humor : Shell Humor : Financial Humor Bulletin, 2011 : Financial Humor Bulletin, 2012 : Financial Humor Bulletin, 2013 : Java Humor : Software Engineering Humor : Sun Solaris Related Humor : Education Humor : IBM Humor : Assembler-related Humor : VIM Humor : Computer Viruses Humor : Bright tomorrow is rescheduled to a day after tomorrow : Classic Computer Humor

The Last but not Least Technology is dominated by two types of people: those who understand what they do not manage and those who manage what they do not understand ~Archibald Putt. Ph.D

Copyright © 1996-2021 by Softpanorama Society. was initially created as a service to the (now defunct) UN Sustainable Development Networking Programme (SDNP) without any remuneration. This document is an industrial compilation designed and created exclusively for educational use and is distributed under the Softpanorama Content License. Original materials copyright belong to respective owners. Quotes are made for educational purposes only in compliance with the fair use doctrine.

FAIR USE NOTICE This site contains copyrighted material the use of which has not always been specifically authorized by the copyright owner. We are making such material available to advance understanding of computer science, IT technology, economic, scientific, and social issues. We believe this constitutes a 'fair use' of any such copyrighted material as provided by section 107 of the US Copyright Law according to which such material can be distributed without profit exclusively for research and educational purposes.

This is a Spartan WHYFF (We Help You For Free) site written by people for whom English is not a native language. Grammar and spelling errors should be expected. The site contain some broken links as it develops like a living tree...

You can use PayPal to to buy a cup of coffee for authors of this site


The statements, views and opinions presented on this web page are those of the author (or referenced source) and are not endorsed by, nor do they necessarily reflect, the opinions of the Softpanorama society. We do not warrant the correctness of the information provided or its fitness for any purpose. The site uses AdSense so you need to be aware of Google privacy policy. You you do not want to be tracked by Google please disable Javascript for this site. This site is perfectly usable without Javascript.

Last modified: December 29, 2018