An algorithm like Quicksort algorithm is hard to understand theoretically. We can understand easily by visualizing such kind of algorithms. In this article, a program that visualizes the Quicksort Algorithm has been implemented.
The Graphical User Interface(GUI) is implemented in python using pygame library.
Approach:
- An array of random values is generated and are drawn as lines(bars) in the window.
- Since the algorithm performs the operation very fast, pygame.time.delay() has been used to slow down the process.
- Assign specific keys for each operation (start sorting, reset bars).
- The actions are performed using
‘pygame.event.get()’method, which stores all the events which user performs. - Different colors are used to indicate types of bar.
- Green – Unsorted bar
- Blue – Pivot bar
- Orange – Sorted bar
Examples:
Input:
Press “Enter” key to Perform Visualization.
Press “r” key to generate new array.
Output:
Initial:
Sorting:
Final:
Please make sure to install the pygame library in your system.
Below is the implementation of the above visualizer:
Python
# Python implementation of the # Sorting visualiser: Quick Sort# Importsimport pygameimport randompygame.font.init()# Total windowscreen = pygame.display.set_mode( (900, 650) )# Title and Icon pygame.display.set_caption("SORTING VISUALISER")# Uncomment below lines for setting # up the icon for the visuliser# img = pygame.image.load('sort_icon.png')# pygame.display.set_icon(img)# Boolean variable to run # the program in while looprun = True# Window size and some initialswidth = 900length = 600array =[0]*151arr_clr =[(0, 204, 102)]*151clr_ind = 0clr =[(0, 204, 102), (255, 0, 0),\ (0, 0, 153), (255, 102, 0)]fnt = pygame.font.SysFont("comicsans", 30)fnt1 = pygame.font.SysFont("comicsans", 20)# Function to generate new Arraydef generate_arr(): for i in range(1, 151): arr_clr[i]= clr[0] array[i]= random.randrange(1, 100) # Initially generate a arraygenerate_arr() # Function to refill the # updates on the windowdef refill(): screen.fill((255, 255, 255)) draw() pygame.display.update() pygame.time.delay(30) # Sorting Algo:Quick sortdef quicksort(array, l, r): if l<r: pi = partition(array, l, r) quicksort(array, l, pi-1) refill() for i in range(0, pi + 1): arr_clr[i]= clr[3] quicksort(array, pi + 1, r) # Function to partition the arraydef partition(array, low, high): pygame.event.pump() pivot = array[high] arr_clr[high]= clr[2] i = low-1 for j in range(low, high): arr_clr[j]= clr[1] refill() arr_clr[high]= clr[2] arr_clr[j]= clr[0] arr_clr[i]= clr[0] if array[j]<pivot: i = i + 1 arr_clr[i]= clr[1] array[i], array[j]= array[j], array[i] refill() arr_clr[i]= clr[0] arr_clr[high]= clr[0] array[i + 1], array[high] = array[high], array[i + 1] return ( i + 1 ) # Function to Draw the # array valuesdef draw(): # Text should be rendered txt = fnt.render("SORT : PRESS 'ENTER'",\ 1, (0, 0, 0)) # Position where text is placed screen.blit(txt, (20, 20)) txt1 = fnt.render("NEW ARRAY : PRESS 'R'",\ 1, (0, 0, 0)) screen.blit(txt1, (20, 40)) txt2 = fnt1.render("ALGORITHM USED: QUICK SORT",\ 1, (0, 0, 0)) screen.blit(txt2, (600, 60)) 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 openwhile run: # background screen.fill((255, 255, 255)) # Event handler stores all event for event in pygame.event.get(): # If we click 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: quicksort(array, 1, len(array)-1) draw() pygame.display.update() pygame.quit() |
Output:
