Python| Searching and Sorting|Bubble Sort

Bubble Sort Example-

Consider the following array A-

 Now, we shall implement the above bubble sort algorithm on this array.

Step-01:

• We have pass=1 and i=0.
• We perform the comparison A[0] > A[1] and swaps if the 0th element is greater than the 1th element.
• Since 6 > 2, so we swap the two elements.

 

Step-02:

• We have pass=1 and i=1.
• We perform the comparison A[1] > A[2] and swaps if the 1th element is greater than the 2th element.
• Since 6 < 11, so no swapping is required.

Step-03:

• We have pass=1 and i=2.
• We perform the comparison A[2] > A[3] and swaps if the 2nd element is greater than the 3rd element.
• Since 11 > 7, so we swap the two elements.

Step-04:

• We have pass=1 and i=3.
• We perform the comparison A[3] > A[4] and swaps if the 3rd element is greater than the 4th element.
• Since 11 > 5, so we swap the two elements.

Finally after the first pass, we see that the largest element 11 reaches its correct position.

Step-05:

• Similarly after pass=2, element 7 reaches its correct position.
• The modified array after pass=2 is shown below-

Step-06:

• Similarly after pass=3, element 6 reaches its correct position.
• The modified array after pass=3 is shown below-

Step-07:

• No further improvement is done in pass=4.
• This is because at this point, elements 2 and 5 are already present at their correct positions.
• The loop terminates after pass=4.
• Finally, the array after pass=4 is shown below-

Optimization Of Bubble Sort Algorithm-

• If the array gets sorted after a few passes like one or two, then ideally the algorithm should terminate.
• But still the above algorithm executes the remaining passes which costs extra comparisons.

Visitor Counter

0056748