Bubble Sort is also referred sometimes as Sinking Sort. It is simple algorithm which is best suited for small lists only. It compares two adjacent elements and swap them if they are not in correct order. The name Bubble is given as in each comparison the small element bubbles to the top. This algorithm is very simple and too slow making it impractical to use for most of the problems.

Performance

Its best case performance is : O(n) when the list is already sorted.
Its Average / Worst case performance are equal i.e., : O(n^2)

So it should be avoided in case of large lists and also if your list or the collection is in reverse order.

How Bubble Sort Works

In the process of sorting you have to traverse the list multiple times. Traversing here is termed as Pass. So you can say that Sorting is performed in multiple passes.
Here adjacent elements are compared with each other and if they are not in their correct order, they are swapped with each other.

Step By Step Example

Let us suppose we have an unordered list here: (5 2 6 7 3). Consider sort it in ascending order (lowest first). Elements in bold are being compared.

Pass 1:

(5 2 6 7 3) —————-> (2 5 6 7 3), here algorithm compares 1st two elements, swap since 5>2
(2 5 6 7 3) —————-> (2 5 6 7 3), no swap since elements are in order. (6>5)
(2 5 6 7 3) —————-> (2 5 6 7 3), no swap since elements are in order. (7>6)
(2 5 6 7 3) —————-> (2 5 6 3 7), swap since 7>3

Pass 2:

(2 5 6 3 7) —————-> (2 5 6 3 7), in order
(2 5 6 3 7) —————-> (2 5 6 3 7), in order
(2 5 6 3 7) —————-> (2 5 3 6 7), swap since 6>3

Pass 3:

(2 5 3 6 7) —————-> (2 5 3 6 7), in order
(2 5 3 6 7) —————-> (2 3 5 6 7), swap since 5>3

Pass 4:

(2 3 5 6 7) —————-> (2 3 5 6 7), in order

Note : Here you can note that if we have n elements , We have (n-1) passes. And comparisons are keep on decreasing in each pass. Comparisons in Pass 1 (n-1), in Pass 2 (n-2), in Pass 3 (n-3) and in Pass 4 (n-4).

Implementing Bubble Sort

Pseudocode Implementation

A : list of unordered elements
n = length(A)

for i = 1 to n-1 //for no. of passes
   /*inner loop*/
   Repeat below steps for j = 1 till j is less than or equal to n-i
      /*swap if elements not in order*/
      if A[j] > A[j+1] then swap (A[j] , A[j+1])
 end j loop
end i loop