[macosxnerd101]

Bubblesort is probably the most basic and inefficient sorting algorithm, and something no one would probably do in real life. Basically, the algorithm iterates through the collection, examining two consecutive elements at a time starting at array[0] and array[1], swapping them if necessary. It then proceeds to elements 1 and 2 in the array, all the way to array[length-2] and array[length-1]. The algorithm then starts all over at the beggining. So when does the algorithm stop? The termination condition is when an entire iteration is made without swapping any elements. When it comes down to the efficiency, Bubblesort has a time complexity of O(n^2), and takes way more time than its quadratic counterparts Insertion and Selection Sorts.

So now that we understand how Bubblesort works, let's take a look at some pseudo-code.

bubblesort(array x){
    boolean sorted <-- true
    do{
        for i <-- 0 to x.length, incrementing i = i+1
            if(x[i] > x[i+1]){
                swap(x[i], x[i+1])
                sorted <-- false
            }
        end FOR
    }while(NOT sorted)
}

One thing I notice right off the bat is that on every swap, we also modify the value of a boolean. So if we make 1000 swaps, we take another 1000 steps to deal with our boolean. On top of that, our inner for loop takes linear time, and the outer loop takes approximately linear time as well. So n*n --> O(n^2).

[AdamSpeight2008]

Bubble Sort isn't n^2 but n * (n Log 2)

For example

For Outer = 0 To n-2
 For Inner = Outer + 1 To n-1
  If Element(Outer) > Element(Inner) Then Swap Elements
 Next Inner
Next Outer

[macosxnerd101]

Log(2) is a constant, so for the purposes of Big-O, I drop the constant. However, for all practicality, that would explain the drastic difference in runtime for Bubblesort vs. other sorting algorithms.