Pythonでソートをしている様子を可視化
PythonのTkinterを利用して、データをソートしていく様子を可視化して
「なるほど！」
と思えるコードです。
before
after
内容としては
- クイックソート
- マージソート
- 選択ソート
を実施します。
サンプルコードはこちらです。
いくつかのクラスを作成します。あとは関数を作ります。
- Controllerクラス
- Viewクラス
- Sortクラス
サンプルコード
sortSample.py
# =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
# tkinter と timeのタイマーで
# ソートを可視化する
# 2020.06.19 ProOJI
# =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
import tkinter
import time
# キャンバスのサイズ
CANVAS_WIDTH = 600
CANVAS_HEIGHT = 400
# 描画時のウェイト（s）
WAIT = 0
class Sort():
# ソート種類
SELECTION_SORT = 1
QUICK_SORT = 2
MERGE_SORT = 3
def __init__(self, view):
'ソートを行うオブジェクト生成'
self.view = view
def start(self, data, method):
'ソートを開始'
# ソートするデータのリストを設定
self.data = data
# ソートするデータの数を設定
self.num = len(data)
# 比較回数の初期化
self.compare_num = 0
# methodに応じてソートを実行
if method == Sort.SELECTION_SORT:
# 選択ソート実行
self.selection_sort(0, self.num - 1)
elif method == Sort.QUICK_SORT:
# クイックソート実行
self.quick_sort(0, self.num - 1)
elif method == Sort.MERGE_SORT:
# マージソート用のワークメモリを用意
self.work = [0] * self.num
# マージソート実行
self.merge_sort(0, self.num - 1)
for num in self.data:
print(num)
# 比較回数を返却
return self.compare_num
def selection_sort(self, left, right):
'選択ソートを実行'
if left == right:
# データ数１つなのでソート終了
return
# 最小値を仮で決定
min = self.data[left]
i_min = left
# ソート範囲から最小値を探索
for i in range(left, right + 1):
if min > self.data[i]:
# 最小値の更新
min = self.data[i]
i_min = i
# 比較回数をインクリメント
self.compare_num += 1
# 最小値と左端のデータを交換
if i_min != left:
# 交換必要な場合のみ交換
tmp = self.data[left]
self.data[left] = self.data[i_min]
self.data[i_min] = tmp
# 現在のデータの並びを表示
self.view.draw_data(self.data)
# 範囲を狭めて再度選択ソート
self.selection_sort(left + 1, right)
def quick_sort(self, left, right):
'クイックソートを実行'
if left >= right:
# データ数１つ以下なのでソート終了
return
# pivot の決定
pivot = self.data[left]
i = left
j = right
# pivot以下の数字を配列の前半に、
# pivot以上の数字を配列の後半に集める
while True:
# pivot以上の数字を左側から探索
while self.data[i] < pivot:
i += 1
# 比較回数をインクリメント
self.compare_num += 1
# pivot以下の数字を右側から探索
while self.data[j] > pivot:
j -= 1
# 比較回数をインクリメント
self.compare_num += 1
# i >= j になったということは、
# 配列の左側にpivot以下の数字が、
# 配列の右側にpivot以上の数字が集まったということ
if i >= j:
# 集合の分割処理は終了
break
# 探索した２つの数字を交換
tmp = self.data[i]
self.data[i] = self.data[j]
self.data[j] = tmp
# 交換後の数字の次から探索再開
i += 1
j -= 1
# 現在のデータの並びを表示
self.view.draw_data(self.data)
# 小さい数字を集めた範囲に対してソート
self.quick_sort(left, i - 1)
# 大きい数字を集めた範囲に対してソート
self.quick_sort(j + 1, right)
def merge_sort(self, left, right):
'マージソートを実行'
if left == right:
# データ数１つなのでソート終了
return
# 集合を中央で２つに分割する
mid = (left + right) // 2
# 分割後の各集合のデータをそれぞれソートする
self.merge_sort(left, mid)
self.merge_sort(mid + 1, right)
# ソート済みの各集合をマージする
self.merge(left, mid, right)
# 現在のデータの並びを表示
self.view.draw_data(self.data)
def merge(self, left, mid, right):
'集合をマージする'
# １つ目の集合の開始点をセット
i = left
# ２つ目の集合の開始点をセット
j = mid + 1
# マージ先集合の開始点をセット
k = 0
# ２つの集合のどちらかが、
# 全てマージ済みになるまでループ
while i <= mid and j <= right:
# 比較回数をインクリメント
self.compare_num += 1
# マージ済みデータを抜いた２つの集合の、
# 先頭のデータの小さい方をマージ
if (self.data[i] < self.data[j]):
self.work[k] = self.data[i]
# マージした集合のインデックスと、
# マージ先集合のインデックスをインクリメント
i += 1
k += 1
else:
self.work[k] = self.data[j]
# マージした集合のインデックスと、
# マージ先集合のインデックスをインクリメント
j += 1
k += 1
# マージ済みでないデータが残っている集合を、
# マージ先集合にマージ
while i <= mid:
# 比較回数をインクリメント
self.compare_num += 1
self.work[k] = self.data[i]
i += 1
k += 1
while j <= right:
# 比較回数をインクリメント
self.compare_num += 1
self.work[k] = self.data[j]
j += 1
k += 1
# マージ先集合を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関連のオブジェクト生成'
# 各種設定
self.drawn_obj = []
# キャンバスのサイズを決定
self.canvas_width = CANVAS_WIDTH
self.canvas_height = CANVAS_HEIGHT
# 情報表示用のフレームを作成
self.canvas_frame = tkinter.Frame(
master,
)
self.canvas_frame.grid(column=1, row=1)
# 操作用ウィジェットのフレームを作成
self.operation_frame = tkinter.Frame(
master,
)
self.operation_frame.grid(column=2, row=1, padx=10)
# キャンバスの生成と配置
self.canvas = tkinter.Canvas(
self.canvas_frame,
width=self.canvas_width,
height=self.canvas_height,
)
self.canvas.pack()
# ラベルの生成と配置
self.text = tkinter.StringVar()
self.text.set("開始ボタンを押してね")
self.label = tkinter.Label(
self.canvas_frame,
textvariable=self.text,
)
self.label.pack()
# テキストボックス配置用のフレームの生成と配置
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="データ数（最大" + str(max) + "）"
)
self.text_frame.pack(ipadx=10, pady=10)
self.entry = tkinter.Entry(
self.text_frame,
width=4
)
self.entry.pack()
# ラジオボタン配置用のフレームの生成と配置
self.radio_frame = tkinter.LabelFrame(
self.operation_frame,
text="アルゴリズム"
)
self.radio_frame.pack(ipadx=10, pady=10)
# チェックされているボタン取得用のオブジェクト生成
self.sort = tkinter.IntVar()
self.sort.set(Sort.QUICK_SORT)
# アルゴリズム選択用のラジオボタンを３つ作成し配置
self.selection_button = tkinter.Radiobutton(
self.radio_frame,
variable=self.sort,
text="選択ソート",
value=Sort.SELECTION_SORT
)
self.selection_button.pack()
self.quick_button = tkinter.Radiobutton(
self.radio_frame,
variable=self.sort,
text="クイックソート",
value=Sort.QUICK_SORT
)
self.quick_button.pack()
self.merge_button = tkinter.Radiobutton(
self.radio_frame,
variable=self.sort,
text="マージソート",
value=Sort.MERGE_SORT
)
self.merge_button.pack()
# 開始ボタンの生成と配置
self.button = tkinter.Button(
self.operation_frame,
text="開始",
)
self.button.pack()
def start(self, n):
'背景を描画'
# データ数をセット
self.num = n
# １つのデータを表す線の幅を決定
self.line_width = CANVAS_WIDTH / self.num
# データの値１の線の高さを決定
# データの値が N の時、線の高さは self.line_height * N となる
self.line_height = CANVAS_HEIGHT / self.num
# データ数が多すぎて描画できない場合
if self.line_width < 2 or self.line_height < 2:
return False
# 背景位置調整用（中央寄せ）
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
)
# 一旦描画しているデータを削除
for obj in self.drawn_obj:
self.canvas.delete(obj)
# 削除したので描画済みデータリストは空にする
self.drawn_obj = []
# 事前に背景オブジェクトを削除
self.canvas.delete("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"
)
# 即座に描画を反映
self.canvas.update()
return True
def get_algorithm(self):
'ソートアルゴリズム取得'
return self.sort.get()
def get_data_num(self):
'データ数取得'
return int(self.entry.get())
def draw_data(self, data):
'データの並びを線としてを描画'
# 一旦描画しているデータを削除
for obj in self.drawn_obj:
self.canvas.delete(obj)
# 削除したので描画済みデータリストは空にする
self.drawn_obj = []
# リストの数字を矩形で描画
i = 0
for value in data:
# 矩形の始点と終点を決定
# データ位置から矩形の横方向座標を決定
x1 = int(self.offset_x + i * self.line_width)
x2 = int(self.offset_x + (i + 1) * self.line_width)
# データの値から矩形の縦方向座標を決定
y1 = int(self.offset_y + self.line_height * (self.num - value))
y2 = int(self.offset_y + self.line_height * self.num)
# 後から消せるようにtagをつけておく
tag = "line" + str(i)
self.drawn_obj.append(tag)
# 長方形を描画
self.canvas.create_rectangle(
x1, y1,
x2, y2,
tag=tag,
fill="#FFA588",
width=1
)
i += 1
# 描画を即座に反映
self.canvas.update()
# WAIT秒分だけスリープ
time.sleep(WAIT)
def update_message(self, text):
'メッセージを更新してラベルに表示'
# ラベルに描画する文字列をセット
self.text.set(text)
# 描画を即座に反映
self.label.update()
class Controller():
def __init__(self, view, sort):
'SortとViewを制御するオブジェクトを生成'
# 制御するViewとSortのオブジェクト設定
self.view = view
self.sort = sort
# ボタンクリック時のイベントを受け付け
self.view.button["command"] = self.button_click
def button_click(self):
'ボタンクリック時の処理'
num = self.view.get_data_num()
# Viewの開始
if not self.view.start(num):
# メッセージ更新
self.view.update_message(
"データ数が多すぎます"
)
# 失敗したら何もしない
return
# NUMを最大値としたデータ数NUMの乱数リストを生成
data = []
for _ in range(num):
import random
data.append(int(random.randint(0, num - 1)))
# 初期データの並びを降順にする場合
#data = []
# for i in range(num):
# data.append(num - i)
# メッセージ更新
self.view.update_message("ソート中です")
# ソートを開始
compare_num = self.sort.start(data, self.view.get_algorithm())
# メッセージ更新
self.view.update_message(
"ソート完了！（比較：" + str(compare_num) + "）"
)
# アプリ生成
app = tkinter.Tk()
app.title("ソート")
# Viewオブジェクト生成
view = View(app)
# Sortオブジェクト生成
sort = Sort(view)
# Controllerオブジェクト生成
controller = Controller(view, sort)
# mainloopでイベント受付を待機
app.mainloop()
まとめ
いろいろなソートアルゴリズムがありますね。
上手に使えるといいですね。
- 参考情報