デレステキャラソートのアルゴリズム

デレステキャラソートのソートの仕組みに関する質問があったので、大したものではないですがソートのアルゴリズムについて書きます。

ソートの説明

データの構造に木構造を使った仕組みになってます。

次の3つの処理を繰り返し行うことで順位を確定します。

  • 木を作る
  • ソートする
  • 確定したノードを取り除く

説明しにくいので例を使って説明していきます。

例では簡易的に28個のノード(01番~28番)を最終的に01,02,03,…,27,28とソートすることを目指します。

#1. 「木を作る」

rootノード(構造上のノード)の下に最大5つの子ノード(01番~28番)がぶら下がるように複数の木を作ります。
※それぞれの木にぶら下げるノードはランダムで決定します

例:6つの木ができました(深さ1なのでイメージしにくいですが)

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
─┬16
05
28
23
17
─┬24
07
27
08
14
─┬10
12
22
09
02
─┬20
03
19
04
21
─┬15
25
01
26
─┬18
06
13
11

#2. 「ソートする」(ユーザによる順位付け)

上位が親ノード、下位が子ノードになるようにノードを付け替えます。

例:
1つ目の木では05,16,17,23,28の順番に付け替えます。
rootノードの子ノードが05で、05の子ノードが16で、16の子ノードが17で、17の子ノードが23で、23の子ノードが28です

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
──05
16
17
23
28
──07
08
14
24
27
──02
09
10
12
21
──03
04
19
20
22
──01
15
25
26
──06
11
13
18

#3. 再び「木を作る」

深さ1のノードを使って、#1と同様に新しく木を作ります。今回も深さ1の子ノードは最大5つです。

例:深さ1のノードは6つあるので2つの木を作ります。(本来はランダムで決めますが今回は元の並び通り)

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
─┬05
│ └16
│ └17
│ └23
│ └28
07
│ └08
│ └14
│ └24
│ └27
02
09
10
12
21
─┬03
│ └04
│ └19
│ └20
│ └22
01
│ └15
│ └25
│ └26
06
11
13
18

#4. 再び「ソートする」(ユーザによる順位付け)

#2と同じ処理です。上位が親ノード、下位が子ノードになるようにノードを付け替えます。

例:
1つ目の木では02,05,07の順番に付け替えます(他の構造は維持します)。
rootノードの子ノードが02で、02の子ノードが05で、05の子ノードが07です

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
──02
09
│ └10
│ └12
│ └21
05
16
│ └17
│ └23
│ └28
07
08
14
24
27
──01
15
│ └25
│ └26
03
04
│ └19
│ └20
│ └22
06
11
13
18

#5. 再び「木を作る」→「ソートする」

今までと同じ手順です。ソートまで進めます。

例:深さ1のノード(01,02)は2つなので1つの木になります。

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
──01
15
│ └25
│ └26
03
│ ├04
│ │ └19
│ │ └20
│ │ └22
│ └06
│ └11
│ └13
│ └18
02
09
│ └10
│ └12
│ └21
05
16
│ └17
│ └23
│ └28
07
08
14
24
27

#6. 「確定したノードを取り除く」

木が1つ&深さ1の子ノードが1つになった場合、その子ノードの順位が確定します。
確定したノードは木から取り除きます。順位は取り除いた順番です。
深さ2だったノードはそれぞれ別の木になります。

例:
深さ1の子ノード(01)が1つなので、01の順位が確定します。
深さ2だったノード(15,03,02)は新しい木になります。

確定したノード[01,]

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
──15
25
26
──03
04
│ └19
│ └20
│ └22
06
11
13
18
──02
09
│ └10
│ └12
│ └21
05
16
│ └17
│ └23
│ └28
07
08
14
24
27

#7. 「木を作る」、「ソートする」、「確定したノードを取り除く」を繰り返し行う

これらの操作を繰り返すことで最終的にすべてのノードの順位を確定します。

末文

思い出しながら書いたので細部の違いはありますが、基本はこんな感じです。