Python ｜ Sort visualization ｜ It feels good to see
Visualize how you are sorting in Python
Visualize how data is sorted using Python's Tkinter
"I see!"
It is a code that seems to be.
before
after
As the content
--Quicksort --Merge sort --Selection sort
Will be carried out. Here is the sample code. Create some classes. After that, create a function. --Controller class --View class --Sort class
Sample code
sortSample.py
# =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
#With tkinter and time timer
#Visualize sort
# 2020.06.19 ProOJI
# =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
import tkinter
import time
#Canvas size
CANVAS_WIDTH = 600
CANVAS_HEIGHT = 400
#Weight at the time of drawing (s)
WAIT = 0
class Sort():
#Sort type
SELECTION_SORT = 1
QUICK_SORT = 2
MERGE_SORT = 3
def __init__(self, view):
'Object generation to sort'
self.view = view
def start(self, data, method):
'Start sorting'
#Set the list of data to sort
self.data = data
#Set the number of data to sort
self.num = len(data)
#Initialization of comparison count
self.compare_num = 0
#Sort according to method
if method == Sort.SELECTION_SORT:
#Execute selection sort
self.selection_sort(0, self.num - 1)
elif method == Sort.QUICK_SORT:
#Execute quick sort
self.quick_sort(0, self.num - 1)
elif method == Sort.MERGE_SORT:
#Prepare work memory for merge sort
self.work = [0] * self.num
#Merge sort execution
self.merge_sort(0, self.num - 1)
for num in self.data:
print(num)
#Return the number of comparisons
return self.compare_num
def selection_sort(self, left, right):
'Perform selection sort'
if left == right:
#Since there is only one data, sorting ends
return
#Temporarily determine the minimum value
min = self.data[left]
i_min = left
#Search for the minimum value from the sort range
for i in range(left, right + 1):
if min > self.data[i]:
#Minimum value update
min = self.data[i]
i_min = i
#Increment the number of comparisons
self.compare_num += 1
#Exchange the minimum value and the leftmost data
if i_min != left:
#Replace only if necessary
tmp = self.data[left]
self.data[left] = self.data[i_min]
self.data[i_min] = tmp
#Show current data sequence
self.view.draw_data(self.data)
#Narrow the range and select sort again
self.selection_sort(left + 1, right)
def quick_sort(self, left, right):
'Perform quicksort'
if left >= right:
#Sorting ends because the number of data is 1 or less
return
#Pivot determination
pivot = self.data[left]
i = left
j = right
#Place the numbers below pivot in the first half of the array,
#Collect numbers above pivot in the second half of the array
while True:
#Search for numbers above pivot from the left
while self.data[i] < pivot:
i += 1
#Increment the number of comparisons
self.compare_num += 1
#Search for numbers below pivot from the right
while self.data[j] > pivot:
j -= 1
#Increment the number of comparisons
self.compare_num += 1
# i >=Becoming j means
#On the left side of the array are the numbers below pivot
#That the numbers above pivot are gathered on the right side of the array
if i >= j:
#The partitioning process of the set is completed
break
#Exchange the two numbers you searched for
tmp = self.data[i]
self.data[i] = self.data[j]
self.data[j] = tmp
#Search resumes from the next number after the exchange
i += 1
j -= 1
#Show current data sequence
self.view.draw_data(self.data)
#Sort by a range of small numbers
self.quick_sort(left, i - 1)
#Sort by the range of large numbers
self.quick_sort(j + 1, right)
def merge_sort(self, left, right):
'Perform merge sort'
if left == right:
#Since there is only one data, sorting ends
return
#Divide the set in two at the center
mid = (left + right) // 2
#Sort the data of each set after division
self.merge_sort(left, mid)
self.merge_sort(mid + 1, right)
#Merge each sorted set
self.merge(left, mid, right)
#Show current data sequence
self.view.draw_data(self.data)
def merge(self, left, mid, right):
'Merge sets'
#Set the starting point of the first set
i = left
#Set the starting point of the second set
j = mid + 1
#Set the start point of the merge destination set
k = 0
#Either of the two sets
#Loop until everything is merged
while i <= mid and j <= right:
#Increment the number of comparisons
self.compare_num += 1
#Of the two sets without the merged data
#Merge the smaller of the first data
if (self.data[i] < self.data[j]):
self.work[k] = self.data[i]
#The index of the merged set and
#Increment the index of the merged set
i += 1
k += 1
else:
self.work[k] = self.data[j]
#The index of the merged set and
#Increment the index of the merged set
j += 1
k += 1
#A set with unmerged data remaining
#Merge into the merge destination set
while i <= mid:
#Increment the number of comparisons
self.compare_num += 1
self.work[k] = self.data[i]
i += 1
k += 1
while j <= right:
#Increment the number of comparisons
self.compare_num += 1
self.work[k] = self.data[j]
j += 1
k += 1
#Copy the merge destination set to data
j = 0
for i in range(left, right + 1):
self.data[i] = self.work[j]
j += 1
class View():
def __init__(self, master):
'UI related object generation'
#various settings
self.drawn_obj = []
#Determine the size of the canvas
self.canvas_width = CANVAS_WIDTH
self.canvas_height = CANVAS_HEIGHT
#Create a frame for displaying information
self.canvas_frame = tkinter.Frame(
master,
)
self.canvas_frame.grid(column=1, row=1)
#Create a frame for the operation widget
self.operation_frame = tkinter.Frame(
master,
)
self.operation_frame.grid(column=2, row=1, padx=10)
#Canvas generation and placement
self.canvas = tkinter.Canvas(
self.canvas_frame,
width=self.canvas_width,
height=self.canvas_height,
)
self.canvas.pack()
#Label generation and placement
self.text = tkinter.StringVar()
self.text.set("Press the start button")
self.label = tkinter.Label(
self.canvas_frame,
textvariable=self.text,
)
self.label.pack()
#Generation and placement of frames for text box placement
max_w = CANVAS_WIDTH // 2
max_h = CANVAS_HEIGHT // 2
if max_w < max_h:
max = max_w
else:
max = max_h
self.text_frame = tkinter.LabelFrame(
self.operation_frame,
text="Number of data (maximum" + str(max) + "）"
)
self.text_frame.pack(ipadx=10, pady=10)
self.entry = tkinter.Entry(
self.text_frame,
width=4
)
self.entry.pack()
#Generation and placement of frames for radio button placement
self.radio_frame = tkinter.LabelFrame(
self.operation_frame,
text="algorithm"
)
self.radio_frame.pack(ipadx=10, pady=10)
#Object generation for getting the checked button
self.sort = tkinter.IntVar()
self.sort.set(Sort.QUICK_SORT)
#Create and place 3 radio buttons for algorithm selection
self.selection_button = tkinter.Radiobutton(
self.radio_frame,
variable=self.sort,
text="Selection sort",
value=Sort.SELECTION_SORT
)
self.selection_button.pack()
self.quick_button = tkinter.Radiobutton(
self.radio_frame,
variable=self.sort,
text="Quick sort",
value=Sort.QUICK_SORT
)
self.quick_button.pack()
self.merge_button = tkinter.Radiobutton(
self.radio_frame,
variable=self.sort,
text="Merge sort",
value=Sort.MERGE_SORT
)
self.merge_button.pack()
#Generation and placement of start buttons
self.button = tkinter.Button(
self.operation_frame,
text="start",
)
self.button.pack()
def start(self, n):
'Draw background'
#Set the number of data
self.num = n
#Determine the width of the line that represents one piece of data
self.line_width = CANVAS_WIDTH / self.num
#Determine line height for data value 1
#When the data value is N, the line height is self.line_height *Become N
self.line_height = CANVAS_HEIGHT / self.num
#When there is too much data to draw
if self.line_width < 2 or self.line_height < 2:
return False
#For background position adjustment (centered)
self.offset_x = int(
(self.canvas.winfo_width() - self.line_width * self.num) / 2
)
self.offset_y = int(
(self.canvas.winfo_height() - self.line_height * self.num + 1) / 2
)
#Delete the data once drawn
for obj in self.drawn_obj:
self.canvas.delete(obj)
#Empty the drawn data list because it was deleted
self.drawn_obj = []
#Delete background object in advance
self.canvas.delete("background")
#Draw background
self.canvas.create_rectangle(
self.offset_x,
self.offset_y,
int(self.offset_x + self.line_width * self.num),
int(self.offset_y + self.line_height * self.num),
width=0,
fill="#EEEEFF",
tag="background"
)
#Immediately reflect drawing
self.canvas.update()
return True
def get_algorithm(self):
'Sort algorithm acquisition'
return self.sort.get()
def get_data_num(self):
'Get the number of data'
return int(self.entry.get())
def draw_data(self, data):
'Draw a sequence of data as a line'
#Delete the data once drawn
for obj in self.drawn_obj:
self.canvas.delete(obj)
#Empty the drawn data list because it was deleted
self.drawn_obj = []
#Draw the numbers in the list as a rectangle
i = 0
for value in data:
#Determine the start and end points of the rectangle
#Determine the horizontal coordinates of the rectangle from the data position
x1 = int(self.offset_x + i * self.line_width)
x2 = int(self.offset_x + (i + 1) * self.line_width)
#Determine the vertical coordinates of the rectangle from the data values
y1 = int(self.offset_y + self.line_height * (self.num - value))
y2 = int(self.offset_y + self.line_height * self.num)
#Add a tag so that you can erase it later
tag = "line" + str(i)
self.drawn_obj.append(tag)
#Draw a rectangle
self.canvas.create_rectangle(
x1, y1,
x2, y2,
tag=tag,
fill="#FFA588",
width=1
)
i += 1
#Immediately reflect drawing
self.canvas.update()
#Sleep for WAIT seconds
time.sleep(WAIT)
def update_message(self, text):
'Update message to display on label'
#Set the character string to be drawn on the label
self.text.set(text)
#Immediately reflect drawing
self.label.update()
class Controller():
def __init__(self, view, sort):
'Create objects to control Sort and View'
#View and Sort object settings to control
self.view = view
self.sort = sort
#Accepts events when the button is clicked
self.view.button["command"] = self.button_click
def button_click(self):
'Processing when a button is clicked'
num = self.view.get_data_num()
#Start View
if not self.view.start(num):
#Message update
self.view.update_message(
"Too much data"
)
#Do nothing if you fail
return
#Generate a random number list of the number of data NUM with NUM as the maximum value
data = []
for _ in range(num):
import random
data.append(int(random.randint(0, num - 1)))
#When sorting the initial data in descending order
#data = []
# for i in range(num):
# data.append(num - i)
#Message update
self.view.update_message("Sorting")
#Start sorting
compare_num = self.sort.start(data, self.view.get_algorithm())
#Message update
self.view.update_message(
"Sorting is complete! (Comparison:" + str(compare_num) + "）"
)
#App generation
app = tkinter.Tk()
app.title("sort")
#View object creation
view = View(app)
#Sort object creation
sort = Sort(view)
#Controller object creation
controller = Controller(view, sort)
#Waiting for event reception in mainloop
app.mainloop()
Summary
There are various sorting algorithms. I hope you can use it well.
- Reference information
I summarized the sort algorithm
Recommended Posts