Edited at

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

More than 1 year has passed since last update.

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