Bubble Sort in Python

A Bubble sort is an easy algorithm among the various sorting algorithms. We learn it as a first sorting algorithm. It is easy to learn and highly intuitive. It can be easy to implement into the code, which is much beneficial for beginner software developers. But it is the worst algorithm for sorting the elements in every except because it checks every time the array is sorted or not.

Let’s understand the concepts of the bubble sort.

Concept of Bubble Sort

The bubble sort uses a straightforward logic that works by repeating swapping the adjacent elements if they are not in the right order. It compares one pair at a time and swaps if the first element is greater than the second element; otherwise, move further to the next pair of elements for comparison.

Let’s understand it by an example –

Example –

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

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

Here the algorithm sort the elements –

First iteration

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

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

In second comparison, 5 < 8 then swapping happen –

[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 iteration is complete and we get the largest element at the end. Now we need to the len(list1) – 1

Second Iteration

Third Iteration

It will iterate until the list is sorted.

Fourth Iteration –

Fifth Iteration

Check the each element and as we can see that our list is sorted using the bubble sort technique.

Implementation in Python Code

We have already described the technique of bubble sort. Now, we will implement the logic in the Python code.

Program

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 defined a bubble_sort() function 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 elements without using the temp variable. Python has a very unique syntax. We can use the following lines of code.

Example –

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 using the two techniques. The swaps are not done; it means list is sorted. In the previous technique – The previous technique will evaluate the complete list though it doesn’t seem necessary to do.

We can prevent the unnecessary evaluation using the Boolean flag and checks if any swaps were made in the previous section.

Example –

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 iteration is ended when the largest element of the list end up at the end of the list.

The first time, we pass the largest element at the end position using the n position. The second time, we pass through the n-1 position, the second largest element.

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

Example –

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 comparison between the above code snippets.

All techniques are useful for the fewer elements, but if the list consists of many elements, then the second optimize technique make a huge difference.