この記事は2022年traPアドベントカレンダー30日目、2022年Springin'公式アドベントカレンダー12月24日の記事です。

こんにちは。@ikura-hamuです。この記事が投稿される12月24日はクリスマスイブです。今日の夜はサンタさんがプレゼントを子供たちの家に届けに行くわけですが、サンタクロースの負担を今まで考えたことはありますか？日本だけでも1000万人以上^[1] の子供がいて、そのすべての家にプレゼントを配らなくてはいけないわけです。しかも順番を間違えないようにしなくてはいけないので大変ですね。きっと長い時間をかけて順番に並べているんでしょうが、トナカイとかが突っ込んできて順番がぐちゃぐちゃになっちゃうこともあるでしょう。

そこでこの記事ではサンタさんに、プレゼントを順番に並べ替える（ソートする）ための方法を紹介したいと思います。

使用ツール

今回使うツールはSpringin'（スプリンギン）です。Springin'はざっくり言うと「文字を使わないプログラミング言語」です。詳しくは公式ページや僕が以前書いた記事を読んでみてください。

スマホでゲームがつくれるアプリ Springin’（スプリンギン）

文字を使わず、直感的な操作だけでオリジナルゲームや動くマンガなどが作れるアプリ。言葉の壁を越え、世界中の誰もがクリエイターになれるプラットフォームです。

Springin’（スプリンギン）| 創造的プログラミングアプリ

ただ、Springin'でソートするってかなり変人です。アルゴリズム系ってSpringin'の一番の苦手分野なんですよね。しかもゲームとかで使えるわけでもなく、ただただソートするだけです。こんな役に立たない記事書いても誰も読まないですね。サンタさんだってこんなの見せられたら困惑してしまいます。やっぱりやめましょう。

おわり

いかがでしたか？
今回はSpringin'でソートする必要なんてないという結論でした。
皆さんもやってみてください。

書きます書きますすみませんでした、読むのやめないでください、ちゃんと真面目に書くから怒らないでよ、ね？

ただ、他のワークの制作に使えないことはほぼ間違いないので、「変な人ががなんかしゃべってるな」ぐらいで読んでください。

いろいろなソート

プログラミングで数字を小さい順もしくは大きい順に並べることを「ソート」といいます。ソートにはいろんな方法があり、「クイックソート」「ヒープソート」などそれぞれに名前がついています。今回Springin'を使って実装するのは「選択ソート」というものです。じつは2年前にもクリスマスにソートをテーマにしたワーク「プレゼンソート」を出しているのですが、その際は「バブルソート」という方法を使いました。絵と文字がありえんぐらい下手なワークですが、興味のある方は見てみてください。ワークバージョンが1なので、アプリ版のみです。

Springin'上での前提

ソートでは数の大きさ比べを繰り返すのですが、Springin'は「文字を使わないプログラミング言語」ですので、当然数字も使えません。（厳密には2進数を使えば数字を扱えなくはないですが、直接的に数字を扱うことはできません。）そこで今回は下のような大きさの異なる5つのブロックと重力を用います。床にブロックを落とした状態で接触属性を使って大きさを比べることで数の大小を調べます。

選択ソートのしくみ

選択ソートのしくみを説明しようと思いますが、かなり簡単です。数字が1列にランダムに並んでいて、それを左から小さい順に並べることを考えます。

1. まず一番小さい数を探します。
2. その一番小さい数と左端の数を交換します。
3. 左端を除いた中で一番小さい数を探します。
4. 残ってる数の左端と交換します。
   ・
   ・
   ・
   と繰り返します。

図で表すとこんな感じです。

背景が黄色くなっている場所が入れ替えた部分、斜体が入れ替えを行ってそれ以降除いて考えるようになった部分です。

これを使うことで、どのような数でも小さい順に並べることができます。
今回のSpringin'での実装では、入れ替えじゃなくて違う部分に持っていくということにしました。これでも一応ソートにはなります。なんで本当のバブルソートでは入れ替えを行っているのかは、詳しくないので推測ですが、メモリとかが関わってそうだなと勝手に思っています。何でSpringin'では入れ替えをしないかというと、めんどくさいのと実装が思いつかなかったからです。移動させるならワープ１個で済みますが、入れ替えはワープが2個必要です。（「プレゼンソート」では入れ替えをやってますが、かなり汚くなりました。）（そして今回も結局2回ワープを使いました。)
なのでこれが選択ソートと呼べるかどうかは微妙になってしまうのですが、考え方は同じなので許してください。

Springin'での実装

ここからSpringin'でのソートの実装をしていきます。全体像はこのようになります。

まあまあ長くなるので、読みながら作っていくのがいいと思います。
大きく「一番小さいものを判定する部分」、「一番小さいものを取り除いて移動させる部分」の2つに分けて考えていきます。

