今回は Python の Tkinter を利用して「ソート」でデータを並び替えていく様子の可視化を行なっていきます。
スクリプトを実行すると下のアニメーションのようにどんどんデータの並びが変わっていく様子が確認できます。
このアニメーションでは1回目は「クイックソート 」、2回目は「マージソート」、3回目は「選択ソート」でデータの並び替えを行っています。
こんな感じでアルゴリズム毎にソートがデータの並び替えがどのように行われるのかを直感的に理解することができます。
ソートの様子を可視化するスクリプト
ソートによりデータの並び替えが行われていく様子を可視化するスクリプトは下記のようになります。
# -*- coding:utf-8 -*-
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:
# データ数1つなのでソート終了
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:
# データ数1つ以下なのでソート終了
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
# 探索した2つの数字を交換
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:
# データ数1つなのでソート終了
return
# 集合を中央で2つに分割する
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):
'集合をマージする'
# 1つ目の集合の開始点をセット
i = left
# 2つ目の集合の開始点をセット
j = mid + 1
# マージ先集合の開始点をセット
k = 0
# 2つの集合のどちらかが、
# 全てマージ済みになるまでループ
while i <= mid and j <= right:
# 比較回数をインクリメント
self.compare_num += 1
# マージ済みデータを抜いた2つの集合の、
# 先頭のデータの小さい方をマージ
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)
# アルゴリズム選択用のラジオボタンを3つ作成し配置
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
# 1つのデータを表す線の幅を決定
self.line_width = CANVAS_WIDTH / self.num
# データの値1の線の高さを決定
# データの値が 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()
スクリプトの実行
スクリプトを実行すると下のような画面が表示されます。
さらに下図で示す画面右側の設定フィールドで、データ数とアルゴリズムを指定します。
データ数とアルゴリズムの指定後、開始ボタンを押すと、指定したデータ数のデータがランダムに並び、そのデータが指定したアルゴリズムでソートされていきます。
データは棒グラフで表しており、高さがデータの値の大きさを表現しています。
ソートが完了すると、画面下側のラベルにソートが完了した旨のメッセージとソートするのに要した比較回数が表示されます。
ソート完了後は、また画面右側でデータ数とアルゴリズムを指定し直して「開始」ボタンをクリックすれば、再びデータのソートを行うことができます。
データ数は「キャンバスの幅÷2」or「キャンバスの高さ÷2」の小さいほうを最大数としています(これよりデータ数が多いとデータを表す棒グラフが枠線だけになって真っ黒になってしまうため)。
ですので、スクリプト先頭のキャンバスサイズの部分を変更すればもっと大きなデータ数を試すこともできます。
# キャンバスのサイズ
CANVAS_WIDTH = 600
CANVAS_HEIGHT = 400
またスクリプトではデータの描画時にスリープ処理を入れられるようにしています。
これは、スリープを入れることで「ゆっくり・じっくり」ソートされていく様子を確認できるようにするためです。
同様にスクリプトの先頭付近にこのスリープする時間を設定することが出来るようにしています。
# 描画時のウェイト(s)
WAIT = 0
スポンサーリンク
スクリプトの解説
最後に簡単にスクリプトの解説をしておきます。
スクリプトは Controller
クラス・View
クラス・Sort
クラスの3つのクラスから構成しています。各クラスのポイントだけ説明していきます。
Controller
クラス
Controller
はユーザーからのイベント(アクション)を受け付けるクラスです。
今回のスクリプトでは受け付けるイベントは「開始ボタンのクリック」のみです。
開始ボタンがクリックされた際には Controller
クラスのオブジェクトは以下のように処理を行います。
設定値の取得
まず後述する View
クラスによって設置されるテキストボックス(データ数)とラジオボタン(使用アルゴリズム)の設定値を取得(get_data_num
メソッドと get_algorithm
メソッドを実行)します。
データのリストの生成
さらに get_data_num
メソッドによって取得されたデータ数の長さのリストを作成します。このリストは random
モジュールを利用してランダムに生成します。
View
クラスと Sort
クラスへの処理依頼
さらに取得した設定値を用いて View
クラスと Sort
クラスのオブジェクトに処理開始を依頼(start
メソッドを実行)します。
View
クラス
View
は主にアプリの画面の描画を行うクラスです。View
のオブジェクトは主に下記のことを行います。
- ウィジェットの生成と配置
- 設定値の取得
- 背景の描画
- データの描画
一つ一つ説明していきます。
ウィジェットの生成と配置
View
クラスはインスタンス生成時(__init__
実行時)にアプリに表示するウィジェット(キャンバス・フレーム・ボタン・ラベル・テキストボックス・ラジオボタン)を作成します。
アプリの画面を構成するウィジェットは下の図のようになります。
これらのウィジェットの生成は全て Tkinter のクラスのオブジェクトを生成することで実現できます。さらにこれらのオブジェクトに grid
や pack
メソッドを実行させることで、ウィジェットの配置を行なっています。
詳細はサンプルスクリプトの View
クラスの __init__
を読んでみてください。
設定値の取得
また View
クラスには get_data_num
メソッドと get_algorithm
メソッドを用意しています。
get_data_num
メソッドはテキストフィールドに設定されたデータ数を取得するメソッドです。
また get_algorithm
メソッドはラジオボタンで選択されたアルゴリズム(アルゴリズムを表す数値)を取得するメソッドです。
これらのメソッドで取得した設定に基づき View
クラスや Sort
クラスはキャンバスへのデータの描画や実際のソート処理を行います。
背景の描画
View
クラスのオブジェクトは start
メソッドでデータを描画するための背景の描画を行います。
背景の横サイズは「データを表す棒グラフの幅×データ数」、背景の縦サイズは「データの値1あたりの棒グラフの高さ×データ数」により計算しています。
「データを表す棒グラフの幅」はスクリプトの先頭で定義している CANVAS_WIDTH
をデータ数で割った値、「データの値1あたりの棒グラフの高さ」は CANVAS_HEIGHT
をデータ数で割った値になります。
これらはデータの描画を行う際にも利用するので、それぞれを View
クラスの属性として line_width
、line_height
として保持させています。
また背景をキャンバスの中央に描画するように、下記により位置調整用のオフセットを計算しています。
self.offset_x = (キャンバスの横サイズ - 背景の横サイズ) / 2
self.offset_y = (キャンバスの縦サイズ - 背景の縦サイズ) / 2
[/coxebox]
これらの値を用いて、最終的に tkinter Canvas
クラスの create_rectangle
メソッドにより背景の描画を行っています。
# 背景を描画
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"
)
データの描画
View
クラスのオブジェクトは draw_data
メソッドでリストに格納されているデータを棒グラフとして描画します。
この draw_data
メソッドは Sort
クラスからデータのソートを行う途中で随時実行され、その時点のデータの並びを描画します。
リストの全データをループ内で下記のように tkinter Canvas
クラスの create_rectangle
を実行することで、棒グラフと見立てた矩形として描画します。
# 長方形を描画
self.canvas.create_rectangle(
x1, y1,
x2, y2,
tag=tag,
fill="#FFA588",
width=1
)
第1引数と第2引数で指定する矩形の始点は start
メソッドで求めた line_width
と line_height
や offset_x
と offset_y
を用いて下記のように求めています。
i
はデータの先頭から何番目かを表すインデックス(0
〜 データ数 - 1
)、value
はそのデータの値、num
はデータ数を表しています。
x1 = int(self.offset_x + i * self.line_width)
y1 = int(self.offset_y + self.line_height * (self.num - value))
第3引数と第4引数で指定する終点も同様にして line_width
と line_height
や offset_x
と offset_y
を用いて下記のように求めています。
x2 = int(self.offset_x + (i + 1) * self.line_width)
y2 = int(self.offset_y + self.line_height * self.num)
これらの x1
、y1
、x2
、y2
を算出時に用いた line_width
・line_height
・offset_x
・offset_y
・i
・num
・value
の 関係を図で表すと下の図のようになります。
こんな感じで棒グラフとして見立てた矩形をデータ数分描画することで、その時点のデータの並びを描画しています。
また、棒グラフが重複して描画されないように、create_rectangle
に引数 tag
を指定し、その tag
で指定したタグ名を利用して描画の前に以前に描画した棒グラフの削除も行なっています。
# 一旦描画しているデータを削除
for obj in self.drawn_obj:
self.canvas.delete(obj)
drawn_obj
は各棒グラフ描画時に tag
で指定したタグ名を格納したリストになります。
スポンサーリンク
Sort
クラス
Sort
クラスは実際にソートを行うクラスです。
ソートの開始
Sort
クラスのオブジェクトは Controller
から start
メソッドが実行されると、引数 method
によって指定されたアルゴリズムに応じて実行するメソッドを決定してそのメソッドを実行します。
具体的には下記のように method
の指定に応じて実行するメソッドを決定します。
- 選択ソート(
Sort.SELECTION_SORT
):selection_sort
- クイックソート (
Sort.QUICK_SORT
):quick_sort
- マージソート(
Sort.MERGE_SORT
):quick_sort
ソート処理
selection_sort
、quick_sort
、quick_sort
では、それぞれのアルゴリズムに従ってデータのソートを行います。
各アルゴリズムの解説は下記ページで行なっていますので、詳しくは下記ページを参照していただければと思います。
選択ソートを図を使って分かりやすく解説(C言語サンプルプログラム付き) クイックソートを図を使って分かりやすく解説(C言語サンプルプログラム付き) マージソートを図を使って分かりやすく解説(C言語サンプルプログラム付き)プログラムはC言語のものになりますが、Python のソースコードに関してはソートの様子を可視化するスクリプトで示した selection_sort
、quick_sort
、quick_sort
メソッドご覧ください。
データ描画の依頼
また selection_sort
、quick_sort
、quick_sort
メソッドの中で、ソート処理が進むたびに View
クラスの draw_data
メソッドを実行し、その時点のデータの並びの画面への描画を依頼します。
データの並びが変わるたびに、その時点のデータの並びが画面に描画されますので、アニメーションにより各アルゴリズムでどのようにデータがソートされていくかの様子を確認することができます。
まとめ
このページではソートによりデータの並びが整列されていく様子を可視化する方法について解説しました。
ソートが進むたびに、その時点のデータの並びを棒グラフとして画面に描画することで、ソートが進む様子を可視化しています。
同様にナイト巡回問題のプログラムの動作を可視化するアプリの解説については下記ページで解説していますので、プログラムの動作の可視化に興味のある方はこちらも併せてお読みください。
【Python】ナイト巡回問題を解く様子を Tkinter で可視化プログラムの動作を可視化すれば、プログラムの動作確認に役立つだけでなく、プログラムの動き(アルゴリズムの動き)を実感して理解することもできます。
皆さんもいろんなプログラムの動作の可視化に挑戦してみてください!
オススメ参考書(PR)
今回紹介したスクリプトのように、ボタンや図形の描画を行う GUI アプリを作成するには tkinter がオススメです。
この tkinter の使い方を習得するための参考書としてはPythonでつくる ゲーム開発 入門講座がオススメです。
この本では主に tkinter を使用したゲームの開発を学べる参考書です。当然 tkinter について学べますし、題材がゲームなので楽しく学ぶ事もできます。
私も Python を始めた時はこの参考書で勉強しました!
ゲームだけでなく、いろんな GUI アプリを作成したい方にもオススメです!