Bubble sort is a simple sorting technique that is the fastest of all the sorting techniques. In this project, we will be understanding the concept of bubble sort and we will create a visualizer using Python to see how the bubble sort actually works.
Bubble Sort Visualizer
Bubble Sort is a simple sorting algorithm that swaps the adjacent numbers in the array to sort the array. Let us take an example and understand the concept of Bubble Sort in detail.
Let us take an array – [1,6,8,3,2]. As we can see this is an unsorted array.
Sorting for the first time:
We will look at each adjacent element from the beginning, taking each input as a pair.
[1,6] – This is sorted so no changes need to be made.
[6,8] – This is sorted so no changes need to be made.
[8,3] – Now this is not sorted so let us swap this. New array after this step is [1,6,3,8,2]
[8,2] – Now this set is also not sorted so let us swap this too. New array after this step is [1,6,3,2,8]
Sorting for second time:
We will be repeating the process till we get a sorted array.
[1,6] – Already sorted
[6,3] – Swap this. Updated array [1,3,6,2,8]
[6,2] – Swap this to sort. Updated array [1,3,2,6,8]
[6,8] – Already sorted.
By the end of this, our array is [1,3,2,6,8]
Sorting for the third time:
[1,3] – Already sorted.
[3,2] – Swap this. Now we get the array [1,2,3,6,8]
Now that we have got the sorted array, we still have to do this till the last element.
[3,6] and [6,8] are already sorted.
So after sorting 3 times, we have our sorted array.
Now that the concept of Bubble Sort is clear, we will use this and make a visual representation of the Bubble Sort Algorithm.
Python Bubble Sort Visualizer project Details
In this project, we are going to use the Bubble Sort Algorithm and Visualize using Pygame. Here we are going to take a list as input from the user and will visualize what happens in a bubble sort algorithm.
This is an intermediate-level project and requires a basic understanding of the Pygame Module.
Project Prerequisites
While creating this project, we will require these three modules.
1. Pygame – We will be building the GUI of the project using Pygame. Command to install pygame is as –
pip install pygame
2. Math – Math Library is for doing some calculations during the creation of a project. The command to install it is –
pip install math
Download Bubble Sort Visualizer Python Project
Before proceeding with the project, please download the source code of the bubble sort visualizer project from the following link: Bubble Sort Visualizer Project Code
Steps to Create the Project
Follow these steps to proceed with the python bubble sort visualizer project:
- Import the required Libraries
- Creating a Game Window
- Function for setting the List
- Displaying the sorting window on the screen
- Bubble Sort Algorithm
- Display List
- Main Function
- Calling the Main Method
1. Import the Required Libraries:
#importing library import pygame import math
- We need to import these libraries to proceed with the project.
2. Creating a Game Window:
pygame.init()#creating a window
- init() – This method initializes the imported modules of this project.
def __init__(self, width, height, lst):
self.width = width
self.height = height
self.window = pygame.display.set_mode((width, height))#display the window
pygame.display.set_caption("Bubble Sort Visualization with TechVidvan")#setting title to the window
self.set_list(lst)
- We have created an init() function that will help us make our GUI window.
- Set_mode() – this method will help us set the window for display and specify the width and height of the window.
- set_caption() – this method sets the title of the screen.
- set_list() – this is for setting the list that we will be generating. We will be generating the set_list() function in the next step.
3. Function for Setting the List (set_list()):
def set_list(self, lst):# setting the min max for the array
self.lst = lst
self.mini = min(lst)#setting minimum value to mini
self.maxi = max(lst)#setting maximum value to maxi
self.block_width = round((self.width - self.SIDE_PAD) / len(lst))
self.block_height = math.floor((self.height - self.TOP_PAD) / (self.maxi - self.mini))
self.start_x = self.SIDE_PAD // 2
- Using the min() and max() methods, we are setting the minimum and maximum values to their variables.
- In this segment, we are creating blocks for each element in the array. According to the value of the element, we are creating the height, width and colour of the block.
- round() – This is for rounding off.
- floor() – Floor() is an inbuilt library of the math module which helps us round off the number to the down number.
4. Displaying the Sorting Window on the Screen:
def draw(draw_info, algo_name, ascending):
draw_info.window.fill(draw_info.BACKGROUND_COLOR)#filling background colour to the window
controls = draw_info.FONT.render("Press SPACE to tart Sorting", 1, draw_info.BLACK)#setting that when space is clicked sorting happens
draw_info.window.blit(controls, (draw_info.width/2 - controls.get_width()/2 , 45))
#function to update the array for sorting
draw_list(draw_info)
pygame.display.update()#updating the window
- We have created a draw function to display the sorting window on the screen.
- Font.render() – Specifies the font and colour of the window and saves it in a variable called controls.
- blit() – This method takes the controls variable and specifies the x and y coordinates that need to be displayed on the screen.
- update() – This method will update what’s happening on the screen.
5. Bubble Sort Algorithm:
def bubble_sort(draw_info, ascending=True):# algo for bubble sort
lst = draw_info.lst
for i in range(len(lst) - 1):
for j in range(len(lst) - 1 - i):
n1 = lst[j]
n2 = lst[j + 1]
if (n1 > n2 and ascending) or (n1 < n2 and not ascending):
lst[j], lst[j + 1] = lst[j + 1], lst[j]
draw_list(draw_info, {j: draw_info.ORANGE, j + 1: draw_info.PINK}, True)
yield True
return lst
#making a new array to display
array1 = [str(i) for i in lst]
array1=",".join(array1)
- As we have seen what bubble sort is, we are creating the bubble sort algorithm using the loops concept in python. Using the draw_info, we are drawing the blocks on the screen.
- We sort the adjacent elements and display the updated blocks one by one. While the blocks are moving we want them to be orange and pink. We set ascending = True so that the sorting is always in the ascending order.
- We create an array (array1) and copy each item of the list into that array using the join method.
6. Show the List :
def show(draw_info):
lst = draw_info.lst
draw_info.window.fill(draw_info.BACKGROUND_COLOR)
block = draw_info.FONT.render(str(lst), True, (0,0,0))
#Display the array
draw_info.window.blit(block, (0,20))
- Draw_info.lst – We will take in the list entered.
- fill() – This will fill in the background colour.
- We have created a block which will display the list in sorted and unsorted manner.
- window.blit() – This function displays the block on the main screen
7. Main Function:
def main():#main method
run = True
clock = pygame.time.Clock()
lst=[]
n = int(input("Enter number of elements : "))
# iterating till the range
for i in range(0, n):
ele=int(input())
lst.append(ele)
draw_info = drawinfo(800, 600, lst)
sorting = False
ascending = True
sorting_algorithm = bubble_sort
sorting_algo_name = "Bubble Sort"
sorting_algorithm_generator = None
while run:
clock.tick(90)
if sorting:
try:
next(sorting_algorithm_generator)
except StopIteration:
sorting = False
else:
draw(draw_info, sorting_algo_name, ascending)
for event in pygame.event.get():
if event.type == pygame.QUIT:
run = False
if event.type != pygame.KEYDOWN:
continue
if event.key == pygame.K_r:
draw_info.set_list(lst)
sorting = False
elif event.key == pygame.K_SPACE and sorting == False:
sorting = True
sorting_algorithm_generator = sorting_algorithm(draw_info, ascending)
elif event.key == pygame.K_a and not sorting:
ascending = True
elif event.key == pygame.K_d and not sorting:
ascending = False
pygame.quit()#exiting the window
- We create an empty list. Using the print() function, we ask the user to enter the number of elements in the list and taking the input using the input() method we add each element entered using the append() method to that empty list.
- pygame.time.clock() – This creates an object and keeps track of the time while sorting.
- clock.tick() – This gets time in milliseconds.
- Now we specify that when the space bar is clicked on the keyboard then the sorting takes place.
- pygame.quit() – Terminates the window.
8. Calling the Main Method:
if __name__ == "__main__":
main()#calling main method
- This is to call the main method.
Python Bubble Sort Visualiser Output
Summary
We have successfully created a Bubble Sort Visualizer Project using Pygame module of python. While creating this project we used three libraries.
- Pygame Module
- Math Module
- Random Module