はじめに
前回(C#.NET Frameworkでソートアルゴリズムの可視化をした話)ではあまり詳しく話をしなかったので今回はもうちょっと詳しく話をしたいと思います。
前回同様、C#.NETでやります。大好きだからです。ちなみにWPFです。パフォーマンスが悪いのは変わらないです。
クイックソートとかマージソートとかは再帰を用いたコードを書くことが多いですが実装したものは全て非再帰コードです。（再帰だとどうもうまく動かなかった）
作ろうと思ったきっかけは、IPAの応用情報技術者試験もありますがこちらの動画の存在も大きいです。超クールですよ...
実装済みのソートアルゴリズム
こちらも前回同様、各アルゴリズムの詳しい説明はggってください...
・バブルソート
・シェーカーソート
・挿入ソート
・マージソート(Out-of-place)
・クイックソート
・基数ソート(Radix sort)
画面
こちらはちょっと改良しまして、RectangleのStrokeThicknessを0にしてRectangleを見やすくしました。
ソースコードたち
初期化
各RectangleのHeightの値はランダムです。そのランダムにするコードがこちら。
using System;
using System.Windows;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Shapes;
namespace sorter
{
/// <summary>
/// MainWindow.xaml の相互作用ロジック
/// </summary>
public partial class MainWindow : Window
{
public MainWindow()
{
InitializeComponent();
}
//色を定義しておく
SolidColorBrush green = new SolidColorBrush(Color.FromRgb(0, 255, 0));
SolidColorBrush red = new SolidColorBrush(Color.FromRgb(255, 0, 0));
SolidColorBrush blue = new SolidColorBrush(Color.FromRgb(0, 0, 255));
SolidColorBrush white = new SolidColorBrush(Color.FromRgb(255, 255, 255));
SolidColorBrush yellow = new SolidColorBrush(Color.FromRgb(255, 255, 0));
int[] array,karray;
static int ARR_SIZE = 200;
void initialize()
{
array = new int[ARR_SIZE];
karray = new int[ARR_SIZE];
Random rd = new Random();
int temp;
for (int i = 0; i < ARR_SIZE; i++)
{
temp = rd.Next(1, 500);//1~500の間でランダム
//重複排除（同じ値は入れない）
for(int k = 0; k<ARR_SIZE;k++)
{
try
{
if (karray[k] == temp)
{
temp = rd.Next(1, 500);
k = 0;
}
}
catch(Exception)
{
ms_er(k.ToString());
}
}
array[i] = temp;
karray[i] = array[i];
}
int j = 0;
foreach(Rectangle current in sp.Children)//StackPanelから一つずつ要素を取り出す
{
if (current == null)
{
ms_er("Error occurred while initializing canvas height.");
Application.Current.Shutdown();
return;
}
else
{
try
{
current.Height = array[j];
current.Margin = new Thickness(0, 447 - array[j], 0, 0);
current.Fill = white;
}
catch (Exception) { }
}
j++;
}
}
}
}
一番簡単なバブルソートのソース
バブルソートでどのようにRectangleを動かしているか説明したいと思います。
バブルソートはとても簡単なのでどのようなものか知っていると思います。
async void Bubble_Sort()
{
sort_initialize();//ソート前処理
int i, j, temp;
for (i = 0; i < (ARR_SIZE - 1); i++)
{
for (j = (ARR_SIZE - 1); j > i; j--)
{
add_array_access(); //アレイアクセスの回数をカウントしていくメソッド
add_array_access();
add_comparison(); //比較回数カウント
//スワップ処理
if (array[j - 1] > array[j])
{
await swap(array, j, j - 1);
}
}
}
success();//ソート終了!
}
各メソッド
sort_initialize()
ソート前に各値とRectangleの色を初期化します。
int sort_initialize()
{
comparison = 0;
array_access = 0;
comp_tex.Content = "0"; //比較回数のLabel.Contentを0にする
access_tex.Content = "0";//アレイアクセスのLabel.Contentを0にする
foreach (Rectangle r in sp.Children)//StackPanelの中の要素を一つずつ取り出す
{
r.Fill = white;//すべてwhiteにする
}
return 0;
}
add_comparison()とadd_array_access()
これらはただ単に比較回数とアレイアクセス回数を表示するメソッドです。
int add_comparison()
{
comparison++;
comp_tex.Content = comparison.ToString();
return 0;
}
int add_array_access()
{
array_access++;
access_tex.Content = array_access.ToString();
return 0;
}
swap(int[] array, int from, int to)
array[from]とarray[to]を交換します。
async Task<int> swap(int[] arr,int from, int to)
{
Rectangle current, current2;
add_array_access();
int temp = arr[from];
current = FindNameRect_nolonger(from);
current2 = FindNameRect_nolonger(to);
current.Height = current2.Height;
current.Margin = new Thickness(0, 447 - current2.Height, 0, 0); //447は高さ合わせ
current2.Height = arr[from];
current2.Margin = new Thickness(0, 447 - arr[from], 0, 0);
mark_red(current);
mark_red(current2);
await Task.Delay(10); //10ms待機する
add_array_access();
add_array_access();
arr[from] = arr[to];
add_array_access();
arr[to] = temp;
return 0;
}
FindNameRect_nolonger(int index)
StackPanelのi番目の要素Rectangleへの参照を返します。
Rectangle FindNameRect_nolonger(int index)
{
Rectangle r = null;
int cindex = 0;
foreach (Rectangle rr in sp.Children)
{
if (cindex == index)
{
r = rr;
break;
}
cindex++;
}
return r;
}
動作例
かなり遅いです。await Task.Delayしてるからですが。
クイックソート
マージソート(Out-of-place)
基数ソート
さいごに
可視化するならin-placeなソートのほうが見ていて楽しいですね。今度はDXライブラリで書いてみようと思います。
ちなみにDXライブラリでの動作例（バブルソート）もこっそり置いておきます。（今度はDXライブラリでのソートの記事を書くかも）
!!GIF画像の点滅にご注意ください!!
最後までみてくれてありがとうございました。なにか変なところとかありましたらコメントで教えてください。