267 Write an algorithm for bubble sort. What is the asymptotic time complexity of bubble
sort in the worst case. 

Ans:
Algorithm for bubble sort:
Let 'A' be a linear array of elements and temp be the variable for
interchanging the position of the elements.
1. Input 'n' elements of an array 'a'.
2. initialize i=0
3. repeat trough step 6 while (i<n)
4. set j=0
5. repeat through step 6 while (j<n-i-l)
6. if (a[j]>a|j+l])
(i) temp=a[j]
(ii) a[j]=a[j+l]
(iii) a[j+l]=temp
7. display the sorted
elements of array 'a'
8. Exit.
In this sorting technique, each element is compared with its adjacent element. If the first
element is larger than the second one then the position of the elements are interchanged,
otherwise it is not changed. Then next element are compared with its adjacent element and
the same process is repeated for all the elements in the array. During the first pass the same
process is repeated leaving the last element. During the second pass the second last element
occupies the second last position. The same process is repeated until no more elements are
left for the comparison. Finally the array is sorted. One may use a Hag to check whether
there is any interchange in a particular pass. If there is no interchange in a pass, the array has
already got sorted, and the algorithm can terminate.
Time complexity in worst case: in worst case, the array will be in reverse sorted order and
the no. of comparisons are calculated as given below
F(n) = l+2+3+4+——— + (n-l)
= n (n-l)/2=O (n2)