Learn Python – Bubble Sort in Python- Basic and advance

A Bubble type is an easy algorithm amongst the quite a number sorting algorithms. We study it as a first sorting algorithm. It is handy to examine and pretty intuitive. It can be effortless to put into effect into the code, which is a whole lot really useful for novice software program developers. But it is the worst algorithm for sorting the elements in each and every besides because it exams every time the array is sorted or not.

Let’s understand the concepts of the bubble sort.

Concept of Bubble Sort

The bubble type uses a easy good judgment that works by means of repeating swapping the adjoining elements if they are now not in the right order. It compares one pair at a time and swaps if the first aspect is greater than the 2nd element; otherwise, move similarly to the subsequent pair of elements for comparison.

Let’s understand it by an example –

Example –

We are creating a listing of element, which stores the integer numbers

list1 = [5, 3, 8, 6, 7, 2]

Here the algorithm sort the elements –

First iteration

[5, 3, 8, 6, 7, 2]

It compares the first two factors and here 5>3 then swap with each other. Now we get new listing is –

[3, 5, 8, 6, 7, 2]

In 2nd comparison, 5 < 8 then swapping show up –

[3, 5, 8, 6, 7, 2]

In third comparison, 8>6 then swap –

[3, 5, 6, 8, 7, 2]

In fourth comparison, 8>7 then swap –

[3, 5, 6, 7, 8, 2]

In fifth comparison, 8>2 then swap-

[3, 5, 6, 7, 2, 8]

Here the first new release is whole and we get the largest thing at the end. Now we need to the len(list1) – 1

Second Iteration

[3, 5, 6, 7, 2, 8] – > [3, 5, 6, 7, 2, 8] here, 3<5 then no swap taken place [3, 5, 6, 7, 2, 8] – > [3, 5, 6, 7, 2, 8] here, 5<6 then no swap taken place [3, 5, 6, 7, 2, 8] – > [3, 5, 6, 7, 2, 8] here, 6<7 then no swap taken place [3, 5, 6, 7, 2, 8] – > [3, 5, 6, 2, 7, 8] right here 7>2 then swap their position. Now [3, 5, 6, 2, 7, 8] – > [3, 5, 6, 2, 7, 8] right here 7<8 then no swap taken place.

Third Iteration

[3, 5, 6, 2, 7, 8] – > [3, 5, 6, 7, 2, 8] here, 3<5 then no swap taken place [3, 5, 6, 2, 7, 8] – > [3, 5, 6, 7, 2, 8] here, 5<6 then no swap taken place [3, 5, 6, 2, 7, 8] – > [3, 5, 2, 6, 7, 8] here, 6<2 then swap their positions [3, 5, 2, 6, 7, 8] – > [3, 5, 2, 6, 7, 8] right here 6<7 then no swap taken place. Now [3, 5, 2, 6, 7, 8] – > [3, 5, 2, 6, 7, 8] right here 7<8 then swap their position.

It will iterate until the list is sorted.

Fourth Iteration –

[3, 5, 2, 6, 7, 8] – > [3, 5, 2, 6, 7, 8] [3, 5, 2, 6, 7, 8] – > [3, 2, 5, 6, 7, 8] [3, 2, 5, 6, 7, 8] – > [3, 2, 5, 6, 7, 8] [3, 2, 5, 6, 7, 8] – > [3, 2, 5, 6, 7, 8] [3, 2, 5, 6, 7, 8] – > [3, 2, 5, 6, 7, 8]

Fifth Iteration

[3, 2, 5, 6, 7, 8] – > [2, 3, 5, 6, 7, 8]

Check the each component and as we can see that our list is sorted the use of the bubble sort technique.

Implementation in Python Code

We have already described the method of bubble sort. Now, we will put into effect the good judgment in the Python code.

Program

# Creating a bubble sort function  
def bubble_sort(list1):  
    # Outer loop for traverse the entire list  
    for i in range(0,len(list1)-1):  
        for j in range(len(list1)-1):  
            if(list1[j]>list1[j+1]):  
                temp = list1[j]  
                list1[j] = list1[j+1]  
                list1[j+1] = temp  
    return list1  
  
