How to Implement Bubble Sort In Python - KodeSrc

Bubble Sort In Python

We already have a post on in depth of bubble sort with code in java and comparison of different levels of bubble sort

In this post we will see how Bubble sort is implemented in python

We will use Bubble Sort of 3 level

In Bubble sort after every iteration
the largest number is positioned at its appropriate end position.


Algorithm:

• We run two loops the outer loop will be for iterating on the array and the inner loop will perform the comparison and swapping part.

• If the next element is smaller than the current element than we swap it with current element.

1. Level 1

def bubbleSortLevel1(arr):
    iterations=0
    for i in range(0,len(arr)):
        for j in range(0,len(arr)-1):
            if arr[j]>arr[j+1]:
                arr[j],arr[j+1]=arr[j+1],arr[j]
            iterations+=1

        print("i=",i," " ,arr)

    return iterations

Output:






You Can see here that the total iterations made are 72





2 Level 2:


In this level we add outer loop iterator in the condition of for loop , because you can see that after every iterations the highest number is positioned to its appropriate end position, thus to avoid extra comparisons we reduce the number of iterations of inner loop.

def bubbleSortLevel2(arr):
    iterations=0
    for i in range(0,len(arr)):
        for j in range(0,len(arr)-i-1):
            if arr[j]>arr[j+1]:
                arr[j],arr[j+1]=arr[j+1],arr[j]
                iterations=iterations+1
        print("i=", i, " ", arr)

    return iterations

Output:






Now as you can see that just be doing simple change the number of iterations are reduced to half in this case.


Now imagine if the search space is huge than their will be a drastic decrease in the time consumption



3 Level 3:

In this level we use a flag variable to avoid extra comparison if the array is already sorted .

def bubbleSortLevel3(arr):
    iterations=0
    for i in range(0,len(arr)):
        flag=True
        for j in range(0,len(arr)-i-1):
            if arr[j]>arr[j+1]:
                flag=False
                arr[j],arr[j+1]=arr[j+1],arr[j]
                iterations=iterations+1
        if flag:
            break

        print("i=", i, " ", arr)

    return iterations


Comparison of Above Three Levels:


lets say we have the list as
arr = [-98, -35, -15, 0, 2, 4, 6, 9, 19]


Now lets take a look how the different levels behave on this input list

We have used Sorted List to see how these techniques perform if the list is already sorted .

Ideally their should be no swapping , so lets check




1 Level 1:





Total Iterations performed in level 1 are 72



2 Level 2:






Total Iterations performed in level 2 are 36


3 Level 3:






Total Iterations performed in level 3 are 8

so we can see that even if the list is sorted the level 1 and level 2 perform unnecessary comparisons ,where as in level 3 the comparisons are reduced thus level 3 is more efficient as compared to others.



Conclusion:

Thus we can use any Sorting level for sorting if the search space that is the array in this case is small.But if the space is large enough then it is good to use level 2 or level 3 sorting technique