📊

ソートアルゴリズムを可視化するGo制CLI「sortvis」を作った

2023/12/21に公開

作ったもの

ソートアルゴリズムのアニメーションをターミナルで表示するコマンドsortvisを作りました。

https://github.com/hamao0820/sortvis

sortvisを使うと、いくつかのアルゴリズムの実行中の要素の動きを可視化することできます。
アルゴリズムがどのように動いているのかをみることで、アルゴリズムの全体感が理解しやすくなると思います。

目的

ソートを可視化するYouTubeの動画を見て、自分でも作ってみたくなりました。そのようなWebアプリはいくつかあったのですが、ターミナルで遊べるものは無さそうだったので、作ることにしました。

アニメーションは以下の記事を参考にしました。

インストール

Homebrew を使用している場合は brew install を使用してインストールできます。

$ brew install hamao0820/tap/sortvis

go installを使用してインストールすることもできます。

go install github.com/hamao0820/sortvis@latest

もしくは、releaseページから直接自分の環境に合うものをダウンロードしてください。

使い方

helpは以下の通りです。

$ sortvis -h
Visualize sorting algorithms.
in interactive mode, you can step forward by pressing space.
Press q or Ctrl+C to quit

Usage:
  sortvis [flags]
  sortvis [command]

Available Commands:
  bubble      Visualize bubble sort
  bucket      Visualize bucket sort
  completion  Generate the autocompletion script for the specified shell
  heap        Visualize heap sort
  help        Help about any command
  insertion   Visualize insertion sort
  merge       Visualize merge sort
  quick       Visualize quick sort
  selection   Visualize selection sort
  shell       Visualize shell sort

Flags:
  -d, --duration int   duration of each step in milliseconds (default 300)
  -f, --file string    file path: number of lines must be 0 < n < 100, each line must be 0 <= n <= 100
  -g, --graph string   The initial value of the array is set to a certain form. Example: sin wave
                        You can check the available list with 'sortvis --graph-list'.
      --graph-list     list all graph types
  -h, --help           help for sortvis
  -i, --interactive    interactive mode
  -l, --ls             list all algorithms
  -n, --num int        number of elements (default 50)

Use "sortvis [command] --help" for more information about a command.

サブコマンド

サブコマンドは以下の通りです。

bubble: バブルソート
selection: 選択ソート
quick: クイックソート
merge: マージソート
heap: ヒープソート
bucket: バケットソート

使用可能なソートアルゴリズムおよびサブコマンドは次のフラグで確認することもできます。

$ sortvis --ls
You can use the following algorithms(subcommands):
Bubble Sort(bubble)
Merge Sort(merge)
Heap Sort(heap)
Quick Sort(quick)
Selection Sort(selection)
Bucket Sort(bucket)

オプション

--help, -h: ヘルプを表示します。
--interactive, -i: インタラクティブモードで実行します。このモードでは、ソートの過程を手動で進めることができます。スペースキーを押すと次のステップに進みます。
--num, -n: ソートする配列のサイズを指定します。デフォルトは 50 です。0 < n < 100 　である必要があります。
--delay, -d: ソートの遅延時間(ms)を指定します。デフォルトは 300 ミリ秒です。
--graph, -g: 使用する(関数の)グラフを指定します使用可能なグラフは --graph-list で確認できます。例: --graph=sin
--ls: サブコマンドの一覧を表示します。
--graph-list: 使用可能なグラフの一覧を表示します。
--file, -f: ソートする配列をファイルから読み込みます。ファイルの形式は以下の通りです。それぞれの値は[0, 100]で、行数は1以上99以下になるようにしてください。

デモ

バブルソート:

$ sortvis bubble

マージソート:

$ sortvis merge

シェルソート(sin波):

$ sortvis shell -g sin

実装

以下のパッケージを利用しました。

Cobra: コマンドやフラグの管理
termdash: グラフの表示やアニメーションの制御

ソートの制御にはchannelを使用しました。

func BubbleSortAsync(arr []int, c chan struct{}) {
	for i := 0; i < len(arr); i++ {
		for j := 0; j < len(arr)-1-i; j++ {
			if arr[j] > arr[j+1] {
				<-c
				swap(&arr[j], &arr[j+1])
			}
		}
	}
}

任意のタイミングで、

c <- struct{}{}

を呼び出すことで、ステップを進めることができます。

基本的に元の配列に変更が加わる直前で、channelによるブロックが起こるようになっています。ですので、アニメーションのステップ数と実際の計算量(ステップ数)には大きな乖離があることに注意してください。
例えば、バケットソートなどは、バケットに入れる処理等はアニメーションにおいては全てスキップされるので、いきなり小さい順に並ぶように見えます。今後は、注目している要素に色をつけたりして、実際のステップ数でアニメーションされるような機能もつけたいです。

リリース

リリースはGoReleaserを使用しました。ほぼ以下の記事のままです。

まとめ

展望としては、参考にした記事のように、実際に注目している要素に色をつけたりして、アルゴリズムがどのように動いているのかを確認できるようにしたいです。

まだソートの数が少ないので、色々追加していきたいです。追加して欲しいものや面白いソートアルゴリズムがあれば、コメントで教えていただけるとありがたいです。
Golang自体も見様見真似で書いているので、こういう書き方の方が良いなどもあれば、ぜひご指導ください。