LoginSignup
3
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@TackKaiware

ソートアルゴリズムを可視化する（コンソールアプリの作成）

Last updated at Posted at 2020-10-22

0. まえがき

Youtubeで"sort algorithms visualized"などと検索すると、
ソートの様子を描いた綺麗なアニメーション動画がヒットします。
今回は、それを真似てコンソールでソートの様子が見えるプログラムを作りたいと思います。
言語はC#ですが、固有の機能（WPFでデータバインドが～とか）は使用せず、
枠組みからムニムニ作りますのでオブジェクト指向型言語であれば同じように作れるかと思います。

端的には、コンソールで動くこれ（↓）を作ります（バブルソートしてますね）
SortAnimation.gif

1. 開発環境

OS
Windows 10 Home
IDE
Visual Studio 2019 Community
言語
C# 7.0以上 (System.ValueTapleが使えるやつ)

2. 設計（雑）

ソート処理にて要素の交換が発生した時、その時点の配列の内容を画面に表示、
また要素の交換が発生したら画面をクリアして再び配列の内容を表示・・・。
という処理をソート完了まで繰り返していけば上にあるようなアニメが出来そうです。

・・・こう書いてみると、ソートアルゴリズムの中に画面表示の処理を組み込んだら
それで一発完成しそうな雰囲気ですが、折角なのでオブジェクト指向の考え方で作っていきたいと思います。
（何が折角なのかは不明）

2.1. Observerパターンを検討してみる

2.1.1 そもそも👆ってなに？

これっす👇
https://ja.wikipedia.org/wiki/Observer_%E3%83%91%E3%82%BF%E3%83%BC%E3%83%B3
またはQiitaで検索検索ゥ！！諸先輩方の大変分かりやすい記事がヒットしますヨ。

2.1.2 パターンに当てはめてみる

上のリンク内の説明に従うと、
ソートする人　→　通知する側（配列内容を交換する度にその状態をお知らせ）
画面表示する人 →　通知を受ける側（お知らせ内容に従い画面表示）
と置けそうです。

2.2 クラス図に起こしてみる

左側のIObserver、SortObserverが通知を受ける側、
右側のObservable、SortObjectが通知する側になります。
また図上部が根幹の仕掛けとなる枠組み（フレームワーク部）で、
図下部が具体的な処理を書く部分（アプリケーション部）になります。
フレームワーク部から順次作っていきます。各クラスの説明は次章にて♨

SortVisualizer.png

3. 実装

3.0 前準備

画面表示用のメソッドを作成する
Observerパターンとは直接関係ないので切り離してここに記載しました。
アニメーションでの一コマ相当を画面に表示する静的クラス＆メソッドです。
一旦画面をクリアしてから描きたいものを表示、それからちょっとタイム。
以降も呼び出される度にクリア→表示→タイムでアニメの再現・・・ってとこです。
タイムを設けているのは、これが無いと目視不可能な程の爆速でアニメが終了し
ﾎﾟｶｰﾝ(　ﾟдﾟ)となってしまうからです。

Animator.cs
using System;
using System.Threading;

namespace SortVisualizerCUI {

    /// <summary>
    /// コンソールに対しアニメ表示を行う人
    /// </summary>
    public static class Animator {
        private const int WaitTime_ms = 100;    // 画面の表示更新の間隔[ms]

        /// <summary>
        /// アニメでいうところの一コマ分を表示する
        /// </summary>
        public static void DisplaySingleFrame( string value ) {
            Console.Clear();
            Console.WriteLine( value );
            Thread.Sleep( WaitTime_ms );
        }
    }
}

3.1 枠組みを作る（フレームワーク部の作成）

3.1.1 Observableクラス（通知する側）

