Bubble Sort

1) In bubble sort, we start from left to right and move the largest element to right.
2) In next round, we again start from left to right but stop at right - 1
3) In next round, , we again start from left to right but stop at right - 2
4) Ideally bubble sort is called bubble sort because when we so many bubbles in a jar, the biggest bubble reaches at the top.

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


Efficiency :- O(N2) as there are two loops