Let's write β

プログラミング中にできたことか、思ったこととか

ソートアルゴリズムの可視化をしました。

ソートのアルゴリズムを可視化するというプログラムを紹介され、自分たちでもつくってみてね
といわれたので,さっそくSmalltalkで作成してみました。

クラスを大別して、ソートのログをOrderedCollectionで渡すとImageをつくる機能をもつ
SortVisualizerと、OrderedCollectionをソートしそのログを返す機能をもつSorterの二つに
基本のクラスを分けました。
まずはSortVisualizer>>createLogImage

createLogImage

	| image |
	image := Image
				extent: self log size @ 128
				depth: 32
				palette: self class colorPalette.
	image pixelsDo: 
			[:x :y |
			| logVal |
			logVal := (self log at: x + 1) at: y + 1.

			image atPoint: x @ y
				put: (image palette
						indexOfPaintNearest: (ColorValue
								red: 0.0
								green: 1 - (logVal / 128.0)
								blue: 0.0))].
	^image

インスタンス変数としてlogをもっていて、これは単純なOrderedCollectionに遅延初期化するようにしています。

次にSorterこちらはアルゴリズムにあわせてsubclassをつくるようにしたので、

sortLog
	^ self subclassResponsibility.

とサブクラスで実装するようなメッセージと、sequence,logというインスタンス変数をもっています。

たとえばQuickSortですと。QuickSorterに

sortLog
	self quickSort: 1 to: self sequence size.
	^self log.

となっており、プライベートメッセージに

quickSort: l to: r

	| m i j |
	l < r
		ifTrue: 
			["次にインデックスを決める"
			m := self sequence at: (l + r) // 2.
			i := l.
			j := r.
			[i > j] whileFalse: 
					[[(self sequence at: i) < m] whileTrue: [i := i + 1].
					[(self sequence at: j) > m] whileTrue: [j := j - 1].
					i <= j
						ifTrue: 
							[| tmp |
							tmp := self sequence at: i.
							self sequence at: i put: (self sequence at: j).
							self sequence at: j put: tmp.
							self log add: self sequence copy.
							i := i + 1.
							j := j - 1]].
			self quickSort: l to: j.
			self quickSort: i to: r]

というメッセージをもっています。
そして

| qs sv |
qs := QuickSorter new.
sv := SortVisualizer new.
sv log: qs sortLog.
sv createLogImage.

というようWorkspaceでInspectItすると
f:id:Pocket7878_dev:20121214155311p:plain
とこのようになります、半分ずつ処理されている様子が見れますね。
次に、シェルソート

sortLog
	| h |
	h := 1.
	[h < self sequence size] whileTrue: [
		h := 3 * h + 1.
	].

	[h > 1] whileTrue: [
		h := h // 3.

		h + 1 to: self sequence size do: [:i |
			
			| w j |
			self log add: (self sequence copy).
			w := self sequence at: i.
			j := i -h.
			[j > 0 and: [w < (self sequence at: j)]] whileTrue: [
				self sequence at: (j + h) put: (self sequence at: j).
				j := j - h.
			].
			self sequence at: (j + h) put: w.
		].
	].
	^self log.

となっています。こちらも可視化すると
f:id:Pocket7878_dev:20121214155714p:plain
このように段階的にソートされているようすが見られます。
このようにアルゴリズムを可視化すると、具体的にどのように動作しているのか
目で確認することができて便利ですね。

僕が働いているAzit.incでは一緒に働けるエンジニアを募集しています!
採用情報 — 株式会社アジット|Azit Inc.