通知する側が備えておくべき機能を持たせた抽象クラスです。
ここから具象クラスをﾆｮｷﾆｮｷ派生させてそこへやりたい処理を書きます。
通知先オブジェクトへの参照をリスト(observers)で複数持っているのは、
例えばGUIなら複数のコントロールに一斉に状態変更を知らせたい時があるためです。
今回は通知する相手が一人なので死に機能なんですけどね。
細けぇこたぁ(ryソースコード中のコメントをご参照くださいませ。m(__)m

Observable.cs
using System.Collections.Generic;

namespace SortVisualizerLibrary {

    /// <summary>
    /// 通知する側の抽象クラス
    /// </summary>
    public abstract class Observable {

        /// <summary>
        /// 通知先オブジェクトへの参照
        /// </summary>
        private readonly List<IObserver> observers = new();

        /// <summary>
        /// 通知先オブジェクトを追加する
        /// </summary>
        /// <param name="observer"></param>
        public void AddObserver( IObserver observer ) => observers.Add( observer );

        /// <summary>
        /// 通知先オブジェクトを削除する
        /// </summary>
        /// <param name="observer"></param>
        public void RemoveObserver( IObserver observer ) => observers.Remove( observer );

        /// <summary>
        /// 通知先オブジェクトへ自身の状態変更を知らせる
        /// </summary>
        protected void NotifyObservers() => observers.ForEach( observer => observer?.Update( this ) );
    }
}

3.1.2 IObserverインターフェース（通知を受ける側）

インターフェースの定義なのでこれだけです。

IObserver.cs
namespace SortVisualizerLibrary {

    /// <summary>
    /// 監視する側のインターフェース定義
    /// </summary>
    public interface IObserver {

        /// <summary>
        ///  通知してくるオブジェクトから状態変更通知を受けた時の更新処理
        /// </summary>
        /// <param name="observable"></param>
        void Update( Observable observable );
    }
}

3.2 具体的な処理を書く（アプリケーション部の作成）

3.2.1 SortObject（通知する側：抽象）

具体的な処理を書くということで、上のObservableクラス（抽象）から
直接バブルソートにあたるクラス（具象）を派生させてもよかったのですが、
例えばXXXソートを増やしたい場合、同じ処理を何度も書くのはダルいので
共通化出来るプロパティ・メソッドを抽出しここに抽象クラスとしてまとめました。
これにて通知する側は三段階派生することになりました。

Observableクラス（抽象）
　　↓
SortObjectクラス（抽象）←今ココ
　　↓
XXXSortクラス（具象）

ソースコードです。例により細けぇこたぁ(ryコメントで書いていますが、
肝はItemsプロパティのSetにてNotifyObservers()を呼んでいる箇所で、
これが自分自身の状態変更を知らせる＝通知を受け取る側に仕事をさせるトリガーです。
NotifyObservers()内で登録している全IObserverにUpdate()の指示を出しています。

SortObject.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

namespace SortVisualizerLibrary {

    /// <summary>
    /// ソートオブジェクトクラス（抽象）
    /// </summary>
    public abstract class SortObject<T> :Observable where T : IComparable<T> {
        protected const int DelayTime_ms = 0;

        private T[] items = Array.Empty<T>();

        /// <summary>
        /// 比較回数
        /// </summary>
        public int CompareCount { get; private set; }

        /// <summary>
        /// 交換回数
        /// </summary>
        public int SwapCount { get; private set; }

        /// <summary>
        /// ソートアルゴリズムの名称
        /// </summary>
        public abstract string Name { get; }

        /// <summary>
        /// ソート対象のデータ
        ///  Setされるたびに更新した内容を通知を受ける側へ知らせる。
        /// </summary>
        public IReadOnlyCollection<T> Items {
            get => items;
            private set {
                if ( !value.SequenceEqual( items ) ) {
                    items = value.ToArray();
                    NotifyObservers(); // ★ココ！で通知を受ける側へ状態変更を知らせる
                    Thread.Sleep( DelayTime_ms );
                }
            }
        }

        /// <summary>
        /// ソートの実行（公開）
        /// </summary>
        public void Execute( IEnumerable<T> items ) {
            Items = items.ToArray();
            CompareCount = 0;
            SwapCount = 0;
            ExecuteSort( items );
        }

        /// <summary>
        /// ソートの実行（非公開）
        /// 派生先クラスで各アルゴリズムの実装を強制させるため抽象メソッドとしている。
        /// ソートの状態変更を通知するため、要素の比較・交換はこのクラスの Compare()、Swap() を用いること。
        /// </summary>
        protected abstract void ExecuteSort( IEnumerable<T> items );

        /// <summary>
        /// 要素の比較。
        /// 比較回数をカウントアップし、通知を受ける側へ状態変更を知らせる。
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        protected int Compare( T a, T b ) {
            CompareCount++;
            NotifyObservers();
            return a.CompareTo( b );
        }

        /// <summary>
        /// 要素の交換。
        /// 交換回数をカウントアップし、通知を受ける側へ状態変更を知らせる。
        /// </summary>
        /// <param name="array"></param>s
        /// <param name="indexA"></param>
        /// <param name="indexB"></param>
        protected void Swap( ref T[] array, int indexA, int indexB ) {
            (array[indexA], array[indexB]) = (array[indexB], array[indexA]);
            SwapCount++;
            Items = array;
        }
    }
}

3.2.2 BubbleSort（通知する側：具象）

これが最終派生クラスになります。通知する仕組みは派生元に定義済みなので、
あとはExecuteSort()メソッド内にバブルソートのアルゴリズムを書くだけでおｋ。
Swap()メソッド内でItemプロパティを更新することにより、
交換直後の配列の状態を通知を受け取る側へ通知しています。

BubbleSort.cs
using System;
using System.Collections.Generic;
using System.Linq;

namespace SortVisualizerLibrary {

    /// <summary>
    ///  バブルソート
    /// </summary>
    public class BubbleSort<T> :SortObject<T> where T : IComparable<T> {
        public override string Name => "バブルソート";

        /// <summary>
        /// ソートの実行
        /// </summary>
        /// <param name="items"></param>
        protected override void ExecuteSort( IEnumerable<T> items ) {
            var array = items.ToArray();
            for ( int i = 0; i < array.Length - 1; i++ ) {
                for ( int j = array.Length - 1; i < j; j-- ) {
                    if ( Compare( array[j], array[j - 1] ) < 0 ) {
                        Swap( ref array, j, j - 1 );
                    }
                }
            }
        }
    }
}

3.2.3 SortObserverクラス（通知を受ける側）

上のBubbleSortから間接的にUpdate()をぶっ叩かれて
画面表示をするクラスです。
これ自体は大したことをしていないので、通知側する側からの処理の流れをまとめると、

  1. BubbleSortのSwap()内でItemプロパティを更新。
  2. ItemプロパティのSet内でNotifyObservers()が呼ばれる。
  3. NotifyObservers()内から通知を受ける側のUpdate()を呼ぶ。
  4. 通知を受ける側のUpdate()内で交換済みの配列を画面表示する。（今回は各配列要素の値を棒グラフ状に変換）

…とこんな感じです。各メソッドの定義が色んなファイルに散っているので
パッと見で処理を追いづらいですね。。。

SortObserver.cs
using SortVisualizerLibrary;

using System;
using System.Linq;

namespace SortVisualizerCUI {

    /// <summary>
    /// ソート状態を監視するクラス
    /// </summary>
    public class SortObserver :IObserver {
        private int[] items = null;

        /// <summary>
        /// ソートオブジェクト（通知してくる側）に、自分自身を登録する
        /// </summary>
        public void SetDataSource( SortObject<int> value ) => value.AddObserver( this );

        /// <summary>
        /// ソートオブジェクトから状態変更の通知を受け取った時の処理
        /// </summary>
        /// <param name="observable"></param>
        public void Update( Observable observable ) {
            // ソートオブジェクトではない
            if ( observable is not SortObject<int> ) {
                return; // 画面は更新しない
            }

            // 配列の並びに変更がない
            var sortObject = observable as SortObject<int>;
            items ??= new int[sortObject.Items.Count];
            if ( items.SequenceEqual( sortObject.Items ) ) {
                return; // 画面は更新しない
            }

            // 数値の大小を横棒グラフで表す文字列に変換する
            var str = string.Join(
                string.Empty,
                sortObject.Items.SelectMany( n =>
                    Enumerable.Repeat( "■", n ).Append( Environment.NewLine ) ) );

            // アニメの一コマ分として画面に表示する
            Animator.DisplaySingleFrame( str );
            items = sortObject.Items.ToArray();
        }
    }
}

3.3 呼び出し側を作って完成

複雑な仕掛けは各クラスの裏側に隠れているので、呼び出し側はこんなあっさり風味です。
今回は直接オブジェクトをnew()!!して生成していますが、
通知を受ける側sortObserverのSetDataSource()に通知する側sortObjを設定し忘れると、
「何も動かねぇ・・・」状態になるので、一連の生成処理をファクトリメソッドにまとめても良いかもしれません。

Program.cs
using SortVisualizerLibrary;

using System;
using System.Linq;

namespace SortVisualizerCUI {

    internal static class Program {

        private static void Main() {
            // 監視対象のオブジェクトを生成
            var sortObj = new BubbleSort<int>();

            // 監視するオブジェクトを生成
            var sortObserver = new SortObserver();

            // 監視するオブジェクトに監視対象のオブジェクトを設定
            sortObserver.SetDataSource( sortObj );

            // ソート対象のデータを生成
            var values = Enumerable.Range( 1, 20 ).OrderBy( x => Guid.NewGuid() ).ToArray();

            // ソートを実行
            sortObj.Execute( values );
        }
    }
}

4. 動作確認

「Ctrl」+「F5」で実行すると、冒頭でお見せしたバブルソートのアニメーションが
コンソールに表示されるハズです。
・・・が、けっこうチラつきます。調べたところConsole.ほにゃらら()を駆使すれば
回避出来るっぽいのですが、今回はこれで許し亭♨

GitHubにプロジェクトを丸ごと置きました。もしよければ弄ってやって下さい。
[SortVisualizer] (https://github.com/TackKaiware/SortVisualizer)

5. プラスα

〇〇〇ソートを追加する
SortObjectクラスから派生させた先でソートのアルゴリズムを書くだけで
容易に追加が出来そうです。

GUIアプリとして作る
コンソール表示からフォームへの表示になるため、通知を受け取る側は
ゴミ箱逝き不可避ですが、通知する側は再利用できそうです。
もっとも、C#には変更通知の機能が備わっているためそちらを使うのが正道でしょうが。。。

6. あとがき

記事が無駄に長くなってしまった感が。
今回はぷちプログラムのためやってる内容に対して
ソース全体が大げさになってしまいましたが、
ある程度の規模以上になるとオブジェクト指向の良さが表れてくると思いました。

小生は、実務経験はほぼほぼ素のC言語でやってきたので、
オブジェクト指向の考え方、実装としておかしい点、説明不足などあれば
ご指摘・アドバイス頂けると大変うれしく存じます。

それでは、アディオス！！

7. 更新履歴

2021/10/31
・文章からフザけた箇所を削除
・文章からウザイ絵文字を削除
・ソースコードを修正（.NET5で作り直し、その他修正）

3
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?