はじめに
初めてQiitaに投稿する上、ブログとか全然やったことがないので至らない部分があると思いますがご了承願います。なにか変だったらコメントで教えていただけると嬉しいです。
なぜC#.NETで作るんだとすでにお気付きでしょうが、C#.NETでつくります。私がC#.NETが好きだからです。
また、勉強途中なので技術力は全然ありません。すごいパフォーマンスの悪いものだと思います。(そもそも可視化にC#.NETを使うものじゃない）
(2/16/19追記)ちなみにこちらの記事の続き C#.NET Frameworkでソートアルゴリズムの可視化をした話２ も書いたのでこちらもよかったら見てください。
(2/21/19追記)さらに新作DXライブラリでソートアルゴリズムの可視化をした話 も書いたのでこちらもよかったら見てください。
作ろうと思った動機
今私がこうして記事を書いてるのが2019年の2月ですが、4月にIPAの応用情報技術者試験のプログラミングの分野を選ぶので勉強がてらにソートアルゴリズムを目に見える形で学習したいので作りました。
今回実装したソートアルゴリズム
今回学習目的で実装したアルゴリズムは以下です。各アルゴリズムの詳しい説明はggってください...
・バブルソート
・シェーカーソート
・挿入ソート
・マージソート(Out-of-place)
・クイックソート
・基数ソート(Radix sort)
画面
四角形オブジェクトはSystem.Windows.Shapes.Rectangleを使ってStackPanelにChildren.Addする方式をとりました。
値を変えたい四角形を取得してプロパティを変更...みたいな感じで可視化しました。
ソースコード(マージソート)
応用情報技術者試験の平成26年秋期 午後問3にマージソートがあったのでマージソートだけおいておきます。
static int ARR_SIZE = 200;
int[] buf;
async void mergesort(int num)
{
sort_initialize(); //ソート前処理
buf = new int[ARR_SIZE]; //バッファ
Rectangle current; //System.Windows.Shapes
int rght, rend;
int i, j, m;
for (int k = 1; k < num; k *= 2)
{
for (int left = 0; left + k < num; left += k * 2)
{
rght = left + k;
rend = rght + k;
if (rend > num)
{
rend = num;
}
m = left;
i = left;
j = rght;
while (i < rght && j < rend)
{
add_array_access(); //配列へのアクセス回数をカウントするメソッド
add_array_access();
add_comparison(); //こっちは比較回数をカウントするメソッド
if (array[i] <= array[j])
{
current = FindNameRect_nolonger(i); //i番目のRectangleへの参照を返すメソッド
mark_red(current); //取得したRectangleを赤色に染める
add_array_access();
buf[m] = array[i]; i++;
await Task.Delay(10); //10ms待機する
}
else
{
current = FindNameRect_nolonger(j);
mark_red(current);
add_array_access();
buf[m] = array[j]; j++;
await Task.Delay(10);
}
m++;
}
while (i < rght)
{
current = FindNameRect_nolonger(i);
mark_red(current);
add_array_access();
buf[m] = array[i];
await Task.Delay(10);
i++; m++;
}
while (j < rend)
{
current = FindNameRect_nolonger(j);
mark_red(current);
add_array_access();
buf[m] = array[j];
await Task.Delay(10);
j++; m++;
}
for (m = left; m < rend; m++)
{
current = FindNameRect_nolonger(m);
mark_blue(current);
add_array_access();
array[m] = buf[m];
current.Height = buf[m];
current.Margin = new Thickness(0, 447 - buf[m], 0, 0);
await Task.Delay(10);
}
}
}
success(); //成功のメソッド
}
スクショ
クイックソート
マージソート
やってみて
ソートアルゴリズムを実装するのはかなり面白くていい経験になりました。応用情報技術者試験でソートアルゴリズムが出題されるかは微妙なところですが動作しているところをみて面白かったので大満足です。
この後楽しくなってPythonのライブラリPygameとVC++のDXライブラリでもソートアルゴリズムを可視化したのはまた別の話。
参考
Non-Recursive Merge Sort - Stack OverFlow
超クールなソートアルゴリズム可視化動画↓
15 Sorting Algorithms in 6 Minutes - Youtube