Visualization in Insertion Sort
An Insertion Sort algorithm can be understood effortlessly by visualizing. We will write a program that visualizes the Insertion Sort Algorithm has been implemented. The Graphical User Interface(GUI) is applied in python using the pygame library.
The approach is simple, just generate some random array and fill the pygame window with bars. Bars are straight and vertical lines that represent array elements in an array list. We can use pygame.time.delay() to slow down the execution of the algorithm so that we can see the sorting process more clearly. Use a timer to see the performance of the algorithm. The pygame.event.get() method performs some action that is used to store all the events which the user performs, such as start and reset.
Ensure you have already installed the pygame library before running the following code.
The implementation is above discussed visualizer is given below:
# Visualization in Insertion Sort
# Using Python library
import pygame
import random
import time
pygame.font.init()
start = time.time()
#Total window
scrn = pygame.display.set_mode(
(900, 650)
)
# Title and Icon
pygame.display.set_caption(
"Visualizer Sort"
)
# Uncomment below lines for setting
# up the icon for the visuliser
# img = pygame.image.load('sorticon.png')
# pygame.display.set_icon(img)
# Boolean variable to run
# the program in while loop
run = True
# Window size and some initials
width = 900
length = 600
array =[0]*151
arr_clr =[(111, 227, 250)]*151
clr_ind = 0
clr =[(0, 214, 255), (210, 180, 140), \
(0, 0, 153), (255, 102, 0)]
font = pygame.font.SysFont("comicsans", 30)
font1 = pygame.font.SysFont("comicsans", 20)
# Generate a new Array
def generate_arr():
for i in range(1, 151):
arr_clr[i]= clr[0]
array[i]= random.randrange(1, 100)
# Initially generate a array
generate_arr()
# Function to refill the
# updates on the window
def refill():
scrn.fill((254, 246, 189))
draw()
pygame.display.update()
pygame.time.delay(10)
# Insertion Sort Algorithm:
def insertionSort(array):
for i in range(1, len(array)):
pygame.event.pump()
refill()
key = array[i]
arr_clr[i]= clr[2]
j = i-1
while j>= 0 and key<array[j]:
arr_clr[j]= clr[2]
array[j + 1]= array[j]
refill()
arr_clr[j]= clr[3]
j = j-1
array[j + 1]= key
refill()
arr_clr[i]= clr[0]
# Draw the array values
def draw():
# Text should be rendered
txt = font.render("For Sorting: Press 'Enter' ", \
1, (0, 0, 0))
# Position where text is placed
scrn.blit(txt, (20, 20))
txt1 = font.render("For New Array: Press 'R' ", \
1, (0, 0, 0))
scrn.blit(txt1, (20, 40))
txt2 = font1.render("Algorithm Used:"\
"Insertion Sort", 1, (0, 0, 0))
scrn.blit(txt2, (600, 60))
text3 = font1.render("Running Time(sec): "+\
str(int(time.time() - start)), \
1, (0, 0, 0))
scrn.blit(text3, (600, 20))
element_width =(width-150)//150
boundry_arr = 900 / 150
boundry_grp = 550 / 100
pygame.draw.line(scrn, (0, 0, 0), (0, 95), \
(900, 95), 6)
# Drawing the array values as lines
for i in range(1, 151):
pygame.draw.line(scrn, arr_clr[i], \
(boundry_arr * i-3, 100), \
(boundry_arr * i-3, \
array[i]*boundry_grp + 100), element_width)
# Program should be run
# continuously to keep the window open
while run:
# background
scrn.fill((254, 246, 189))
# Event handler stores all event
for event in pygame.event.get():
# On clicking Close button in window
if event.type == pygame.QUIT:
run = False
if event.type == pygame.KEYDOWN:
if event.key == pygame.K_r:
generate_arr()
if event.key == pygame.K_RETURN:
insertionSort(array)
draw()
pygame.display.update()
pygame.quit()
You can also try this code with Online Python Compiler
Run Code
OUTPUT
Frequently Asked Questions
Why do we use Insertion Sort?
Insertion sort is a sorting algorithm that builds the final sorted array one item at a time.
What is the best, average, and worst-case of the Insertion sort?
The best case of Insertion sort is n. Moreover, its average-case and worst-case complexity are the same is n^2.
What are the limitations of Insertion sort?
Insertion sort is a good sorting algorithm for small datasets, but it is not much effective against large data sets. This is the reason why it does not perform well as other sorting algorithms.
Conclusion
In this article, we have extensively discussed the topic of Insertion Sort visualization in pygame in detail. We hope that this blog has helped you enhance your knowledge regarding the subject of Insertion Sort visualization in pygame and if you would like to learn more, check out our Coding Ninjas Studio Resources.
Recommended Problem - Merge K Sorted Arrays
For peeps out there who want to learn more about Data Structures, Algorithms, Power programming, JavaScript, or any other upskilling, please refer to guided paths on Coding Ninjas Studio. Enroll in our courses, go for mock tests, solve problems available, and interview puzzles. Also, you can put your attention towards interview stuff- interview experiences and an interview bundle for placement preparations.
Thank you for reading.
Keep Learning and Keep improving.