Bubble Sort implementation in python 2.7. Worst case: when the list is sorted in reversed order total swaps == total loops == n+(n-1)+(n-2)+...+1 i.e. (n(n+1))/2 complexity : O(n^2) Best case: sorted list total swaps =0 complexity sigma(n)

bubble_sort.py

def bubble_sort(inp_lis):
    """Bubble Sort implementation in python 2.7.
         Worst case: when the list is sorted in reversed order
           total swaps == total loops == n+(n-1)+(n-2)+...+1  i.e. (n(n+1))/2
           complexity : O(n^2)

        Best case:  sorted list
          total swaps =0
          complexity sigma(n) 
    """   
    end=len(inp_lis)
    swap_count=0
    total_loops=0
    for i in xrange(1,end):
        local_swaps=0
        for j in xrange(end-i):                       #each time the loop size decrease by 1, initially loop size n-1
            if inp_lis[j] > inp_lis[j+1]:               #if current element is bigger than next
              inp_lis[j],inp_lis[j+1] = inp_lis[j+1],inp_lis[j]          #swap
              swap_count += 1                                        #increment swap_count
              local_swaps+=1
        
        total_loops += j+1
        #if in a particular loop no swaps were made then it is clear
        #that the lis is already sorted, so break
        if not local_swaps:
            break
        
    
    results="""
    total number of loops = {0} 
    total swaps = {1}
    sorted list : {2}
    """.format(total_loops,swap_count,inp_lis)
    return results
            

if __name__=="__main__":
    from random import shuffle
    lis=range(10)
    shuffle(lis)
    print lis
    print bubble_sort(lis)