Use app×
Join Bloom Tuition
One on One Online Tuition
JEE MAIN 2025 Foundation Course
NEET 2025 Foundation Course
CLASS 12 FOUNDATION COURSE
CLASS 10 FOUNDATION COURSE
CLASS 9 FOUNDATION COURSE
CLASS 8 FOUNDATION COURSE
+1 vote
2.9k views
in Computer by (69.7k points)

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

1 Answer

+2 votes
by (69.2k points)
selected by
 
Best answer

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 - 1)

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) = 1 +2+3+4+——— + (n-1) 

= n (n-1)/2=O (n2)

Welcome to Sarthaks eConnect: A unique platform where students can interact with teachers/experts/students to get solutions to their queries. Students (upto class 10+2) preparing for All Government Exams, CBSE Board Exam, ICSE Board Exam, State Board Exam, JEE (Mains+Advance) and NEET can ask questions from any subject and get quick answers by subject teachers/ experts/mentors/students.

Categories

...