Bubble Sort also known as Exchange Sort, is a simple sorting algorithm. It works by repeatedly stepping throughout the list to be sorted, comparing two items at a time and swapping them if they are in the wrong order. The pass through the list is duplicated until no swaps are desired, which means the list is sorted.

This is the easiest method among all sorting algorithms.

BUBBLE SORT (A)
1. for i ← 1 to length [A]
2. for k ← length [A] down to i+1
3. if A[k] <A[k-1]
4. exchange (A[k], A [k-1])

Analysis:

1. Input: n elements are given.
2. Output: the number of comparisons required to make sorting.
3. Logic: If we have n elements in bubble sort, then n-1 passes are required to find a sorted array.

  In pass 1: n-1 comparisons are required
  In pass 2: n-2 comparisons are required
  In pass 3: n-3 comparisons are required
 ............................................................................
 ...............................................................................
  In pass n-1: 1 comparisons is required 
  Total comparisons: T (n) = (n-1) + (n-2) +...........+ 1
                           = 

= o (n

2)
   Therefore complexity is of order n2