Vimscriptでヴィジュアル系ソートアルゴリズムを実装してみた

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 はアルゴリズムを可視化するのにも便利だと思います。