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

Posted on   |   In   |  

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

ソートの説明

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

次の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. 「木を作る」、「ソートする」、「確定したノードを取り除く」を繰り返し行う

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

末文

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