Bubble sort

Bubble sort

1. what is iteration here

   • no of times outer for loop executes

2. time comp

   • worst case O(n^2)
   • best case O(n)
   • average case O(n^2)

3. algorithm

   • improved
     • if no of swaps in any iteration is 0, then stop as it is sorted
   • repeatedly swap two adjacent elements if they are in wrong order

4. we have to do n-1 iterations before we get sorted array

   • 1st iteration - n-1 steps, 2nd iteration - n-2 steps and so on. for i th iteration check up to n-i

5. iterative and recursive both approach

6. space complexity O(1)