はじめに
夏ぼっちカレンダー（仮）の18日目の記事です。
記事の中に間違いなどあれば指摘していただけると幸いです。
List.Sort((a,b)=>(a-b))がよく分からない
要素数5のリストの
List.Sort((a,b)=>(a-b))の中身を以下のコードで出力してみます。
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static void Main()
{
var list = new List<int>();
for (int i=5; 1 <= i; --i)
{
list.Add(i);
}
Console.WriteLine("ソート前");
Console.WriteLine();
foreach (var i in list)
{
Console.Write($"{i} ");
}
Console.WriteLine();
Console.WriteLine("ソート");
Console.WriteLine();
list.Sort((a, b) => {
Console.Write($"a:{a} ");
Console.Write($"b:{b} ");
Console.WriteLine($"a-b:{a-b}");
return a - b;
});
Console.WriteLine();
Console.WriteLine("ソート後");
Console.WriteLine();
foreach (var l in list)
{
Console.Write($"{l} ");
}
}
}
すると以下のように出力されます
ソート前
5 4 3 2 1
ソート
a:4 b:5 a-b:-1
a:3 b:5 a-b:-2
a:3 b:4 a-b:-1
a:2 b:5 a-b:-3
a:2 b:4 a-b:-2
a:2 b:3 a-b:-1
a:1 b:5 a-b:-4
a:1 b:4 a-b:-3
a:1 b:3 a-b:-2
a:1 b:2 a-b:-1
ソート後
1 2 3 4 5
よく分からないところ
①それぞれのaとbの値の決め方
②ループの回る回数（処理の回数）
③returnされた値の利用方法
Sortについて
まず、順番が前後しますが「③returnされた値の利用方法」についてです。
Sortにはいくつか種類があり、
ここで使用されている種類は「Sort(Comparison)」です。
他に、Sort()やSort(IComparer)があります。
Sort(Comparison)はComparisonデリゲートから返された値が
負の場合に要素の位置を交換します。
つまり、
上の例では以下のことが起こっています。
① 5 4 3 2 1の配列が存在
② 4と5が比較され、-1が返される
③ 負の値が返されたので4と5の順番を逆にする
④ 4 5 3 2 1の配列になる
⑤ 3と5が比較され、-2が返される
⑥ 負の値が返されたので3と5の順番を逆にする
⑦ 4 3 5 2 1の配列になる
…
ここから、
「③returnされた値の利用方法」は
負の時に要素の順番を入れ替えることだということが分かります。
並び替えるアルゴリズムの選択
次に
「①それぞれのaとbの値の決め方」と「②ループの回る回数（処理の回数）」
についてです。
要素が16未満の際は「挿入ソート」
それ以外は（たぶん）イントロソート（クイックソート＋ヒープソート）
の使用になるようです。
上の要素数は5だったので
挿入ソートが行われていました。
そのため、
「①それぞれのaとbの値の決め方」と「②ループの回る回数（処理の回数）」も
挿入ソートの方法に沿ったものになっていました。
要素数を20にするとクイックソートになりました。
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static void Main()
{
var list = new List<int>();
for (int i = 20; 1 <= i; --i)
{
list.Add(i);
}
Console.WriteLine("ソート前");
Console.WriteLine();
foreach (var i in list)
{
Console.Write($"{i} ");
}
Console.WriteLine();
Console.WriteLine("ソート");
Console.WriteLine();
list.Sort((a, b) => {
Console.Write($"a:{a} ");
Console.Write($"b:{b} ");
Console.WriteLine($"a-b:{a-b}");
return a - b;
});
Console.WriteLine();
Console.WriteLine("ソート後");
Console.WriteLine();
foreach (var l in list)
{
Console.Write($"{l} ");
}
}
}
以下のように出力されます
ソート前
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
ソート
a:20 b:11 a-b:9
a:11 b:1 a-b:10
a:20 b:11 a-b:9
a:19 b:11 a-b:8
a:11 b:3 a-b:8
a:18 b:11 a-b:7
a:11 b:4 a-b:7
a:17 b:11 a-b:6
a:11 b:5 a-b:6
a:16 b:11 a-b:5
a:11 b:6 a-b:5
a:15 b:11 a-b:4
a:11 b:7 a-b:4
a:14 b:11 a-b:3
a:11 b:8 a-b:3
a:13 b:11 a-b:2
a:11 b:9 a-b:2
a:12 b:11 a-b:1
a:11 b:10 a-b:1
a:2 b:11 a-b:-9
a:12 b:11 a-b:1
a:11 b:2 a-b:9
a:14 b:13 a-b:1
a:15 b:14 a-b:1
a:16 b:15 a-b:1
a:17 b:16 a-b:1
a:18 b:17 a-b:1
a:19 b:18 a-b:1
a:12 b:19 a-b:-7
a:12 b:18 a-b:-6
a:12 b:17 a-b:-5
a:12 b:16 a-b:-4
a:12 b:15 a-b:-3
a:12 b:14 a-b:-2
a:12 b:13 a-b:-1
a:20 b:19 a-b:1
a:3 b:1 a-b:2
a:4 b:3 a-b:1
a:5 b:4 a-b:1
a:6 b:5 a-b:1
a:7 b:6 a-b:1
a:8 b:7 a-b:1
a:9 b:8 a-b:1
a:10 b:9 a-b:1
a:2 b:10 a-b:-8
a:2 b:9 a-b:-7
a:2 b:8 a-b:-6
a:2 b:7 a-b:-5
a:2 b:6 a-b:-4
a:2 b:5 a-b:-3
a:2 b:4 a-b:-2
a:2 b:3 a-b:-1
a:2 b:1 a-b:1
ソート後
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
ここから、
「①それぞれのaとbの値の決め方」と「②ループの回る回数」は、
ソートする際に使用するアルゴリズムによることが分かりました。
まとめ
・Sort(Comparison)はComparisonデリゲートから返された値が、負の場合に要素の位置を交換する
・デリゲートの引数の値の決め方と、処理の回数はアルゴリズムによる
参考
C#の配列やListをソートする (List.Sort)
List.Sort Method
C#の安定ソートを検討
ノームソート
【Unity】ソートアルゴリズム12種を可視化してみた
Sortメソッドの並び替え順序
ヒープソート
イントロソート
挿入ソート
C# デリゲートについて
Comparison Delegate