Bubble Sort in Python

There are many sorting algorithms, often with several variations, but the bubble sort is probably the best known. It's simple to understand and the process can be illustrated with some cute animations and even Hungarian folk dancing!

Despite all that the bubble sort cannot claim to be the most efficient, and is often derided. However, it is still taught and sometimes crops up in coding tests or interview questions so for that reason I'll put together a simple implementation in Python. For the full lowdown take a look at the Wikipedia article.

Bubble Sort on Wikipedia

And then take a look at the Hungarian folk dancers.

Bubble-sort with Hungarian folk dance

Hopefully Wikipedia and Youtube were enlightening enough so let's get coding.

Swapping Integers Using Exclusive Or

Bubble Sort relies on being able to swap two values, and the most obvious way of doing this is by using a temporary variable, for example

Swapping Two Values with a Temp Variable

a = 45
b = 99

temp = a # temp = 45
a = b    # a = 99
b = temp # b = 45

However, if we are swapping integers we can use a trick with XOR, the Python symbol for which is ^. The following code and comments show how this works. Pay particular attention to the binary values in the comments.

Swapping Two Integers with Exclusive Or

a = 45     # 00101101
b = 99     # 01100011

a = a ^ b  # 01001110
b = a ^ b  # 00101101
a = a ^ b  # 01100011

I think this is a neat and clever bit of code so I'll be using it in this project.

Implementing Bubble Sort in Python

Create a new folder and within it create the following empty files:

  • bubblesort.py
  • main.py

You can download the files as a zip from the Downloads page, or clone or download the Github repo if you prefer.

Source Code Links

ZIP File
GitHub

bubblesort.py

def bubblesort(data):

    """
    Takes a list of numbers and runs the bubblesort
    algorithm on them, printing each stage to show progress.
    """

    print("Unsorted...")

    print_data(data, len(data))

    print("Bubble sorting...")

    lastindex = len(data) - 1

    while lastindex > 0:

        for i in range(0, lastindex):

             if data[i] > data[i+1]:

                data[i] = data[i] ^ data[i+1]
                data[i+1] = data[i] ^ data[i+1]
                data[i] = data[i] ^ data[i+1]

        print_data(data, lastindex)

        lastindex-= 1

    print("Sorted!")


def print_data(data, sortedto):

    """
    Prints data on a single line.
    Takes a sortedto argument, printing the sortedto
    portion in green and the unsorted portion in red.
    """

    for i in range(0, len(data)):

        if i >= sortedto:
            print("\x1B[32m{:3d}\x1B[0m".format(data[i]), end="")
        else:
            print("\x1B[31m{:3d}\x1B[0m".format(data[i]), end="")

    print("")

The bubblesort function takes a list to sort and starts off by printing the list as it is. When sorting we only need to go up to the last but one unsorted item, which is compared to the last unsorted item and swapped if necessary. The index of this item is stored in the lastindex variable.

We now enter a while loop. At the end of this loop lastindex is decremented, and the loop's condition is that we have not yet got down to 0.

For each iteration of the outer while loop we for-loop through the unsorted data, swapping any items which are out of order using the xor trick described above. For each iteration of the while loop we call the print_data function to show the state of the list at that point in time, including the colour coding.

The other function in this file is print_data. As well as the list to print it takes a sortedto argument to enable the sorted part of the data to be printed in green and the unsorted part in red. The colours are set using ANSI codes which I'll cover in a later post, but for now just note that this function uses the following three codes.

  • \x1B[32m - green
  • \x1B[31m - red
  • \x1B[0m - reset to default

We now need a main function to call the bubblesort function, which I have included in main.py.

main.py

import bubblesort
import random


def main():

    """
    Create a list of random numbers and pass them to the bubblesort function.
    """

    print("-----------------")
    print("| codedrome.com |")
    print("| Bubble Sort   |")
    print("-----------------\n")

    data = []

    for i in range(0, 16):
        data.append(random.randint(1, 99))

    bubblesort.bubblesort(data)


main()

This function simply creates a list and populates it with random numbers, before passing it as an argument to bubblesort. After the function definition the main function is called.

That's the source code finished so we can run it by typing the following in the terminal:

Running the Program

python3.7 main.py

This is the output from the program. Each row represents the data after one iteration, with unsorted data shown in red and sorted data shown in green. You can easily see that after each pass one more item has bubbled up to the top.

Program Output

-----------------
| codedrome.com |
| Bubble Sort   |
-----------------  

Unsorted...
 78 25 32 58 44  8 55  9 49  6 92 61 12 64 42 86
Bubble sorting...
 25 32 58 44  8 55  9 49  6 78 61 12 64 42 86 92
 25 32 44  8 55  9 49  6 58 61 12 64 42 78 86 92
 25 32  8 44  9 49  6 55 58 12 61 42 64 78 86 92
 25  8 32  9 44  6 49 55 12 58 42 61 64 78 86 92
  8 25  9 32  6 44 49 12 55 42 58 61 64 78 86 92
  8  9 25  6 32 44 12 49 42 55 58 61 64 78 86 92
  8  9  6 25 32 12 44 42 49 55 58 61 64 78 86 92
  8  6  9 25 12 32 42 44 49 55 58 61 64 78 86 92
  6  8  9 12 25 32 42 44 49 55 58 61 64 78 86 92
  6  8  9 12 25 32 42 44 49 55 58 61 64 78 86 92
  6  8  9 12 25 32 42 44 49 55 58 61 64 78 86 92
  6  8  9 12 25 32 42 44 49 55 58 61 64 78 86 92
  6  8  9 12 25 32 42 44 49 55 58 61 64 78 86 92
  6  8  9 12 25 32 42 44 49 55 58 61 64 78 86 92
  6  8  9 12 25 32 42 44 49 55 58 61 64 78 86 92
Sorted!

As I mentioned earlier bubble sort is rather inefficient, and this project is intended only as a demonstration and programming exercise. You might find the xor swap and terminal colours more useful than the algorithm itself!