Bubble Sorting Python Program

What is bubble sort ?

  • Bubble sort is repeatedly comparing pairs of adjacent elements and then swapping their positions if they exist in the wrong order.
  • Bubble sorting can be used for collections of numbers, strings, characters etc.
  • The basic idea behind bubble sort is to imagine that the records to be sorted are kept in an array held vertically. The records with lower key values are 'light' and bubble up to the top. We make repeated iteration over the array from bottom to top.
Example, consider sorted collection of elements
bubble sort step1
bubble sort step2

Bubble Sort Time Complexity

Time complexity of bubble sort is O(n^2) in both worst and average cases, here complete array is iterated for each elements.

Bubble Sort Python Program

def bubble_sort(list_vals):                                                     
    temp = 0;                                                                   
    n = len(list_vals);                                                         
    for k in range(0,  n-1):                                                    
        # (n-k-1) to ignore the comparisons of elements                         
        # which have already been compared in earlier iterations                
        for i in range(0, n-k-1):                                               
            if (list_vals[i] > list_vals[i+1]):                                 
                # here swapping of positions.                                   
                temp = list_vals[i];                                            
                list_vals[i] = list_vals[i+1];                                  
                list_vals[i+1] = temp;                                          
    return list_vals;                                                           
if __name__ == "__main__":                                                      
    list_vals = [30, 10, 20, 70, 60, 80, 50, 40];                               
    print("Collection before sorting: %s" % str(list_vals));                    
    print("Sorting list elements: %s" % str(bubble_sort(list_vals)));   
$ python bubble_sort.py 
Collection before sorting: [30, 10, 20, 70, 60, 80, 50, 40]
Sorting list elements: [10, 20, 30, 40, 50, 60, 70, 80]

Privacy Policy  |  Copyrightcopyright symbol2020 - All Rights Reserved.  |  Contact us   |  Report website issues in Github   |  Facebook page   |  Google+ page

Email Facebook Google LinkedIn Twitter