• Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar
  • Skip to footer
Code Specialist

Code Specialist

Code and Programming Blog

  • Home
  • Clean Code
  • Code Principles
  • Code Interview
  • Python

Bubble Sort in Python and how to Visualize it

In this post about the bubble sort algorithm in Python, we want to look into how to implement and visualize it. Bubble sort isn't quite an efficient algorithm when it comes to time complexity. However, it is easy to code and to understand, so it is often an introductory problem for computer science students and pupils.

Home » Algorithms » Bubble Sort in Python and how to Visualize it

February 2, 2021 by Yannic Schröer 1 Comment

Contents hide
1 The Concept Behind Bubble Sort
2 Implementing the Algorithm
3 Time Complexity in Big-O-Notation
4 Optimizing Bubble Sort in Python
5 Visualizing Bubble Sort in Python
5.1 Our Book Recommendations on Python (Affiliate)

The Concept Behind Bubble Sort

To remind yourself what the concept behind bubble sort -not especially in Python- is, it might help look into its naming. Think of the analogy like that: you have some random air bubbles below the surface. The larger the bubble is, the higher its buoyancy speed is to rise to the top, and that’s it.

Air bubbles below the water surface

The idea behind the algorithm is to compare only two elements simultaneously and iterate over the whole list without going back. In the first step, you look at the first element in the list, in the second step at the second element, and in the last step, you look at the last element. You start at the beginning of the list and compare the first with the second item. If the first item is larger, you switch positions and go on.

Initial list: 	[4, 3, 2, 1]
First step: 	[4, 3, 2, 1] → 4 > 3? True → [3, 4, 2, 1]

In the next step, you would compare the second element (which is now the item that was the first one) with the third item and so on.

Second step: 	[3, 4, 2, 1] → 4 > 2 ? True → [3, 2, 4, 1]

The Algorithm has done its job if, in one run, no numbers have been switched.

...
Before last step: 	[2, 1, 3, 4] → [1, 2, 3, 4] → 1 change
last step: 		[1, 2, 3, 4]   0 changes → sorted

Implementing the Algorithm

An actual implementation of bubble sort in Python might look like this:

If you have problems understanding the 5th line

 unsorted_list[index], unsorted_list[index + 1] = unsorted_list[index + 1], unsorted_list[index]  # swap

That is called an in-place swap. That’s possible in Python because the interpreter evaluates expression strictly from left to right. In the case of an assignment, the interpreter will first read the assigning values and then assign them. For example:

a = 5
b = 6
print(a, b)
a, b = b, a
print(a, b)

out1 >> 5, 6
out2 >> 6, 5

So the values a and b effectively swap positions as a gets assigned b and b gets assigned a, after they both have been read. You may read more on this in the Python docs.

Note that I used the concept of recursion (the function calls itself under given circumstances). Using recursion is not necessary here, and if the list is long enough, the system’s max recursion depth might terminate your program. You may get to know your systems max recursion depth by using:

import sys
sys.getrecursionlimit()

You might change this constant to 3000 for example:

import sys
sys.setrecursionlimit(3000)

However, I do not recommend doing so. Recursive functions are often way faster than loops, but their memory usage is often immensely. The max recursion limit is set with the reason to prevent infinite loops and extensive memory-usage. Thereby, a non-recursive version might look like this:

Time Complexity in Big-O-Notation

A common thing in computer science is evaluating algorithms’ time complexity for a certain problem to decide which algorithm fits the best. However, it’s important to know, that the Big-O Notation only makes statements about the growth in relation to the input-parameter, not the time it takes to compute. Take these two function for example:

f_1(x)=x^2\\f_2(x)=3x^2

Both functions are considered quadratic in growth in relation to their input, even though the second function will always return a larger value.

Theoretically, there’s also a memory complexity to be considered. Still, as most of the time, memory isn’t a problem today, computer scientists tend only to give the time complexity of algorithms. The usual procedure is to evaluate the best- and the worst-case scenario of the algorithm concerning a given input of length n.

Given this knowledge, let’s try to assume the best possible runtime for this algorithm. The best possible scenario would be the whole list is already sorted, then we would iterate once over the list of length n and return it, as we detected zero changes. The runtime in relation to n would be n-1, as we compare each element with the next until we are at the penultimate element comparing it with the last one.

You might wonder what happens to the operations performed each time the algorithm is called – let’s call that factor k – a rule for big-o-notation that then applies is that constant factors are ignored.

\mathcal{O}(k*(n-1)) =\mathcal{O}(kn-k)= \mathcal{O}(n)

Even though we have n calls with k operations, k is a constant factor and is thereby ignored.

BestCase_{bubblesort} = \mathcal{O}(n)

The worst-case scenario, in contrast, would be the list totally reverse-sorted. Then would call the algorithm n-1 times as we only shift one element each time we call the algorithm. This would effectively lead to:

n(n-1) = n^2-n

n²-n calls. Another rule for the big-o-notation is that only the term with the largest exponent is relevant. Thereby the worst-case scenario would be described as n².

WorstCase_{bubblesort}=\mathcal{O}(n^2)

Optimizing Bubble Sort in Python

Suppose you read closely and know about bubble sort, you probably found the implementation in Python not to be optimal. That’s because I wanted to keep it simple to understand. In the following section, I want to describe how we can optimize the algorithm drastically with a slight modification. If you don’t want to optimize the algorithm or think that math is extraordinarily boring, I urge you to skip this section.

