Prerequisite: QuickSort
Tkinter is a very easy-to-use and beginner-friendly GUI library that can be used to visualize the sorting algorithms. Here Quick Sort Algorithm is visualized which is a divide and conquer algorithm. It first considers a pivot element then, creates two subarrays to hold elements less than the pivot value and elements greater than the pivot value, and then recursively sort the sub-arrays. There are two fundamental operations in the algorithm, swapping items in place and partitioning a section of the array. The process is repeated by recursion until the sub-arrays are small enough to be sorted easily. Ultimately, the smaller sub-arrays can be placed one on top of the other to produce a fully sorted and ordered set of elements.
In this article, we will use the Python GUI Library Tkinter to visualize the QuickSort algorithm.
Algorithm:
- Selecting any element as a pivot
- Elements lesser than the pivot are placed before it and the ones which are greater are placed after it. Two sub-arrays are created on either side of the pivot.
- The same process is applied recursively on the right and left sub-arrays to sort them.
Time Complexity :
- Best case: The best-case occurs when the pivot always separates the array into two equal halves. In the best case, the result will be log(N) levels of partitions, with the top-level having one array of size N, the next having an array of size N/2, and so on. The best-case complexity of the quick sort algorithm is O(log N)
- Worst case: The worst case will occur when the pivot does a poor job of breaking the array, i.e. when there are no elements in one partition and N-1 elements in the other. The worst-case time complexity of Quick Sort would be O(N^2).
Extension Code for Quick Sort :
This is the extension code for the quick sort algorithm which is imported in the main Tkinter visualizer code to implement the quick sort algorithm and return the sorted result.
Python3
# Extension Quick Sort Code# importing time moduleimport time# to implement divide and conquerdef partition(data, head, tail, drawData, timeTick): border = head pivot = data[tail] drawData(data, getColorArray(len(data), head, tail, border, border)) time.sleep(timeTick) for j in range(head, tail): if data[j] < pivot: drawData(data, getColorArray( len(data), head, tail, border, j, True)) time.sleep(timeTick) data[border], data[j] = data[j], data[border] border += 1 drawData(data, getColorArray(len(data), head, tail, border, j)) time.sleep(timeTick) # swapping pivot with border value drawData(data, getColorArray(len(data), head, tail, border, tail, True)) time.sleep(timeTick) data[border], data[tail] = data[tail], data[border] return border# head --> Starting index,# tail --> Ending indexdef quick_sort(data, head, tail, drawData, timeTick): if head < tail: partitionIdx = partition(data, head, tail, drawData, timeTick) # left partition quick_sort(data, head, partitionIdx-1, drawData, timeTick) # right partition quick_sort(data, partitionIdx+1, tail, drawData, timeTick)# Function to apply colors to bars while sorting:# Grey - Unsorted elements# Blue - Pivot point element# White - Sorted half/partition# Red - Starting pointer# Yellow - Ending pointer# Green - after all elements are sorted# assign color representation to elementsdef getColorArray(dataLen, head, tail, border, currIdx, isSwaping=False): colorArray = [] for i in range(dataLen): # base coloring if i >= head and i <= tail: colorArray.append('Grey') else: colorArray.append('White') if i == tail: colorArray[i] = 'Blue' elif i == border: colorArray[i] = 'Red' elif i == currIdx: colorArray[i] = 'Yellow' if isSwaping: if i == border or i == currIdx: colorArray[i] = 'Green' return colorArray |
Tkinter Implementation:
In this code, we are generating the data values as bars of different lengths and a particular color. The basic layout is designed in a Tkinter ‘Frame’ and the portion when the bars are generated and the quick sort algorithm is visualized is designed in a Tkinter ‘Canvas’.
The code essentially has the following components:
- Mainframe: a Tkinter frame to arrange all the necessary components(labels, buttons, speed bar, etc.) in an organized manner
- Canvas: A Tkinter canvas used as the space where the generated data bars are drawn and the sorting process is visualized
- generate(): Method to generate the data values by accepting a range and then passing that as a parameter to the drawData() function
- drawData(): Method to generate bars to normalized data values(within the given range) of a particular color on the canvas
- start_algorithm(): This function is called when the “START” button is pressed. It initiates the sorting process by calling the quick_sort() function from the Quick Sort Extension Code.
Python3
# code for Quick Sort Visualizer # using Python and Tkinter# import modulesfrom tkinter import *from tkinter import ttkimport randomfrom quick import quick_sort# initialising root class for Tkinterroot = Tk()root.title("Quick Sort Visualizer")# maximum window sizeroot.maxsize(900, 600)root.config(bg="Black")select_alg = StringVar()data = []# function to generate the data values # by accepting a given rangedef generate(): global data # minval : minimum value of the range minval = int(minEntry.get()) # maxval : maximum value of the range maxval = int(maxEntry.get()) # sizeval : number of data # values/bars to be generated sizeval = int(sizeEntry.get()) # creating a blank data list which will # be further filled with random data values # within the entered range data = [] for _ in range(sizeval): data.append(random.randrange(minval, maxval+1)) drawData(data, ['Red' for x in range(len(data))])# function to create the data bars # by creating a canvas in Tkinterdef drawData(data, colorlist): canvas.delete("all") can_height = 380 can_width = 550 x_width = can_width/(len(data) + 1) offset = 30 spacing = 10 # normalizing data for rescaling real-valued # numeric data within the # given range normalized_data = [i / max(data) for i in data] for i, height in enumerate(normalized_data): # top left corner x0 = i*x_width + offset + spacing y0 = can_height - height*340 # bottom right corner x1 = ((i+1)*x_width) + offset y1 = can_height # data bars are generated as Red # colored vertical rectangles canvas.create_rectangle(x0, y0, x1, y1, fill=colorlist[i]) canvas.create_text(x0+2, y0, anchor=SE, text=str(data[i])) root.update_idletasks()# function to initiate the sorting # process by calling the extension codedef start_algorithm(): global data if not data: return if (algmenu.get() == 'Quick Sort'): quick_sort(data, 0, len(data)-1, drawData, speedbar.get()) drawData(data, ['Green' for x in range(len(data))])# creating main user interface frame # and basic layout by creating a frameMainframe = Frame(root, width=600, height=200, bg="Grey")Mainframe.grid(row=0, column=0, padx=10, pady=5)canvas = Canvas(root, width=600, height=380, bg="Grey")canvas.grid(row=1, column=0, padx=10, pady=5)# creating user interface area in grid manner# first row componentsLabel(Mainframe, text="ALGORITHM", bg='Grey').grid(row=0, column=0, padx=5, pady=5, sticky=W)# algorithm menu for showing the # name of the sorting algorithmalgmenu = ttk.Combobox(Mainframe, textvariable=select_alg, values=["Quick Sort"])algmenu.grid(row=0, column=1, padx=5, pady=5)algmenu.current(0)# creating Start Button to start # the sorting visualization processButton(Mainframe, text="START", bg="Blue", command=start_algorithm).grid(row=1, column=3, padx=5, pady=5)# creating Speed Bar using scale in Tkinterspeedbar = Scale(Mainframe, from_=0.10, to=2.0, length=100, digits=2, resolution=0.2, orient=HORIZONTAL, label="Select Speed")speedbar.grid(row=0, column=2, padx=5, pady=5)# second row components# sizeEntry : scale to select # the size/number of data barssizeEntry = Scale(Mainframe, from_=3, to=60, resolution=1, orient=HORIZONTAL, label="Size")sizeEntry.grid(row=1, column=0, padx=5, pady=5)# minEntry : scale to select the # minimum value of data barsminEntry = Scale(Mainframe, from_=0, to=10, resolution=1, orient=HORIZONTAL, label="Minimum Value")minEntry.grid(row=1, column=1, padx=5, pady=5)# maxEntry : scale to select the # maximum value of data barsmaxEntry = Scale(Mainframe, from_=10, to=100, resolution=1, orient=HORIZONTAL, label="Maximum Value")maxEntry.grid(row=1, column=2, padx=5, pady=5)# creating generate buttonButton(Mainframe, text="Generate", bg="Red", command=generate).grid(row=0, column=3, padx=5, pady=5)# to stop automatic window terminationroot.mainloop() |
Output:
