この記事で扱っていること
- ジョークソートを実装する方法
を紹介しています。
注意：すべてのエラーを確認しているわけではないので、記事の内容を実装する際には自己責任でお願いします。また、エラー配線は適当な部分があるので適宜修正してください。
ソートとは、対象となるデータ群の中の要素をあるルール（一般的には昇順、あるいは降順）に並べる操作です。
ただしそのやり方にはいくつかあり、アルゴリズムによってどれが最も早く目的を達成できるかが違います。
さらに、重複要素があった場合にその前後関係を保つ、いわゆる安定ソートであるかどうかという観点もあります。
これらいくつかのソートアルゴリズムの実装方法については以前別の記事で紹介しました。
しかし、今回扱うのははっきり言って実用性のない「ジョークソート」です。
最終的な結果はある意味ソートされていると言えなくないのですが、色々な意味で実用性がないものばかりです。
なぜこれらを扱うのか？それは、LabVIEWにおいて、ジョークでもなんでも、自分が作りたい（表現したい）処理をどう実装するかという練習になるからです。
皆さんも、それぞれのソートが何を行うかの結果を見て、それを自分ならどう実現するか、ということを考えながら見てもらうと、ただ単に「ふーんそんなものもあるのね」というだけでなく、LabVIEWへの習熟度も上がると思うのでぜひチャレンジしてみてください。
今回扱うソート
では今回扱うソートでの並べ方のルールと、LabVIEWで実装した場合の結果例を紹介していきます。
なお、最終的には要素を昇順にすることを目指します。
それぞれのルールに従った処理をLabVIEWでどう実装するか、一例を記事後半で紹介していますが、実装の仕方は一つではないと思うので、皆さんも考えてみてください。
ボゴソート
フロントパネルには、ソート前の要素の並びおよび、ソート途中あるいはソート後の様子を示すグラフを用意しています。
グラフに表す際には、デフォルトの設定、つまり点を線で結んだ表示だとわかりにくいので、適宜プロットの様子を変えています。
例えば、ボゴソートでは、以下の図で示しているような棒プロットの少し太いのがわかりやすいのでこれを選択しています（後で紹介する他のソートも適宜プロットのやり方を変えてみてください）
これは、ソート前の状態、つまり要素がランダムに配置されている状態で、そこからランダムにシャッフルを行います。
シャッフルをしたら、それが昇順になっているかを確認します。
もし昇順になっていたら終了、なっていなかったら再びシャッフルをして、昇順になるまでこれを繰り返します。
運が良ければ1発でソートが完了し、運が悪ければいつまでたってもソートが完了しません。
スターリンソート
これは、左から順番に要素を確認し、それまでに出てきた最大の値を記録していきます。
次の要素がその最大値よりも小さい値だったら、その要素を「並びを乱すもの」と判断して「粛清」します。
最後まで確認すると、残された要素は昇順に並んでいます。
取り除かれた要素をどうするかは、このソートでは考えません。
一度左から右へ確認するだけなので、とても短い時間で終わりますが、要素の数がソート前と比べて減ります。
アベソート
これは、スターリンソートと似ていて、左から順番に要素を確認し、それまでに出てきた最大の値を記録するのは同じです。
しかし、次の要素がその最大値よりも小さい値だったら、粛清するのではなく、その要素を最大値に置き換えてしまいます。
これを最後まで繰り返すと、左から右へ昇順に並ぶことになります。
ソート前後で要素の数は変わらないですが、要素の値そのものが変わることになります。
ポモドーロソート
これは、一定時間だけユーザー（人）がソートを進め、その一定時間が過ぎたら作業を中断し、しばらく休憩してから再び続きを行います。
時間管理術である、ポモドーロテクニック、よくあるのは「25分作業して5分休憩する」というルールに従ってソートを進めるのが特徴です。
データを早く並べ替えることよりも、作業する人が集中力を維持できることを目的としています。
最終的にユーザーが頑張れば、ちゃんと昇順に並べることはできますが、ユーザーの労力を伴います。
こちらはユーザーがどのようにしてソートを進めていくかの部分の実装を考える必要がありますが、今回は、ソート前の配列に対して、要素番号を2つユーザーが指定でき、ボタンを押せばそれらの要素番号の要素が入れ替わる、という仕組みを設け、これを何度も行ってソートする、という機能を付けることにしました。
各アルゴリズムの実装例
では、各アルゴリズムをどう実装するかの例について紹介していきます。
ボゴソート
単純にシャッフルを繰り返します。
シャッフル後、ソートされたかどうかを確認するために、Forループの自動指標付け有効にした入力から一つずつ要素を取り出し、前の要素よりも大きくなっているかを判断し続け、一回でもFalseになったらソートされていないとみなします。
Falseになったら即終了、はForループに対して条件端子を設定することで実装できます。
性質上、ソート対象の要素数が多いといつまでたってもプログラムが終わらないため、強制的に終わらせるために停止ボタンもつけておくほうがいいです。
スターリンソート
ソート前の要素を一つずつ順に調べて、より大きい値が出てきたらその値を最大値として扱い、その最大値よりも小さい要素は消す、のですが、消されたことを強調するために、配列のサイズそのものは変えません。
グラフに表現する際には、消されたことを分かりやすくするため、「NaN」に置き換えることで、グラフに表現はされないものの配列の要素としては存在している状態としています。
なお、最初の要素を配列から削除して「最初の最大値」としてシフトレジスタの初期化に使わなくても、以下のようにシフトレジスタの初期化時に明らかに一番小さくなる数字（-inf）を指定すれば、もう少しスッキリ書けます。
アベソート
スターリンソートとやることはほぼ一緒で、最大値との大小比較後の処理を少し変える（NaNを使用しない）だけです。
ポモドーロソート
人間がソートする、という仕組みの部分と、時間を測るという部分をどう実装するか、今回はイベントストラクチャと時間測定用のループを組み合わせてみました。
時間測定の部分は少しややこしいですが、以下の例では、集中時間が10秒、休憩時間が5秒になるものとし、これらを交互に繰り返させるようにしています。
もっとわかりやすく書くなら簡易的なステートマシンの形にするのがいいですが、今回はフィードバックノードを多く駆使してケースを分けずに選択関数のみで切り替えられるように組んでいます。
決定ボタンが押された、つまり値変更イベントが発生した場合には、ユーザーが入力した二つの要素番号の値から、指標配列と部分配列置換を使って要素を入れ替えています。
入れ替えた後に、ソートされているかを確認し、ソートが完了していたらWhileループを止めるようにしています。
今回は、ジョークソートを実装する方法を紹介しました。
世の中にジョークソートと呼ばれるものはまだいくつかあります。
それらについても、無理やりにでもLabVIEWで実装するにはどうすればいいか、を考えるのは、最終的に昇順に並べる、などといった目的もわかりやすいので、プログラムでの「表現力」を高める題材として面白いと思います。
実用性はないですが、こんな話もあるんだなということで参考になればうれしいです。
ここまで読んでいただきありがとうございました。
コメント