Fun With Python #5: Bubble Sort Visualization

Welcome to “Fun with Python”, part 5. In this part, we will utilize the pygame module to visualize bubble sort and get more insights about how it works.

Theory and Foundations

Every CS student or developer has spent time studying sorting techniques and algorithms and the first and simplest sorting algorithm that gets presented is bubble sort.

Bubble sort is a sorting algorithm that compares adjacent numbers and swaps them if needed. This continues until all the elements are sorted. An example will make things clearer:

We start of with this sequence of numbers and we want to sort them resulting in an ascending sequence:

5, 3, 2, 6, 1, 4

First we compare 5 with 3, with 5 being bigger than 3 so we swap:

3, 5, 2, 6, 1, 4

Next we compare 5 with 2. Again 5 is greater that 2 so we swap:

3, 2, 5, 6, 1, 4

Our next comparison is between 5 and 6. This time, 6 is greater than 5 so we do not swap the two numbers. So we move on and compare 6 with the next number which is 1 and the result is a swap:

3, 2, 5, 1, 6, 4

Finally we compare 6 with 4 and we swap resulting to this sequence:

3, 2, 5, 1, 4, 6

As you can see, the greatest number is now on the last position. If we do this process again, we will swap numbers and 5 will be put to the correct position. If we continue doing this process, we will have the sequence sorted.

From what you have seen, you might already have guessed that performance wise, this is not an optimal algorithm. In fact, its complexity is O(n²) where n is the number of elements that need to be sorted. This makes the algorithm not suitable for practical use cases, where other, more efficient algorithms are being used.

By intuition, one can see that the greatest numbers are put to the end of the sequence in every iteration. Let’s confirm it by visualizing the algorithm. Here, the pygame module will be of great assistance.

According to pygame official page:

Pygame is a set of Python modules designed for writing video games. Pygame adds functionality on top of the excellent SDL library. This allows you to create fully featured games and multimedia programs in the python language.

In other words, pygame is a module used in Python, in order to create video games, but we are going to use some basic features. Let’s get started.

Implementation

The first thing we are going to do is create an empty window. We will define the width and the height. We will also give out window a name:

import random
import pygame
win_width = 700
win_height = 400
values = [int(random.random()*win_height) for _ in range(win_width)]

pygame.init()
win = pygame.display.set_mode((win_width, win_height))
pygame.display.set_caption('Bubble Sort Visualization')

Also, we will create a list of random numbers. We want to create a number for every pixel in the window and we will normalize the values random.random() returns so that the whole height of the window gets filled.

Let’s draw our values in the empty window we have:

run = True

while run:
    pygame.time.delay(100)

    for i in range(0, win_width):
        pygame.draw.line(win, (255, 255, 255), (i, win_height),
                         (i, values[i]))

    pygame.display.update()

    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            run = False

We create an endless loop, in which for every value in the list, we draw a line, starting from the bottom of the window. The height of each line represents the value of the number being drawn. Also, we check if the user decides to close the window, so that we can exit our program. This is the result we get:

Initial list

Next, we will implement bubble sort. Implementation is quite simple:

for i in range(0, len(values) - 1):
    for j in range(0, len(values) - i - 1):
        if (values[j] < values[j + 1]):
            tmp = values[j]
            values[j] = values[j + 1]
            values[j + 1] = tmp

Finally, we will insert this code in the loop we created above. After each iteration, we will update our window, with the updated list:

run = True
done = False

while run:
    pygame.time.delay(100)

    if (done == False):
        for i in range(0, len(values) - 1):
            for j in range(0, len(values) - i - 1):
                if (values[j] < values[j + 1]):
                    tmp = values[j]
                    values[j] = values[j + 1]
                    values[j + 1] = tmp

            win.fill((0, 0, 0))
            for i in range(0, win_width):
                pygame.draw.line(
                    win, (255, 255, 255),
                    (i, win_height),
                    (i, values[i])
                )

            pygame.display.update()

        done = True

    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            run = False

Conclusion

After the first iterations, you will see the following window:

Greatest numbers are moved to the right of the window

As you can see, the greatest numbers start moving to the right of the window. This is exactly how bubble sort works. In every pass, you are trying to bring the greatest number to its correct position (or the minimum if you are sorting ascending). When the sorting finishes, the window will look like this:

Sorted list

Every number is in the correct position and we get this “hill”.

Now, you have a visual overview of how bubble sort works. Of course you can implement other sorting algorithms and see how they work and understand them better by visualizing them. You can find the full functional code here.

I hope you enjoyed reading it and try it yourself. Let me know your thoughts and your ideas about it! In the meanwhile, you can find the rest of the “Fun with Python” series here.