その前に、いくつか準備をしましょう。まずは下向きの重力を付けます。最大がおすすめです。次に、上で触れたように今回ソートの対象となる数字が書かれたブロックを用意します。大きいものほど縦に大きくしましょう。横幅は特にありませんが、同じ幅だとわかりやすいのと、あまり太すぎるとシーンに収まらないので適度な太さにしましょう。これらのブロックにはあとから「接触」属性を付けますが、今は何もつけなくて大丈夫です。

また、ブロックを置くための床が必要です。普通の細長い四角のアイテムで大丈夫です。ブロックの移動前後で二つ必要になります。落ちたら困るので、ピンを付けておきましょう。写真では細かい仕切りのようなアイテムとか縦向きの壁とかも置いてありますが、これはブロックを置きやすくする目印なので、なくても大丈夫です。

これらのアイテムが用意出来たら、写真のように並べておきましょう。数字の順番は何でもいいです。

一番小さいものを判定する部分

とりあえず写真を貼ります。

まず、床の下に床と同じ長さの棒を置いて属性を付けます。僕は床と同じアイテムにしました。（アイテムは使いまわせるなら使いまわした方が楽ですからね。リユースです）

• 「ピン」と「物理無効」を付けて
• 上に並んだ5つの灰色の小さい四角に向けて「接触」を付けます。

これらの四角にも全て同じ属性を付けます。

• 「消滅」をつけて、
• さっきの長い棒に向けて「リセット」を付けます。

このとき四角は、5つのブロックのそれぞれ真上になるように配置しましょう。

この長い棒と5つの四角が最小のブロックを見つけるのに使われます。どちらも後から属性を追加するので、長い棒を「バー」、四角を「センサー」と呼ぶことにします。

「センサー」を置いておくためのスペースを作ります。「バー」と同じ形でいいと思います。写真を参考にして配置し、「ピン」「消滅」を付けてください。「センサー置き場」と呼ぶことにします。

操作するためのボタンを作ります。2つ必要になります。どちらのボタンにも「ピン」を付けます。その後、一つ目のボタン「ボタン１」には、

• 「消滅」を付け、
• 「連鎖」を「センサー置き場」につけます。

このボタンを押すと「センサー置き場」が消えるようになりました。

もう一つのボタン「ボタン２」には、

• 「バー」に向けて上向きの「動力」をかけるようにします。

このボタンを長押しすると、「バー」が上に動くようになりました。そして「センサー」に当たると元の場所に戻るはずです。

ここで動作確認をしてみましょう。まず「ボタン1」を押してください。「センサー置き場」が消えて、ブロックの上に「センサー」が乗っかるはずです。その状態で「ボタン2」を長押ししてください。「バー」が下の方にある「センサー」にぶつかると「センサー」は消えて「バー」はもとの場所に戻ります。「ボタン2」を長押しし続けると下から順番に「センサー」が消えていくはずです。こうならない場合はどこかで間違っていると思います。

この「下から順番に」が大事です。「下から順番に」ということは、「その時点で一番下にあるセンサーが消える」すなわち「最小値を見つける」ということだからです。

ここまでで一番小さいものを見つける部分を作ることができました。

一番小さいものを取り除いて移動させる部分

こちらもとりあえず写真を貼っておきます。ただ、隠れて見えなくなっている部分もあるので気を付けてください。(完成図とおなじ)

ブロックを移動させるために、「ワープ」と「反転」を使います。やりたいことは、「一番小さいものを移動させて並べる」です。並べるためには「ワープ」の出口を適切な位置に移動させる必要がありますが、これも「ワープ」で行います。つまりブロックを移動させるための「ワープ」と、その「ワープ」の出口を移動させる「ワープ」が必要です。

まずは一つ目の、「ブロックを移動させるためのワープ」を作ります。

初めに「ブロックワープ出口」を作ります。写真で言う青い正方形です。これに「物理無効」を付けてください。

ワープを発動させるためにはワープの入り口のアイテム「ブロックワープ入口」をブロックに当てる必要があります。今回はそれに「反転」を使います。写真のようなアイテムを作成し、横向きで使ってください。

ポイントは左上の小さい点です。Springin'の「反転」は自動で反転の中心が決められますが、これをつけることで反転の中心を自分が思うように変えることができます。

「ブロックワープ入口」には、

• 「ピン」を付け、
• 「ブロックワープ出口」に向けて「ワープ」を設定します。

「ブロックワープ入口」を5個作り、それぞれのブロックの下に、小さい点がブロックに触れないよう気を付けて置いてください。

次に、「ブロックワープ出口」をワープさせる仕組みを作ります。

「ブロックワープ出口」がワープしてくる場所、つまりブロックを落としたい場所に「ブロックワープ出口ワープ出口」（写真の水色の丸）を置きます。等間隔に置けるとよいです。横一直線に並べてもいいのですが、写真のように階段状になると速く動きます。ただ、位置の調整が難しいので、階段状にしてうまくいかなかったら一直線に直してください。属性はとりあえず「ピン」と「物理無効」を付けます。