list1 = [5, 3, 8, 6, 7, 2]  
print("The unsorted list is: ", list1)  
# Calling the bubble sort function  
print("The sorted list is: ", bubble_sort(list1))  

Output:

The unsorted list is:  [5, 3, 8, 6, 7, 2]
The sorted list is:  [2, 3, 5, 6, 7, 8]

Explanation:

In the above code, we have described a bubble_sort() feature which takes list1 as an argument.

Inside the function, we have defined two for loop – first for loop iterates the complete list and the second for loop iterates the list and the compare the two elements in every outer loop iterations.

The for loop will be terminated when it reaches at the end.

We have defined the condition in the inner for loop; if a first index value is greater than the second index value, swap their positions with each other.

We called the function and passed a list; it iterated and returned the sorted list.

Without using a temp variable

We can also swap the factors barring the usage of the temp variable. Python has a very unique syntax. We can use the following lines of code.

Example –

def bubble_sort(list1):  
    # Outer loop for traverse the entire list  
    for i in range(0,len(list1)-1):  
        for j in range(len(list1)-1):  
            if(list1[j]>list1[j+1]):   
                # here we are not using temp variable  
                list1[j],list1[j+1] = list1[j+1], list1[j]  
    return list1  
  
list1 = [5, 3, 8, 6, 7, 2]  
print("The unsorted list is: ", list1)  
# Calling the bubble sort function  
print("The sorted list is: ", bubble_sort(list1))  

Output:

The unsorted list is:  [5, 3, 8, 6, 7, 2]
The sorted list is:  [2, 3, 5, 6, 7, 8]

Optimization of Python Code Implementation

We can optimize the above code the usage of the two techniques. The swaps are no longer done; it skill list is sorted. In the preceding method – The previous approach will evaluate the whole list though it doesn’t seem essential to do.

We can prevent the unnecessary comparison the use of the Boolean flag and assessments if any swaps were made in the previous section.

Example –

def bubble_sort(list1):  
   # We can stop the iteration once the swap has done  
    has_swapped = True  
  
    while(has_swapped):  
        has_swapped = False  
        for i in range(len(list1) - 1):  
            if list1[i] > list1[i+1]:  
                # Swap  
                list1[i], list1[i+1] = list1[i+1], list1[i]  
                has_swapped = True  
    return list1  
  
  
list1 = [5, 3, 8, 6, 7, 2]  
print("The unsorted list is: ", list1)  
# Calling the bubble sort function  
print("The sorted list is: ", bubble_sort(list1))  

Output:

The unsorted list is:  [5, 3, 8, 6, 7, 2]
The sorted list is:  [2, 3, 5, 6, 7, 8]

In the second technique, we consider the fact that the generation is ended when the biggest thing of the list cease up at the cease of the list.

The first time, we pass the greatest thing at the stop function the usage of the n position. The 2d time, we omit via the n-1 position, the 2nd largest element.

In each consecutive iteration, we can evaluate at one much less aspect than before. More accurately, in the k-th iteration, solely need to evaluate at the first n – k + 1 elements:

Example –

def bubble_sort(list1):  
    has_swapped = True  
  
    total_iteration = 0  
  
    while(has_swapped):  
        has_swapped = False  
        for i in range(len(list1) - total_iteration - 1):  
            if list1[i] > list1[i+1]:  
                # Swap  
                list1[i], list1[i+1] = list1[i+1], list1[i]  
                has_swapped = True  
        total_iteration += 1  
    print("The number of iteraton: ",total_iteration)  
    return list1  
  
list1 = [5, 3, 8, 6, 7, 2]  
print("The unsorted list is: ", list1)  
# Calling the bubble sort funtion  
print("The sorted list is: ", bubble_sort(list1))  

Output:

The unsorted list is:  [5, 3, 8, 6, 7, 2]
The number of iteraton:  6
The sorted list is:  [2, 3, 5, 6, 7, 8]

Time Comparison

Let’s see the time assessment between the above code snippets.

Unoptimized Bubble Sort Takes: 0.0106407  
Optimize Bubble Sort Takes: 0.0078251  
Bubble Sort with a Boolean flag and shortened list Takes: 0.0075207   

All strategies are beneficial for the fewer elements, but if the list consists of many elements, then the second optimize approach make a massive difference.