Edited at

List.Sort((a,b)=>(a-b))について


はじめに

夏ぼっちカレンダー(仮)の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