「ブロックワープ出口」をワープさせるための「ブロックワープ出口ワープ入口」も作ります。(灰色の四角)これには

• 「消滅」を付け、
• 「フラグ」をワークフラグのどれか一つ（どれでもいいです）のオフに設定します。

それを4つ作り、一番右の「ブロックワープ出口ワープ出口」以外 の少し上（ぎりぎりの場所）に置きます。それぞれの「ブロックワープ出口ワープ入口」には、

• 「ワープ」を 右隣の「ブロックワープ出口ワープ出口」 につけます。

「ブロックワープ出口ワープ出口」から「接触」を自分の上にある「ブロックワープ出口ワープ入口」に向けてつけます。

最後にブロックが床についたことを確かめるためのアイテム「接地センサー」を作ります。「ワープ出口ワープ出口」の真下の床に左から4つ並べます。属性は、

• 「ピン」、「消滅」、「物理無効」を設定、
• 「リセット」を 真上の「ブロックワープ出口ワープ入口」に向けて設定します。

また、すべてのブロックで、「接触」をすべての「接地センサー」に向けて設定します。

これでちゃんと動くはずです。ブロックを適当な順番で並べた後に、ボタン1を押して「センサー置き場」を消し、ボタン2を長押しすると順番に並びます。

これを書いている途中で中断してしまったので、もしかしたら抜けていることがあるかもしれません。これの通り作ったのに動かないみたいなのがあったら教えてください、

動作の様子

ところで

計算量

プログラミングではよく「計算量」という概念を扱います。僕はあまり詳しくないのですが、ざっくり言うと「計算した 回数」のことです。数を足したら1回、大きさを比べたら1回、のように数えます。（アルゴリズム班の人、間違ってたら教えてください）

また、計算量の表し方としてランダウの記号というものを使います。$O$という記号を使い、N個の入力(今回であればソートする数が何個あるか)に対して$O(N)$や$O(N^2)$のように表し、それぞれ計算量が最悪の場合（一番多く計算しなくてはいけない場合)、ざっくり$N$,$N^2$に比例して大きくなることを表しています。（数学的な定義も存在しますが、自分が理解できていません。）$O(N^2)$よりも$O(N)$の方が計算量が少なく、速く動作する良いプログラムだと言えます。

選択ソートの計算量

それでは選択ソートの計算量はどれほどになるのでしょうか。$N$個の数を選択ソートで並べ替えることを考えましょう。
選択ソートではいくつかあるものの中から最小のものを探すという作業を何度か行いますが、この作業は（普通にやったら）$N$個に対して$N-1$、すなわち$O(N)$の計算量がかかります。（もちろん普通でない方法もあって、データ構造を工夫すれば$O(1)$とか$O(\log N)$でもできるらしいです。）
この操作を何回も繰り返しますが、最小値を探す対象は一個ずつ減っていきます。なので、全体の計算量は次のように計算できます。
${\sum }_{k=1}^N(k-1)=\frac{1}{2}N(N+1)-N=\frac{1}{2}{N}^2-\frac{1}{2}N$

つまり、選択ソートの計算量は$O(N^2)$になります。

じゃあSpringin'では？

Springin'ではどうなっているでしょう？
まずは一番小さい数を見つけます。計算量は$O(N)$になるはずですが、
.
.
.

あれ？１回？

そうなんです。Springin'で最小の値を見つけようとすると、1回の計算でできてしまうんです。^[1]なぜかというと、「接触」属性、つまり当たり判定を使えば、要素がいくつあっても一回で最小値（最大値でも同じ）を調べられるからです。（やってみてはいないですが、ちょっと工夫すれば全探索も$O(1)$でできそうです。）

これを$N$回行えばいいので、

Springin'での選択ソートは$O(N)$です!

おわり

ソートの計算量がSpringin'で小さくなるのはかなり衝撃的で、気づいた時は思わず声が出てしまいました。
もちろんこれは計算「量」の話であって、計算「時間」ではSpringin'が圧倒的に遅いです。ただ、今回のSpringin'での実装には速度の面でかなり改善の余地があります。一般にSpringin'で何かに反応して動作を起こすとき、「接触」属性を使うと遅くなることが知られています。^[1] 大小を判定するのに「接触」を使うのはしょうがないですが、他の部分でも「接触」を使っているので、それを上手く改善して高速化すれば、一定条件下だけでも文字プログラムに勝てるかもしれないですね。

こんな何にも役に立たない記事を最後まで読んでいただきありがとうございました。これでサンタさんもプレゼントを順番に並べて正しく子供たちに届けることができるといいですね。僕はクリスマスプレゼントに冬休みが追加で1週間ほしいです。

メリークリスマス！そしてよいお年を！

明日の2022traPアドベントカレンダー（最終日！）の担当は@inutamago_dogeggです。