Bubble Sort in Python

By /
Bubble Sort In Python

Let’s study one of the most intuitive and easiest to learn sorting algorithms, and implement Bubble Sort in Python. We’ll start by understanding sorting itself, and then we’ll get to sorting via bubble sort, and finally, we’ll see how to implement it in Python.

Importance of Sorting Algorithms

What is sorting? And why is it so important? These are the questions that we will try to answer in this section.

From the books in a library and the words in a dictionary to the entries of a database and the instructions in a processor, we’ve experienced sorting numerous times.

“In computer science, sorting is the act of arranging things in an ordered sequence.” – Wikipedia

This means when we sort things, we need to know the criteria upon which we will arrange the sequence given to us. For the purposes of this tutorial, we shall assume the criteria is the value of a number, and we shall sort a given sequence of numbers.

In computer science, the most important purpose of sorting is to produce efficient algorithms. Binary Search is an exceptionally fast searching algorithm that will not be possible in an unsorted collection of objects.

Almost all set operations work very fast on sorted data.

Apart from making efficient algorithms, sorting is used when the very requirement of a program is to sort something, like a program that works with a deck of cards. Consequently, sorting algorithms are one of the most fundamental concepts a programmer must know.

Understanding Bubble Sort Algorithm

Think of how in a glass of soda, the bubbles inside rise up. The bubbles represent the greatest/smallest element in a given sequence, and the bubble’s rising movements represent how the greatest/smallest element moves to the end/beginning of the sequence.

This is how Bubble Sort works, and why it has the name.

To put it simply, we go through the sequence multiple times, and every time, we swap several pairs of elements in a manner that the greatest/smallest element in the sequence ends up at one of the ends of the sequence.

For the sake of this tutorial, we shall consider the given array, and we shall sort it in increasing order of the value of the numbers.

12, 16, 11, 10, 14, 13

Now, the algorithm of Bubble Sort works like this for sorting in increasing order:

  1. Consider two variables i and j. i represents the number of elements we have sorted or the number of times we have gone through the list because every time we go through the list we sort one item for certain.
    j represents a position in the list, so if we say that j is 3, then we are talking about the third number in the list, which is 11.
  2. Consider n as the number of elements in the list.
  3. Let i be equal to 0. Because we have not gone through the list and no elements are sorted.
  4. Let j be equal to 1. So we are starting with the number in the first position.
  5. If the number at position j is greater than the number at position j+1, then we need to swap the numbers at positions j and j+1. This is because the list is in increasing order, so the number that comes before cannot be greater than the number that comes after.
  6. Increase j by 1. So now, we can look at the next pair of numbers.
  7. If j is not n-i, go to step 5, otherwise, we stop the loop and go to the next step. In this loop, every time a swap occurs, the greater element moves toward the end of the list. This is the behavior of Bubble Sort, the greatest elements bubble towards the end of the list. If i represents the number of elements already sorted, then the last i elements of the list are in their correct position (because they bubbled their way through during the i number of times we went through the loop), so we don’t need to check the last i elements as it will only waste time, and hence the loop ends when j is equal to n-i.
  8. Increase i by 1. If we ended the loop when j reached the end, we have gone through the list one more time and one more element is sorted.
  9. If i is not n-1, then go to step 4, otherwise, we stop the loop with i and go to the next step. As you might have noticed, there are two loops, the inner one with j is responsible for sorting one more element, and we have a total of n elements to sort, which is handled by the outer loop that runs on i. If i becomes n-1, it means n-1 elements are sorted, which automatically means that the last element is also in its correct position, and that means the entire sequence is sorted, and so we stop.
  10. The sequence is sorted.

Now, you may want to try this on the given sequence, and that is what we’ll do now.

Bubble Sort Example

Given sequence: 12, 16, 11, 10, 14, 13
Number of elements (n): 6
Let’s start-

  • Step 1: Variables i and j representing sorted elements and position.
  • Step 2: n is 6. n = 6
  • Step 3: Set i as 0. i = 0
  • Step 4: Set j as 1. j = 1
  • Step 5: Comparing positions j and j+1, the element at position 1 (12) is not greater than the one at 2 (16).
  • Step 6: Increment j. j = 2
  • Step 7: j (2) is not n-i (6), so we go to step 5.
  • Step 5: Position 2 (16) is greater than position 3 (11), so we swap.
  • Sequence: 12, 11, 16, 10, 14, 13
  • Step 6: Increment j. j = 3
  • Step 7: 3 is not 6, so we go to step 5.
  • Step 5: 16 is greater than 10, so we swap. Sequence: 12, 11, 10, 16, 14, 13
  • Step 6: Increment j. j = 4
  • Step 7: 4 is not 6, so we go to step 5.
  • Step 5: 16 is greater than 14, so we swap. Sequence: 12, 11, 10, 14, 16, 13
  • Step 6: Increment j. j = 5
  • Step 7: 5 is not 6, so we go to step 5.
  • Step 5: 16 is greater than 13, so we swap. Sequence: 12, 11, 10, 14, 13, 16
  • Step 6: Increment j. j = 6
  • Step 7: j (6) is equal to n-i (6), so we move on to step 8. Notice that the greatest element (16) is at the end, and we have sorted one element for certain.
  • Step 8: Increase i. i = 1
  • Step 9: i (1) is not n-1 (5), so we repeat it all over from step 4, and the loop continues, the resulting changes in the sequence will look like this:

11, 12, 10, 14, 13, 16
11, 10, 12, 14, 13, 16
11, 10, 12, 14, 13, 16
11, 10, 12, 13, 14, 16
10, 11, 12, 13, 14, 16
10, 11, 12, 13, 14, 16
10, 11, 12, 13, 14, 16
10, 11, 12, 13, 14, 16
10, 11, 12, 13, 14, 16
10, 11, 12, 13, 14, 16
10, 11, 12, 13, 14, 16

After this, i becomes 5, which is n-1, so the loop ends and the algorithm tells us that the list is sorted. It also seems that the list may end up getting sorted before the algorithm finishes, which just means that the given sequence was somewhat sorted before it was given to the algorithm.

Implementing Bubble Sort in Python

Now that we have the algorithm ready, we can start to implement each step in Python. There are some things to note:

The sequence will be represented by a list, and lists have indexes instead of positions, and indexes go from 0 to size-1 instead of 1 to size, so that will need to be adjusted, and here’s how the algorithm will look:

def bubble_sort(sequence):
    n = len(sequence)
    for i in range(n-1):
        for j in range(n-i-1):
            if(sequence[j] > sequence[j+1]):
                sequence[j], sequence[j+1] = sequence[j+1], sequence[j]

Let us use an example and sort it using this algorithm:

Binary Sort Example
Binary Sort Example

Note that this algorithm sorts the list in place, but it is very simple to change the algorithm so that it returns a sorted list instead.

Conclusion

In this tutorial, we studied what sorting is and where it is used, then we learned how Bubble Sort works, we came up with an algorithm and implemented Bubble sort in Python.

Bubble Sort is one of many sorting algorithms and it is far from the best one but it is very easy to implement. The reason it is not used too often is that it has a complexity of O(n2), which means if the number of elements in the list is doubled, the time it takes to sort them using this algorithm will increase by four times.

So for a very large amount of data, this algorithm becomes inefficient. Nevertheless, knowing Bubble Sort as a programmer is important and I hope you learned something.