BUBBLE SORT

• A bubble sort compares adjacent array elements and exchange their value if they are out of order.
• It focuses on bringing the largest element to the end of the list with each successive pass.

EXAMPLE
  We take an unsorted array for our example. 
                         
      First pass,

         Second pass,

        Third pass,

        Fourth pass,

• Four passes were required to sort a list of 5 elements hence,we can says that bubble sort requires n-1 passes to sort an array of 'n' elements.
• Unlike selection sort it does not perform a search to identify the largest element,instead it repeatedly compares two consecutive elements & moves the largest amongst them to right.
• This process is repeated for all pairs of elements until the current iteration moves the largest elements element to the end of the list.

Efficiency of bubble sort: 

      Assume that an array containing n elements is sorted using bubble sort technique.

  No.of comparisons made in 1st pass=n-1

  No.of comparisons made in 2nd pass=n-2

  No.of comparisons made in last pass=1

Total no.of comparisons made

                           =(n-1)+(n-2)+....+1

                           =n*(n-1)/2

Efficiency of bubble sort=O(n^2)

Advantages:

• It is easy to understand and implement.
• It leverage the presence of any existing sort pattern in the list, thus resulting in better efficiency.

Disadvantages:

• The efficiency of O(n^2) is not well suited for large sized lists.
• It requires large number of elements to be shifted.
• It is slow in execution as large elements are moved elements towards the end of the list in a step_by_step fashion.

                                             *******