Algorithm for bubble sort:
Let 'A' be a linear array of elements and temp be the variable for interchanging the position of the elements.
Input 'n' elements of an array 'a'.
initialize i=0
repeat trough step 6 while (i<n)
set j=0
repeat through step 6 while (j<n - i - 1)
if (a[j]>a|j+l])
(i) temp=a[j]
(ii) a[j]=a[j+l]
(iii) a[j+l]=temp
- display the sorted
elements of array 'a'
- 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) = 1 +2+3+4+——— + (n-1)
= n (n-1)/2=O (n2)
