デレステキャラソートのソートの仕組みに関する質問があったので、大したものではないですがソートのアルゴリズムについて書きます。
ソートの説明
データの構造に木構造を使った仕組みになってます。
次の3つの処理を繰り返し行うことで順位を確定します。
- 木を作る
- ソートする
- 確定したノードを取り除く
説明しにくいので例を使って説明していきます。
例では簡易的に28個のノード(01番~28番)を最終的に01,02,03,…,27,28とソートすることを目指します。
#1. 「木を作る」
rootノード(構造上のノード)の下に最大5つの子ノード(01番~28番)がぶら下がるように複数の木を作ります。
※それぞれの木にぶら下げるノードはランダムで決定します
例:6つの木ができました(深さ1なのでイメージしにくいですが)
#2. 「ソートする」(ユーザによる順位付け)
上位が親ノード、下位が子ノードになるようにノードを付け替えます。
例:
1つ目の木では05,16,17,23,28の順番に付け替えます。
rootノードの子ノードが05で、05の子ノードが16で、16の子ノードが17で、17の子ノードが23で、23の子ノードが28です
#3. 再び「木を作る」
深さ1のノードを使って、#1と同様に新しく木を作ります。今回も深さ1の子ノードは最大5つです。
例:深さ1のノードは6つあるので2つの木を作ります。(本来はランダムで決めますが今回は元の並び通り)
#4. 再び「ソートする」(ユーザによる順位付け)
#2と同じ処理です。上位が親ノード、下位が子ノードになるようにノードを付け替えます。
例:
1つ目の木では02,05,07の順番に付け替えます(他の構造は維持します)。
rootノードの子ノードが02で、02の子ノードが05で、05の子ノードが07です
#5. 再び「木を作る」→「ソートする」
今までと同じ手順です。ソートまで進めます。
例:深さ1のノード(01,02)は2つなので1つの木になります。
#6. 「確定したノードを取り除く」
木が1つ&深さ1の子ノードが1つになった場合、その子ノードの順位が確定します。
確定したノードは木から取り除きます。順位は取り除いた順番です。
深さ2だったノードはそれぞれ別の木になります。
例:
深さ1の子ノード(01)が1つなので、01の順位が確定します。
深さ2だったノード(15,03,02)は新しい木になります。
確定したノード[01,]
#7. 「木を作る」、「ソートする」、「確定したノードを取り除く」を繰り返し行う
これらの操作を繰り返すことで最終的にすべてのノードの順位を確定します。
末文
思い出しながら書いたので細部の違いはありますが、基本はこんな感じです。