Requisito previo: QuickSort
Tkinter es una biblioteca GUI muy fácil de usar y amigable para principiantes que se puede usar para visualizar los algoritmos de clasificación. Aquí se visualiza el algoritmo de clasificación rápida, que es un algoritmo de divide y vencerás. Primero considera un elemento pivote, luego crea dos subarreglos para contener elementos menores que el valor pivote y elementos mayores que el valor pivote, y luego ordena recursivamente los subarreglos. Hay dos operaciones fundamentales en el algoritmo, intercambiar elementos en su lugar y dividir una sección de la array. El proceso se repite por recursión hasta que los subconjuntos son lo suficientemente pequeños como para clasificarlos fácilmente. En última instancia, los subconjuntos más pequeños se pueden colocar uno encima del otro para producir un conjunto de elementos completamente clasificado y ordenado.
En este artículo, usaremos la biblioteca Tkinter de la GUI de Python para visualizar el algoritmo QuickSort.
Algoritmo:
- Seleccionar cualquier elemento como pivote
- Los elementos menores que el pivote se colocan antes de él y los que son mayores se colocan después. Se crean dos subarreglos a cada lado del pivote.
- El mismo proceso se aplica recursivamente en los subconjuntos derecho e izquierdo para ordenarlos.
Complejidad del tiempo:
- Mejor caso: el mejor caso ocurre cuando el pivote siempre separa la array en dos mitades iguales. En el mejor de los casos, el resultado será log(N) niveles de particiones, con el nivel superior con una array de tamaño N, el siguiente con una array de tamaño N/2, y así sucesivamente. La complejidad del mejor de los casos del algoritmo de clasificación rápida es O (log N)
- Peor caso: El peor caso ocurrirá cuando el pivote haga un mal trabajo al romper la array, es decir, cuando no haya elementos en una partición y N-1 elementos en la otra. La complejidad de tiempo en el peor de los casos de Quick Sort sería O(N^2) .
Código de extensión para clasificación rápida:
Este es el código de extensión para el algoritmo de ordenación rápida que se importa en el código principal del visualizador de Tkinter para implementar el algoritmo de ordenación rápida y devolver el resultado ordenado.
Python3
# Extension Quick Sort Code # importing time module import time # to implement divide and conquer def 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 index def 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 elements def 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
Implementación de Tkinter:
En este código, estamos generando los valores de datos como barras de diferentes longitudes y un color particular. El diseño básico está diseñado en un ‘Marco’ de Tkinter y la parte en la que se generan las barras y se visualiza el algoritmo de clasificación rápida está diseñado en un ‘Canvas’ de Tkinter.
El código tiene esencialmente los siguientes componentes:
- Mainframe: un marco Tkinter para organizar todos los componentes necesarios (etiquetas, botones, barra de velocidad, etc.) de manera organizada
- Canvas: un lienzo de Tkinter utilizado como el espacio donde se dibujan las barras de datos generadas y se visualiza el proceso de clasificación
- generar(): método para generar los valores de datos aceptando un rango y luego pasándolo como un parámetro a la función drawData()
- drawData(): método para generar barras a valores de datos normalizados (dentro del rango dado) de un color particular en el lienzo
- start_algorithm(): Esta función se llama cuando se presiona el botón «INICIO». Inicia el proceso de clasificación llamando a la función quick_sort() desde el código de extensión de clasificación rápida.
Python3
# code for Quick Sort Visualizer # using Python and Tkinter # import modules from tkinter import * from tkinter import ttk import random from quick import quick_sort # initialising root class for Tkinter root = Tk() root.title("Quick Sort Visualizer") # maximum window size root.maxsize(900, 600) root.config(bg="Black") select_alg = StringVar() data = [] # function to generate the data values # by accepting a given range def 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 Tkinter def 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 code def 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 frame Mainframe = 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 components Label(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 algorithm algmenu = 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 process Button(Mainframe, text="START", bg="Blue", command=start_algorithm).grid(row=1, column=3, padx=5, pady=5) # creating Speed Bar using scale in Tkinter speedbar = 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 bars sizeEntry = 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 bars minEntry = 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 bars maxEntry = 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 button Button(Mainframe, text="Generate", bg="Red", command=generate).grid(row=0, column=3, padx=5, pady=5) # to stop automatic window termination root.mainloop()
Producción: