How does bubble sort work? Why is it considered inefficient?
I need to sort [64, 34, 25, 12, 22, 11, 90] using bubble sort for my class 11 exam. Can you show me each pass and explain why it is O(n^2)?
1 Answer
Bubble sort repeatedly compares adjacent elements and swaps if in wrong order. Each pass bubbles the largest unsorted element to its correct position. Pass 1 on [64,34,25,12,22,11,90]: 64>34 swap: [34,64,25,12,22,11,90]. 64>25 swap: [34,25,64,12,22,11,90]. 64>12 swap: [34,25,12,64,22,11,90]. 64>22 swap: [34,25,12,22,64,11,90]. 64>11 swap: [34,25,12,22,11,64,90]. 64<90 no swap. After pass 1: [34,25,12,22,11,64,90] (90 is in place). Repeat for remaining n-1 elements. For n elements: n-1 passes, each with up to n-1 comparisons = O(n^2). Inefficient for large n — use merge sort or quicksort for real applications.
No comments yet — start the discussion.