Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Insertion Sort
3.
Visualization in Insertion Sort
4.
Frequently Asked Questions
4.1.
Why do we use Insertion Sort?
4.2.
What is the best, average, and worst-case of the Insertion sort?
4.3.
What are the limitations of Insertion sort?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Insertion Sort Visualization in Pygame

Author Sagar Mishra
0 upvote

Introduction

Insertion sort is a type of sorting algorithm where the elements are transferred to the right position one by one. In other words, an insertion sort allows for building the final sorted list, one item at a time, with the movement of higher-positioned elements. An insertion sort has the advantage of simplicity and low overhead.

In this article, we will discuss the definition of Insertion sort, and visualization in insertion sort.

                             

Insertion Sort

In an insertion sort, the first element of the array is taken as a sorted array, even if it's an unsorted array. In this sorting technique, every element in the array is checked with the preceding elements, resulting in a growing sorted output array. The sorting algorithm removes one element at a time in each iteration and finds the best location within the sorted array, and inserts it there. The iteration continues till the complete array list is sorted.

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.

Live masterclass