If you think about the algorithm extensively you might notice that in the first iteration over the whole list, the last element will be the largest. In the second iteration over the list, the second-last item will be the second-largest, and so on.

Using this knowledge we can cut the list in length by the last item each time we iterate over the list as it is already sorted. If we formularize this regarding the worst case, we get to the following formula:

(n-1)+(n-2)...+(n-(n-2)) + (n-(n-1))
(n-1)+(n-2)...+2 + 1 

In the first iteration, we have n-1 steps, then n-2, and so on, until we have only one element left or no changes. So, for example if we have 8 elements, the worst case will be

7+6+5+4+3+2+1 = 28

28 steps. So the maximum number of steps is exactly the sum of all numbers from 1 to n-1. Something that comes into play now is the Gaussian sum.

sum([0, n])=\frac{n(n+1)}{2}

Since we only need the sum of numbers from 0 to n-1, we have to modify the formula slightly

\frac{(n-1)((n-1)+1)}{2} =\frac{(n-1)(n)}{2} =\frac{n(n-1)}{2} 

This, in turn can be rewritten to

\frac{n(n-1)}{2} =\frac{n^2-n}{2}= \frac{1}{2}(n^2-n)

As ½ is again a constant factor, the time complexity again would be considered:

\mathcal{O}(n^2)

This is confusing as the runtime surely will be better. You have to remind yourself that the Big O Notation only makes statements about the growth, not the computation time. The optimized (recursive) code could look like this:

In row 8 you see, that instead of passing the whole list, we pass only the list minus the last element to the function call and append the last element. To prove to you that the optimized version is still considerably faster, I plotted the average runtimes (100 runs) of bubble sort and the optimized version with increasing list sizes from 10 to 1000:

Bubble Sort Runtime Plot, 100 runs with increasing list sizes from 10 to 1000 elements

Visualizing Bubble Sort in Python

The following animation (gif) was created using only Python and matplotlib (pyplot):

Bubble Sort Visualization Gif
Bubble Sort Algorithm Visualization

To reproduce this with any kind of sorting algorithm, you could use a variation of my code:

To briefly describe the code: The idea behind the visualization was to interpret each number in a given list as a bar of a bar chart. All that was left to do was take a picture of the current number order after each change. Then merge all the pictures to create an animated algorithm’s illusion. I tried to follow all the clean code rules regarding the animation code, but don’t hesitate to comment on anything unclear. Code isn’t always as self-explanatory as one might think…

Happy coding!

Download Source Files

Click to rate this post
[Total: 4 Average: 5]
Yannic Schröer

I am a developer and entrepreneur from Germany. I chose studying computer science because I love building things. I am of the opinion that there isn’t one truth (especially for computer science concepts) and whoever claims so isn’t that trustworthy in my eyes. I constantly try to improve things and myself. In my spare time I support businesses by offering them most of my services for free. Beside that I am kind of addict to e-learning courses.

Our Book Recommendations on Python (Affiliate)

Category iconAlgorithms,  Python,  Technical Background Tag iconCode Interview Question

Related Posts

Reverse words in a string
4.8 (4)
January 31, 2021
Decorators in Python
5 (1)
February 23, 2021
New Syntax Features in Python 3.9
5 (3)
February 12, 2021

Reader Interactions

Comments

  1. Nina says

    February 9, 2021 at 7:56 pm

    I bailed on the math stuff but found the rest very interesting

    Reply

Leave a Reply Cancel reply

Your email address will not be published.

Primary Sidebar

Search

Categories

  • Algorithms
  • Code Interview
  • Code Principles
  • Environment
  • Errors
  • Learn to Code
  • Object Orientation
  • Python
  • Technical Background
  • Write Better Code

Tags

Alternative (1) Announcement (1) Clean Code (6) Code (1) Code Interview Question (2) Code Philosophy (1) Comments (1) Computer Graphics (2) Concurrency (1) Control Characters (1) Data Structures (1) decorators (2) dictionaries (3) Easter Eggs (1) funny (1) Github Actions (1) Marching Cubes (1) Meshing (1) Nice to know (1) Parallelisation (1) Pythonic (3) PyYAML (1) Readability (4) Simple is good (2) Software Engineering (2) switch (1) Syntax (1) Tricks (1) type hints (1) Ubuntu 20.04 (1) Underscores (1) Unix (1) Video (1) Virtualization with Windows (1)

Footer

Recent Posts

  • Decorators in Python
  • New Syntax Features in Python 3.9
  • 5 Ways to Speed Up Python Code
  • Bubble Sort in Python and how to Visualize it
  • Reverse words in a string

Tags

Alternative Announcement Clean Code Code Code Interview Question Code Philosophy Comments Computer Graphics Concurrency Control Characters Data Structures decorators dictionaries Easter Eggs funny Github Actions Marching Cubes Meshing Nice to know Parallelisation Pythonic PyYAML Readability Simple is good Software Engineering switch Syntax Tricks type hints Ubuntu 20.04 Underscores Unix Video Virtualization with Windows

Categories

  • Algorithms
  • Code Interview
  • Code Principles
  • Environment
  • Errors
  • Learn to Code
  • Object Orientation
  • Python
  • Technical Background
  • Write Better Code

Recent Comments

  • Nina on Bubble Sort in Python and how to Visualize it
  • Bhan on Concurrency in Python

Follow Us

  • Facebook
  • Instagram
  • Pinterest
  • Twitter

Quicklinks

  • About us
  • Become a writer

Privacy Policy | Legal Notice | Contact

 

All rights reserved © 2020-2021 code-specialist.com