Heap Sort Visualization in Pygame

Visualization in Heap Sort

We can understand Heapsort very easily using visualization. We will write a program that visualizes the Heap Sort Algorithm implemented. The Graphical User Interface(GUI) is applied in python using the pygame library.

The approach is easy and simple, generate some random array and fill the pygame window with bars. Bars are straight and vertical lines representing array elements in an array list. 

Do the process of heapify in the array to perform sorting. We can use pygame.time.delay() to slow down the algorithm's execution 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. 

As per observation, Heapsort is faster than other sorting algorithms like insertion sort or selection sort. We can say that it matches the merge sort algorithm in speed.

Ensure you have already installed the pygame library before running the following code. 

The implementation of the above-discussed visualizer is given below:

# Visualization in Heap Sort
# Using Python library

import pygame
import time
import random
pygame.font.init()
start = time.time()

# Total window
screen = 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 = [(0, 204, 102)]*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 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():
	screen.fill((254, 246, 189))
	draw()
	pygame.display.update()
	pygame.time.delay(10)

# Heap Sort Algorithm
def heapSort(array):
	n = len(array)
	for i in range(n//2-1, -1, -1):
		pygame.event.pump()
		heapify(array, i, n)
	for i in range(n-1, 0, -1):
		array[i], array[0] = array[0], array[i]
		arr_clr[i] = clr[1]
		refill()
		heapify(array, 0, i)

def heapify(array, root, size):
	left = root * 2 + 1
	right = root * 2 + 2
	largest = root
	if left < size and array[left] > array[largest]:
		largest = left
	if right < size and array[right] > array[largest]:
		largest = right
	if largest != root:
		arr_clr[largest] = clr[2]
		arr_clr[root] = clr[2]
		array[largest],\
		array[root] = array[root],\
		array[largest]
		refill()
		arr_clr[largest] = clr[0]
		arr_clr[root] = clr[0]
		heapify(array, largest, size)
		refill()

# Draw the array values
def draw():

	# Text should be rendered
	text = font.render("For Sorting: Press 'Enter' ",
						1, (0, 0, 0))
	# Position where text is placed
	screen.blit(text, (20, 20))
	text1 = font.render("For New Array: Press 'R' ",
						1, (0, 0, 0))
	screen.blit(text1, (20, 40))
	text2 = font1.render("Algorithm Used:" +
						"Heap Sort", 1, (0, 0, 0))
	screen.blit(text2, (600, 60))
	text3 = font1.render("Running Time(sec): " +
						str(int(time.time() - start)),
						1, (0, 0, 0))
	screen.blit(text3, (600, 20))
	element_width = (width-150)//150
	boundry_arr = 900 / 150
	boundry_grp = 550 / 100
	pygame.draw.line(screen, (0, 0, 0), (0, 95),
						(900, 95), 6)

	# Drawing the array values as lines
	for i in range(1, 151):
		pygame.draw.line(screen, 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:
	#for background
	screen.fill((254, 246, 189))

	# Event handler stores all event
	for event in pygame.event.get():

		# If we click the Close button in the 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:
				heapSort(array)
	draw()
	pygame.display.update()

pygame.quit()

You can also try this code with Online Python Compiler

Run Code

OUTPUT

Also Read - Selection Sort in C

Frequently Asked Questions

What are the limitations of Heapsort?

Heapsort is not a stable sorting technique. The processing time for heapsort is also more than other sorting algorithms.

Is heap sort better than merge sort?

Merge sort is faster than heapsort in terms of processing the larger dataset, but it requires double the memory as compared to heapsort because of the second array.

What is the time complexity of Heapsort?

The time complexity of heapsort is O(n log n) using heapify versions.

Conclusion

In this article, we have extensively discussed the topic of Heap Sort visualization in pygame in detail. We hope that this blog has helped you enhance your knowledge regarding the subject of Heap Sort visualization in pygame. 

If you would like to learna more, check out our Coding Ninjas Studio Resources. Still, the knowledge never stops, have a look at more related articles like Web Applications and many more. Do upvote our blog to help other ninjas grow. 

Recommended Problems - 

• Sort 0 1 2 
• Wiggle sort
• Find first and last position in sorted array

A ninja never stops learning, so to feed your quest to learn and become more advanced and skilled, head over to our practice platform Coding Ninjas Studio to practice advanced-level problems. Attempt mock tests, read interview experiences, interview bundles, and much more! 

You can refer to programming fundamentals and SQL practice questions to sharpen your skills. If you need guidance at any stage while learning, then you can go to our Guided path.

Happy coding!

Until then, Keep Learning and Keep improving.