Vim (その2) Advent Calendar 2016 20日の記事です。
Vim Scriptでバブルソート、クイックソート、マージソート、挿入ソートを可視化してみました。
(Vim Script 初心者なので至らぬ点が多々あると思われます。予めご了承ください。)
ソースコードはGitHubにあります。
動作の様子
- bubble sort
- merge sort
- insert sort
- quick sort
解説
入力データを作る
シェルコマンドでやろうとしたけれどうまく行かなかったので、perlを使ってズルをします。(無駄が多い気がしますが、気にしない。)
seq 1 40 | xargs -I{} perl -e 'print int(rand(1000)) . "\t" . "*"x{}; print "\n"'|sort|sed -e 's/^.*\t\(\**\)$/\1/'>input.txt
すると以下のようなランダム出力が得られます。
[input.txt]
****************
******************
**************************
***************************************
*******************************
*****************
*
( ... 略 ... )
***********
********************************
**************
これを、以下のように(行ごとの文字列の長さで)ソートするのがスクリプトの目的です。
[output.txt]
*
**
***
****
*****
******
*******
********
*********
**********
( ... 略 ... )
**********************************
***********************************
************************************
*************************************
**************************************
***************************************
****************************************
アニメーションでの表示
このスクリプトでは、行からの読み込み/行への書き込み(マージソートでは行の挿入および削除)を行うたびに行を反転表示させ、10ミリ秒待機することでアニメーション表示を行っています。そのために使っているコードを以下に示します。
function! Getval(line)
call cursor(a:line, 1)
normal! V
let val = getline(".")
redraw
sleep 10ms
return val
endfunction
function! Setval(line, val)
call cursor(a:line, 1)
normal! V
call setline(".", a:val)
redraw
sleep 10ms
endfunction
すなわち、カーソルを移動した後、を送信し、:redrawを行い、:sleep 10msを行っています。
時間計測機能
これはほとんどオマケ機能ですが、一応アルゴリズムの実行時間を計測できます。
以下のように実装されています。
let stime = reltime()
call Quicksort(1, line("."))
echomsg reltimestr(reltime(stime))
ソート完了後、:mesとすると計測した時間を表示できます。
ちなみに、手元の環境では以下のようになりました。(入力データは毎回ランダムに与えています)
| 種類 | 時間[s] |
|---|---|
| bubble | 27.260499 |
| merge | 5.799719 |
| insert | 11.273425 |
| quick | 5.781766 |
このプログラムはあくまで観賞用なので、実行時間を測ることにあまり意味を見いだせないのですが、まあ何かの役には立つのでしょう。
さいごに
Vim Script はアルゴリズムを可視化するのにも便利だと思います。