ソートのアルゴリズムを可視化するというプログラムを紹介され、自分たちでもつくってみてね
といわれたので,さっそく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すると
とこのようになります、半分ずつ処理されている様子が見れますね。
次に、シェルソート
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.
となっています。こちらも可視化すると
このように段階的にソートされているようすが見られます。
このようにアルゴリズムを可視化すると、具体的にどのように動作しているのか
目で確認することができて便利ですね。
