【Python】ソートが行われていく様子を Tkinter で可視化

今回は 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 のクラスのオブジェクトを生成することで実現できます。さらにこれらのオブジェクトに gridpack メソッドを実行させることで、ウィジェットの配置を行なっています。

詳細はサンプルスクリプトの 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_widthline_height として保持させています。

また背景をキャンバスの中央に描画するように、下記により位置調整用のオフセットを計算しています。

中央寄せのための調整値
self.offset_x = (キャンバスの横サイズ - 背景の横サイズ) / 2
self.offset_y = (キャンバスの縦サイズ - 背景の縦サイズ) / 2
[/coxebox]

これらの値を用いて、最終的に tkinter Canvas クラスの create_rectangle メソッドにより背景の描画を行っています。

[codebox title="背景の描画"]
# 背景を描画
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_xoffset_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_xoffset_y を用いて下記のように求めています。

矩形の終点
x2 = int(self.offset_x + (i + 1) * self.line_width)
y2 = int(self.offset_y + self.line_height * self.num)

これらの x1y1x2y2 を算出時に用いた line_widthline_heightoffset_xoffset_yinumvalue の 関係を図で表すと下の図のようになります。

棒グラフ描画時の各パラーメータの関係

こんな感じで棒グラフとして見立てた矩形をデータ数分描画することで、その時点のデータの並びを描画しています。

また、棒グラフが重複して描画されないように、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_sortquick_sortquick_sort では、それぞれのアルゴリズムに従ってデータのソートを行います。

各アルゴリズムの解説は下記ページで行なっていますので、詳しくは下記ページを参照していただければと思います。

選択ソート解説ページのアイキャッチ選択ソートを図を使って分かりやすく解説(C言語サンプルプログラム付き) クイックソート解説ページのアイキャッチクイックソートを図を使って分かりやすく解説(C言語サンプルプログラム付き) マージソート解説ページのアイキャッチマージソートを図を使って分かりやすく解説(C言語サンプルプログラム付き)

プログラムはC言語のものになりますが、Python のソースコードに関してはソートの様子を可視化するスクリプトで示した selection_sortquick_sortquick_sort メソッドご覧ください。

データ描画の依頼

また selection_sortquick_sortquick_sort メソッドの中で、ソート処理が進むたびに View クラスの draw_data メソッドを実行し、その時点のデータの並びの画面への描画を依頼します。

データの並びが変わるたびに、その時点のデータの並びが画面に描画されますので、アニメーションにより各アルゴリズムでどのようにデータがソートされていくかの様子を確認することができます。

まとめ

このページではソートによりデータの並びが整列されていく様子を可視化する方法について解説しました。

ソートが進むたびに、その時点のデータの並びを棒グラフとして画面に描画することで、ソートが進む様子を可視化しています。

同様にナイト巡回問題のプログラムの動作を可視化するアプリの解説については下記ページで解説していますので、プログラムの動作の可視化に興味のある方はこちらも併せてお読みください。

【Python】ナイト巡回問題を解く様子を Tkinter で可視化

プログラムの動作を可視化すれば、プログラムの動作確認に役立つだけでなく、プログラムの動き(アルゴリズムの動き)を実感して理解することもできます。

皆さんもいろんなプログラムの動作の可視化に挑戦してみてください!

オススメ参考書

今回紹介したスクリプトのように、ボタンや図形の描画を行う GUI アプリを作成するには tkinter がオススメです。

この tkinter の使い方を習得するための参考書としてはPythonでつくる ゲーム開発 入門講座がオススメです。

この本では主に tkinter を使用したゲームの開発を学べる参考書です。当然 tkinter について学べますし、題材がゲームなので楽しく学ぶ事もできます

私も Python を始めた時はこの参考書で勉強しました!

ゲームだけでなく、いろんな GUI アプリを作成したい方にもオススメです!

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です