バブルソートをすることでデータが移動していく様子を可視化するとどうなるかやってみました。
ソートするのはランダムに生成した1～500の整数です。これを横向きの棒グラフのようにして表示させます。
デザイナで以下のようなものをつくります。
コンストラクタで乱数を生成して表示させます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
public partial class Form1 : Form { int[] Data = new int[100]; public Form1() { InitializeComponent(); this.DoubleBuffered = true; label1.Text = ""; ShuffleData(); } void ShuffleData() { Random random = new Random(); for (int i = 0; i < 100; i++) Data[i] = random.Next(500) + 1; Invalidate(); label1.Text = ""; } } |
配列内に格納されている整数を横向きの棒グラフのようにして表示させます。幅3ピクセルにして添え字に幅を掛け合わせれば矩形を描画するときのY座標が決まります。矩形の幅は乱数の値をそのまま使います。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
public partial class Form1 : Form { Brush Brush = new SolidBrush(Color.Black); void DrawBar(Graphics graphics, int index, int value) { int width = 3; graphics.FillRectangle(Brush, new Rectangle(new Point(10, 10 + width * index), new Size(value, width))); } protected override void OnPaint(PaintEventArgs e) { for (int i = 0; i < 100; i++) { DrawBar(e.Graphics, i, Data[i]); } base.OnPaint(e); } } |
あとは乱数をシャッフルしてソートするときに配列の要素が入れ替わるときにInvalidateメソッドを呼び出せばそれっぽい描画ができます。
これは乱数をシャッフルするための処理です。
|
1 2 3 4 5 6 7 |
public partial class Form1 : Form { private void ButtonShuffle_Click(object sender, EventArgs e) { ShuffleData(); } } |
以下はバブルソートをするときの様子を描画するメソッドです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
public partial class Form1 : Form { async private void ButtonBubbleSort_Click(object sender, EventArgs e) { label1.Text = ""; int n = Data.Length; for (int i = 0; i < n - 1; i++) { for (int x = n - 1; x >= i + 1; x--) { if (Data[x - 1] > Data[x]) { int c = Data[x - 1]; Data[x - 1] = Data[x]; Data[x] = c; Invalidate(); } await Task.Delay(10); // 移動回数が多いので、ループごとに止める時間は0.01秒にする } } label1.Text = "終了！"; } } |
これは選択ソートの様子を描画するためのメソッドです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
public partial class Form1 : Form { async private void ButtonSelectionSort_Click(object sender, EventArgs e) { label1.Text = ""; int n = Data.Length; for (int i = 0; i < n - 1; i++) { int minIndex = i; // 最小値を探す for (int x = i + 1; x < n; x++) { if (Data[x] < Data[minIndex]) minIndex = x; } // vs[i] と vs[min_index]を交換 int c = Data[i]; Data[i] = Data[minIndex]; Data[minIndex] = c; await Task.Delay(100); Invalidate(); } label1.Text = "終了！"; } } |
これは選択ソートの様子を描画するためのメソッドです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
public partial class Form1 : Form { async private void ButtonQuickSort_Click(object sender, EventArgs e) { label1.Text = ""; await QuickSort(Data, 0, Data.Length); label1.Text = "終了！"; } async Task QuickSort(int[] vs, int left, int right) { // ソートする範囲の長さが1以下の場合は何もしない if (left + 1 >= right) return; // データ列の末尾 vs[right-1] をピボットとする int pivot = vs[right - 1]; // ピボット未満のデータを挿入する位置を保持する変数を用意 int curIindex = left; int tmp; // 数値交換用 for (int i = left; i < right - 1; i++) { if (vs[i] < pivot) { { // 入れ替える tmp = vs[curIindex]; vs[curIindex] = vs[i]; vs[i] = tmp; await Task.Delay(50); Invalidate(); } curIindex++; } } // ピボットを vs[curIindex] へ移動し、データ列を分割する { // 入れ替える tmp = vs[curIindex]; vs[curIindex] = vs[right - 1]; vs[right - 1] = tmp; await Task.Delay(50); Invalidate(); } // 分割されたデータ列に対して再帰的にクイックソートを行う await QuickSort(vs, left, curIindex); await QuickSort(vs, curIindex + 1, right); } } |
